树和叉树(数据结构).doc

(tree)的概念在日常生活中,可以见到很多情形可以归结为树结构。如:家族谱系、行政管理机构、DOS和Windows磁盘文件管理系统等。资料个人收集整理,勿做商业用途我们讨论的树和自然界的树在生长方向上正好相反,它是倒长的树,即根朝上,枝干和叶子朝下。例1:某家族谱系的一部分例2:国家行政管理机构的一部分例3:DOS和Windows磁盘文件的一部分C:\……MyTc程序Tc1Tc2……MyVc程序Vc1Vc2……树是一种层次结构,属于非线性结构。我们学过的线性表可以灵活组织数据,但它受到线性结构的限制,表达层次结构不太方便。资料个人收集整理,·树T是n(n≥0)个结点的有限集合。它满足:(1)仅有一个特定的结点,称为根(root)结点;(2)其余结点分为m(m≥0)个互不相交的非空有限集合,,……,,其中每个集合自身又是一棵树,称为根的子树(subtree)。·为了表述方便,把没有结点的树称为空树。·树的定义具有递归性:即一棵树是由根及若干棵子树构成的,而子树又是由根及若干棵子树构成的,……。表达树的方法通常有4种:树形、凹入、集合和广义表(1)树形表示法ABCDEFGH凹入表示法ABCEFDGH集合嵌套表示法ACDB资料个人收集整理,勿做商业用途广义表表示法T(A(B,C(E,F),D(G,H))),通常引用树和人的特征及术语来描述。(1)结点和树的度(degree)结点所拥有的子树的个数称为该结点的度,而树中各结点的度的最大值称为该树的度。ABCDEFGH如:·结点B、E、F、G和H的度数是0·结点C和D的度数都是2·结点A的度数是3;显然3也是树的度数(2)叶子(leaf)结点和分支结点度为0的结点称为叶子结点(终端结点);度不为0的结点称为分支结点(非终端结点)。一棵树除了叶子结点就是分支节点。ABCDEFGH如:·结点B、E、F、G和H是叶子结点·结点A、C和D是分支结点(3)孩子(child)结点、双亲(parents又称父亲)结点、兄弟(brother)及堂兄弟结点树中一个结点的子树的根称为该结点的孩子,该结点称为其孩子结点的双亲结点。同一个双亲的孩子结点互称为兄弟。双亲在同一层的结点互为堂兄弟。资料个人收集整理,勿做商业用途ABCDEFGH如:·结点B、C和D均为结点A的孩子结点;A是B、C和D的双亲结点·结点E和F为孩子C的结点;C是E和F的双亲结点·结点G和H为孩子D的结点;D是G和H的双亲结点·显然结点A没有双亲结点(因为A不是子树的根)·结点B、C和D互为兄弟;结点E和F互为兄弟;结点G和H互为兄弟。但结点E、F为一方和G、H为另一方互为堂兄弟资料个人收集整理,勿做商业用途(4)祖先(ancestor)和子孙(descendant)结点的祖先是从根到该所经分支上的所有结点。反之,以某结点为根的子树中的任一结点称为该结点的子孙。显然祖先和子孙关系是父子关系的延伸。资料个人收集整理,勿做商业用途ABCDEFGH如:·结点A是结点B、C、D、E、F、G和H的祖先;反之,结点B、C、D、E、F、G和H是的结点A的子孙(5)结点的层数(level)和树的深度(depth,或称高度height)结点的层次从根结点开始算起,根结点的层数为1,其余结点的层数等于其双亲结点的层数加1。比如,如果某个结点的层数为h,则其子树就在第h+1层。资料个人收集整理,勿做商业用途树中各个结点层数的最大值称为树的深度(高度)。ABCDEFGH如:·结点A的层数为1;结点B、C和D的层数为2;结点E、F、G和H的层数为3·树的深度(高度)为3。(6)有序树(orderedtree)和无序树(unorderedtree)若一棵树中结点的各子树从左到右是有次序的,即若交换了某结点各子树的相对位置就构成不同的树,则称这棵树为有序树,否则称为无序树。资料个人收集整理,勿做商业用途(7)路径(path)从树中的一个结点到另一个结点的路途ABCDEFGH如:A-C-E,A-D-H等但B-A-D-G不是路径,因为树不能这样遍历。(8)森林(forest):m(m≥0)棵互不相交的树的集合ABCDEFGHABCD树的逻辑关系:(1)树的任一结点都可以有0个或多个直接的后继结点(孩子,这也是非线性的原因),但至多只能有一个直接的前驱结点(双亲结点);资料个人收集整理,勿做商业用途(2)只有根结点没有前驱,叶子结点(终端结点)没有后继;(3)祖先与子孙关系是父子关系的延伸,它定义了树中各结点之间的纵向次序;(4)在有向树中,同一组兄弟结点从左至右有长幼之分。它定义了树中各结点之间的横向次序。