数据结构与41(树) .pptVIP

* 一、树的概念：是n（n=0）个结点的有限集合。 第四章 树 4.1 树的结构定义和基本术语 非空树: 只有一个根结点 还可以有m个互不相交的有限集合： T1，T2，…，Tm 其中每一个集合Ti(i=1,2,..,m)本身又是一棵树，并且称为根的子树。 * A B C D E F G H I J A是根 T1 = {B,E,F} T2 = {C,G,I,J} T3 = {D,H} 在树中，每个结点被定义为它的每个子树的根结点的前驱。 二、树的表示： 结点连线。 隐含：上方结点是下方结点的前驱。 * (2)集合图表示法:每棵树对应一个圆形，圆内包含根结点和子树。 A B C D E F G H I J A E B D H F C G I J * （3）凹入表示法:每棵树的根对应着一个条形，子树的根对应着一个较短的条形。 A B C D E F G H I J A B E F C G I J D H * (1)树的结点：包含一个数据元素及若干指向其子树的分支。 (2)结点的度（degree）：结点拥有的子树数。 (3)根结点：无前驱。 (4)叶子（终端结点）：度为零的结点。无后继。 (5)分支结点（非终端结点）：度不为零的结点。除根结点外，分支结点也称内部结点 （一个前驱，多个后继）。 (6)树的度:树内各结点的度的最大值。 A B C D E F G H I J 三、基本术语 * (7)孩子：结点的子树的根称为该结点的孩子。相应地，该结点称为孩子的双亲。 (8)兄弟：同一双亲的孩子之间互为兄弟。 (9)堂兄弟:有相同的祖父 (10)祖先：结点的祖先是从根到该结点所经分支上的所有结点。 (11)子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。 A B C D E F G H I J * A B C D E F G H I J (12)结点的层次：根为第一层，根的孩子为第二层。 (13)树的深度（高度）：树中结点的最大层次。 (14)有序树及无序树： 如： A A B C C B 是两棵不同的有序树。 * (15)森林：是m棵互不相交的树的集合。 对树中每个结点而言，其子树的集合即为森林。树和森林可以互相递归定义： Tree=(root, F) F = (T1, T2, … ,Tm) (m≥0) Ti = (ri,Fi) 当m≠0时，树根和子树森林之间存在下列关系：RF = {root,ri|1≤i≤m, m0} * 四、树的基本操作： 求根：ROOT(T); 结果：树T的根结点。 求双亲： PARENT(T, X); 结果：结点X在树T的双亲。 求孩子：CHILD(T，X，i); 结果：树T上X结点的第i个孩子。 建树：CREATE(X,T1,T2,…,Tn); 结果：建立一棵以X为根，以T1，T2，…，TN为子树的树 剪枝：DELETE(T,X,i); 结果：删除树T上结点X的第i棵子树。 * 线性结构 (1)第一个数据元素(无前驱) ???? (2)最后一个数