六章树ppt课件.ppt

《六章树ppt课件.ppt》由会员分享，可在线阅读，更多相关《六章树ppt课件.ppt（83页珍藏版）》请在三一文库上搜索。

1、第六章 树,树的概念和基本术语,树由n (n 0)个结点组成的有限集合。 如果n = 0，称为空树； 如果n 0，则 有一个特定的称之为根(root)的结点，它只有直接后继，但没有直接前驱； 除根以外的其它结点划分为m (m 0)个互不相交的有限集合T0, T1, , Tm-1，每个集合又是一棵树，并且称之为根的子树(subTree)。 每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。,树的表示 树型表示 a是根； T1,T2都是根a的子树，且本身也是一棵树 T1=b,d,e,f,i,j； T2=c,g,h；,凹入表表示,嵌套集合表示 嵌套括号表示 a ( b ( d, e

2、( i, j ), f ), c ( g, h ) ),树的基本术语 结点(node) 结点的度(degree) 结点的子树个数 分支(branch)结点 度不为0的结点 叶(leaf)结点 度为0的结点 子女(child)结点 某结点子树的根结点 双亲(parent)结点 某个结点是其子树之根的双亲,兄弟(sibling)结点 具有同一双亲的所有结点 祖先(ancestor)结点 若树中结点k到ks存在一条路径，则称k是ks的祖先 子孙(descendant)结点 若树中结点k到ks存在一条路径，则称ks是k的子孙 结点所处层次(level) 根结点的层数为1，其余结点的层数为双亲结点的层数

3、加1 树的高度(depth) 树中结点的最大层数,有序树 树中结点的子树由左向右有序，子树的次序不能互换 无序树 子树的次序可以互换 森林 m(m 0)棵互不相交的树的集合 对树中每个结点而言，其子树的集合即为森林,树的基本操作 初始化 求指定结点所在树的根结点 求指定结点的双亲结点 求指定结点的某一孩子结点 求指定结点的最右边兄弟结点 将一棵树插入到另一树的指定结点下作为它的子树 删除指定结点的某一子树 树的遍历,二叉树 (Binary Tree),二叉树的定义 一棵二叉树是n（n0）个结点的一个有限集合，该集合或者为空(n=0)，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交

4、的二叉树组成。(递归定义：用二叉树定义二叉树),二叉树的五种不同形态,二叉树的每个结点至多只有两棵子树（二叉树中不存在度大于2的结点） 在二叉树中，子树是有顺序的，下面两棵二叉树是不同的。 思考：画出由三个结点所能组成的所有二叉树。,二叉树的性质 性质1 若二叉树的层次从1开始, 则在二叉树的第 i 层最多有 2i-1 个结点。(i 1) 证明： i = 1 时，有2i-1 = 20 =1，成立 假定 ：i = k 时性质成立，即第k层最多有2k-1个结点； 当 i = k+1 时，由于二叉树的每个结点的度至多为2，故在第i层上的最大结点数为第i-1层上的最大结点数的2倍，第k+1的结点至多是

5、第k层结点的两倍，即总的结点个数至多为22k-1 = 2k,性质2 高度为k的二叉树最多有2k 1个结点。(k 1) 证明：仅当每一层都含有最大结点数时，二叉树的结点数最多，利用性质1可得二叉树的结点数至多为： 20 + 21 + 22 + 23 + + 2k-1 = 2k 1,性质3 对任何一棵二叉树, 如果其度为0的叶结点个数为n0, 度为2的非叶结点个数为 n2, 则有n0n21 证明： 1、结点总数n=度为0的结点数度为1的结点数度为2的结点：n = n0 + n1 + n2 2、另一方面，二叉树中一度结点有一个孩子，二度结点有二个孩子，根结点不是任何结点的孩子，因此，结点总数为：n

6、= n1 + 2n2 + 1 3、两式相减，得到：n0 = n2 + 1,特殊形态的二叉树 满二叉树 (Full Binary Tree) 一棵深度为k且有2k -1个结点的二叉树 完全二叉树(Complete Binary Tree) 若设二叉树的高度为h。除第h层外，其它各层的结点数都达到最大个数，第h层从右向左连续缺若干结点，这就是完全二叉树。,性质4 具有 n (n 0) 个结点的完全二叉树的深度为log2n 1 证明： 设完全二叉树的深度为 h，则根据性质2和完全二叉树的定义有 2h-1 - 1 n 2h 1 ，即 2h-1 n 2h 取对数 h-1 log2n h，又h是整数， 因

7、此有 h = log2n 1,性质5 如果将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号1, 2, , n-1,n，然后按此结点编号将树中各结点顺序地存放于一个一维数组中, 并简称编号为i的结点为结点i (1 i n)。,则有以下关系： 若i = 1, 则 i 无双亲 若i 1, 则 i 的双亲为i /2 若2*i n/2 的结点必定是叶结点 若2*i+1 = n, 则 i 的右子女为2*i+1，否则，i无右子女 若 i 为奇数, 且i不为1，则其左兄弟为i-1，否则无左兄弟； 若 i 为偶数, 且小于 n，则其右兄弟为i+1，否则无右兄弟 i 所在层次为 log2i +1

8、,二叉树的存储结构,顺序存储(数组表示),完全二叉树的数组表示 一般二叉树的数组表示,由于一般二叉树必须仿照完全二叉树那样存储，可能会浪费很多存储空间，单支树就是一个极端情况。 顺序存储的缺点： 存储空间浪费 动态变化困难 很少采用顺序存储实现二叉树,单支树,链式存储,二叉树链表表示的示例,三叉链表的静态结构,二叉链表的定义 typedef char TreeData; /结点数据类型 typedef struct node /结点定义 TreeData data; struct node *leftChild, *rightchild; BiTreeNode; typedef BiTreeN

9、ode* BiTree; /根指针,二叉树的基本操作 构造一棵空二叉树 判断一棵二叉树是否空二叉树 返回二叉树中的结点数 返回二叉树的高度 清空一个已经存在的二叉树 在二叉树中插入结点 在二叉树中删除结点 遍历一棵二叉树,二叉树的遍历,树的遍历指的是按照某种顺序访问二叉树中的每个结点，使得每个结点均被访问1次，而且仅被访问1次。 对于线性表，结点间有严格的前趋和后继关系，结点的遍历顺序也就是结点在线性表中的排列顺序。 对于二叉树而言，遍历顺序并不唯一。常见的遍历顺序有: 先序遍历 中序遍历 后序遍历 ( 先/中/后是对根而言),例 设访问根结点记作 V 遍历根的左子树记作 L 遍历根的右子树记

10、作 R 则可能的遍历次序有 先序 VLR 中序 LVR 后序 LRV,中序遍历 (Inorder Traversal) 中序遍历二叉树算法的定义： 若二叉树为空，则空操作； 否则 中序遍历左子树 (L)； 访问根结点 (V)； 中序遍历右子树 (R)。 遍历结果 a + b * c - d - e / f,中序遍历二叉树的递归算法 void InOrder ( BiTreeNode *T ) if ( T != NULL ) InOrder ( T-leftChild ); /递归 Visit( T-data); InOrder ( T-rightChild ); /递归 ,先序遍历 (Pre

11、order Traversal) 先序遍历二叉树算法的定义： 若二叉树为空，则空操作； 否则 访问根结点 (V)； 先序遍历左子树 (L)； 先序遍历右子树 (R)。 遍历结果 - + a * b - c d / e f,先序遍历二叉树的递归算法 void PreOrder ( BiTreeNode *T ) if ( T != NULL ) Visit( T-data); PreOrder ( T-leftChild ); PreOrder ( T-rightChild ); ,后序遍历 (Postorder Traversal) 后序遍历二叉树算法的定义： 若二叉树为空，则空操作； 否则

12、后序遍历左子树 (L)； 后序遍历右子树 (R)； 访问根结点 (V)。 遍历结果 a b c d - * + e f / -,后序遍历二叉树的递归算法： void PostOrder ( BiTreeNode * T ) if ( T != NULL ) PostOrder ( T-leftChild ); PostOrder ( T-rightChild ); Visit( T-data); ,*层序遍历 层序遍历二叉树算法的定义 若二叉树为空，则空操作； 否则， 根结点入队，并作为当前结点； 如队列不空，循环： 将当前结点的左右孩子(非空)入队； 做出队操作，队首元素作为当前结点 最后，

13、出队序列就是层序遍历序列 遍历结果 - + / a * e f b - c d,二叉树遍历应用,1、按先序建立二叉树(递归算法) 输入结点值的顺序必须对应二叉树结点先序遍历的顺序。 约定以输入序列中不可能出现的值作为空结点的值以结束递归。 例如用“”或用“-1”表示字符序列或正整数序列空结点。,Status CreateBiTree ( BiTree /CreateBiTree,2、计算二叉树结点个数(递归算法) int Count ( BiTreeNode *T ) if ( T = NULL ) return 0; else return (1 + Count ( T-leftChild

14、) + Count ( T-rightChild ) ); ,3. 求二叉树中叶子结点的个数(递归算法) int Leaf_Count(BiTree T) if(!T) return 0; /空树没有叶子 else if (!T-lchild /左子树的叶子数加上右子树的叶子数 ,4. 求二叉树高度(递归算法) int Depth ( BiTreeNode * T ) if ( T = NULL ) return 0; else int m = Depth ( T-leftChild ); int n = Depth ( T-rightChild ) ); return (m n) ? (m+

15、1) : (n+1); ,5、在二叉树中查找具有给定值的结点 BiTree findnode(BiTree t, Datatype x) if ( t = NULL) return NULL; else if ( t-data = x) return t; else return( findnode(t-lchild, x)| findnode(t-rchild, x) ); ,6、给定一棵二叉树，输出其嵌套括号表示 void print(BiTree t) if (t) printf(“%d”, t-data); if (t-lchild |t-rchild) printf(“(”); pr

16、int(t-lchild); if (t-rchild) printf(“,”); print(t-rchild); printf(“)”); ,二叉排序树(Binary Sort Tree),二叉排序树或者是一棵空二叉树；或者是具有下列性质的二叉树： （1）若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值。 （3）根结点的左右子树分别也是二叉排序树。 二叉排序树可以用来组织一组数据，并且实现在这组数据上的快速检索。,在二叉排序树上检索给定的值限定二叉查找树上任何两个结点均不相同） （1）若二叉排序树为空，查找失

17、败。 （2）首先用给定的值和根结点的值进行比较，若相等，则查找成功。 （3）若给定的值比根结点的值小，则转根结点的左子树进行查找。 （4）若给定的值比根结点的值大，则转根结点的右子树进行查找。,在上图的二叉排序树中查找下列关键字 ： （1）kay（2）Eva （3）Roy 计算在查找上述关键字时，各进行了几次比较运算？ 试想一下，在线性表中查找上述关键字需要作几次比较？,树和森林,树的存储结构 1、双亲表示法 以一组连续空间存储树的结点，同时在结点中附设一个指针，存放双亲结点在链表中的位置。 该方法利用每个结点只有一个双亲的特点，可以很方便求结点的双亲，但不方便求结点的孩子。,用双亲表示实现的

18、树定义 #define MaxSize 100 /最大结点个数 typedef char TreeData; /结点数据类型定义 typedef struct /树结点类型定义 TreeData data; int parent; TreeNode; typedef TreeNode TreeMaxSize; /树,2、孩子表示法(多重链表 ) 第一种方案：等数量的链域 空链域n(d-1)+1个。(d为树的度，n为结点数) =总链域n*d 已用链域(n-1),第二种方案：孩子链表 将每个结点的孩子链在该结点之后组成链表，再将所有头结点组成一个线性表,struct CTNode int chil

19、d; /孩子所在位置 CTNode *next; ; typedef CTNode* ChildPtr; struct CTBox ElemType data; ChildPtr firstchild; ; struct CTree CTBox nodesMAX_TREE_SIZE; int n, root;/结点数和根的位置 ;,G,6,F,5,E,4,D,3,C,2,B,1,A,0,3、树的左子女(第1个)-右兄弟(第1个)表示 二叉链表，结点结构： 空链域n+1个,用左子女-右兄弟表示实现的树定义 typedef char TreeData; typedef struct node Tr

20、eeData data; struct node *firstChild, *nextSibling; TreeNode; typedef TreeNode* Tree;,森林与二叉树的转换,森林转换成二叉树 如果F = T1,T2,Tm是森林，则可按照如下的规则将其转换成一棵二叉树B = (root, LB, RB) 1）若F为空，即m0，则B为空。 2）若F非空，即m0，则B的根root即为森林中第一棵树的根ROOT(T1)； B的左子树LB是从T1中根节点的子树森林F1= T11,T12, T1m1转换而成的二叉树； B的右子树RB是从森林F=T2, T3, , Tm转换而成的二叉树。,

21、二叉树转换成森林 如果B = (root, LB, RB)是一棵二叉树，则可按照如下规则转换成森林F = T1,T2,Tm。 1）若B为空，则F为空。 2）若B非空，则F中第一棵树T1的根ROOT(T1)即为二叉树的根root； T1中根结点的子树森林F1是由B的左子树LB转换而成的森林； F中除T1之外其余树组成的森林F=T2, T3, , Tm是由B的右子树RB转换而成的森林。,若结点 x 是其双亲 y 的左孩子，则把 x 的右孩子，右孩子的右孩子，都与 y 用连线连起来，最后去掉所有双亲到右孩子的连线。,树的遍历 先根(次序)遍历 （1）访问树的根结点； （2）从左向右依次先根遍历根的每

22、棵子树。 后根(次序)遍历 （1）从左向右依次后根遍历根的每棵子树； （2）访问树的根结点。,先根遍历 A，B，E，F，C，G，D，H，I，J 后根遍历 E，F，B，G，C，H，I，J，D，A,树的遍历算法可借助二叉树的实现 先根遍历某树等价于先序遍历该树对应的二叉树 后根遍历某树等价于中序遍历该树对应的二叉树,赫夫曼树 (Huffman Tree),路径长度 PL (Path Length) 两个结点之间的路径长度，是连接两结点的路径上的分支数。 树的外部路径长度EPL(External ) 各叶结点(外结点)到根结点的路径长度之和 树的内部路径长度IPL(Internal ) 各分支结点(

23、内结点)到根结点的路径长度之和 树的路径长度 PL = EPL + IPL,带权路径长度WPL (Weighted Path Length) 二叉树的带权 (外部) 路径长度是树的各叶结点所带的权值 wi 与该结点到根的路径长度 li 的乘积的和。,赫夫曼树 带权路径长度达到最小的二叉树即为赫夫曼树（最优二叉树）。 在赫夫曼树中，权值越大的结点离根越近。 赫夫曼算法(构造赫夫曼树) (1) 由给定的 n 个权值 w0, w1, w2, , wn-1，构造具有 n 棵扩充二叉树的森林 F = T0, T1, T2, , Tn-1 ，其中每棵扩充二叉树 Ti只有一 个带权值 wi 的根结点, 其左

24、、右子树均为空。,(2) 重复以下步骤, 直到 F 中仅剩下一棵树为止： 在 F 中选取两棵根结点的权值最小的扩充二叉树, 作为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 在 F 中删去这两棵二叉树。 把新的二叉树加入 F。,例：赫夫曼树的构造过程,上例存储结构,赫夫曼树的定义 const int n = 20; /叶结点数 const int m = 2*n -1; /结点数 typedef struct float weight; int parent, leftChild, rightChild; HTNode; typedef HTNod

25、e HuffmanTreem;,建立赫夫曼树的算法 void CreateHuffmanTree(HuffmanTree T, float fr ) for ( int i=0; i n; i+ ) Ti.weight = fri; for ( i=0; i m; i+ ) Ti.parent = -1; Ti.leftChild = -1; Ti.rightChild = -1; for ( i = n; i m; i+ ) ,int min1 = min2 = MaxNum; int pos1, pos2; for ( int j = 0; j i; j+ ) if ( Tj.parent

26、 = -1 ) if ( Tj.weight min1 ) pos2 = pos1; min2 = min1; pos1 = j; min1 = Tj.weight; else if ( Tj.weight min2 ) pos2 = j; min2 = Tj.weight; Ti.leftChild = pos1; Ti.rightChild = pos2; Ti.weight = Tpos1.weight + Tpos2.weight; Tpos1.parent = Tpos2.parent = i; ,赫夫曼树的应用,最佳判定树,考试成绩分布表,WPL = 0.10*1+0.15*2 +

27、0.25*3+0.35*4+0.15*4 = 3.15,WPL = 0.10*3+0.15*3+0.25*2+0.35*2+0.15*2 = 0.3+0.45+0.5+0.7+0.3 = 2.25,赫夫曼编码 主要用途是实现数据压缩，便于传送/存储 设给出一段报文： CAST CAST SAT AT A TASA 字符集合是 C, A, S, T ，各个字符出现的频度(次数)是 W 2, 7, 4, 5 。 若给每个字符以等长编码 A : 00 T : 10 C : 01 S : 11 则总编码长度为 ( 2+7+4+5 ) * 2 = 36,若按各个字符出现的概率不同而给予不等长编码，可望减

28、少总编码长度 各字符出现概率为 C:2/18, A:7/18, S:4/18, T:5/18 ,化整为 2, 7, 4, 5 。以它们为各叶结点上的权值, 建立赫夫曼树。左分支赋 0，右分支赋 1，得赫夫曼编码(变长编码)。,CAST CAST SAT AT A TASA A : 0 T : 10 C : 110 S : 111 总编码长度： 7*1+5*2+( 2+4 )*3 = 35 比等长编码的情形要短 总编码长度正好等于赫夫曼树的带权路径长度WPL,赫夫曼编码是一种前缀编码(都由叶结点组成,路径不会重复)。解码时不会混淆。 赫夫曼编码: A : 0 T : 10 C : 110 S : 111 11001111011001111011101001001001110 等长编码: A : 00 T : 10 C : 01 S : 11 010011100100111011001000100010001100,作业p194,1. 3. 4. 5. 6. 8. 9. 实习题 2.,