第六章树和二叉树

《第六章树和二叉树》由会员分享，可在线阅读，更多相关《第六章树和二叉树（73页珍藏版）》请在金锄头文库上搜索。

1、第六章第六章 树和二叉树树和二叉树 本章内容本章内容p树、二叉树的定义、性质和存储结构；p二叉树的遍历和线索化以及遍历算法的各种描述形式；p树遍历；p二叉树的多种应用。 本章要点本章要点p熟练掌握二叉树的结构特性；p熟悉二叉树的各种存储结构的特点及适用范围；p熟练掌握二叉树各种遍历策略的递归和非递归算法，了解遍历过程中“栈”的作用和状态，而且能灵活运用遍历算法实现二叉树的其它操作；p理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系；p熟悉树的各种存储结构及其特点；p学会编写实现树的各种操作的算法；p了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。6.1 树的定义和

2、基本术语树的定义和基本术语树的定义树的定义p树是一类重要的非线性数据结构，是以分支关系定义的层次结构；p树是n(n0)个结点的有限集，非空树满足：n有且仅有一个特定的称之为有且仅有一个特定的称之为根根(root)的结点；的结点；n除根以外的其余结点可分为除根以外的其余结点可分为m(0 mn)个互不相交的个互不相交的子集子集T1,T2,T3Tm，其中每个子集本身又是一棵树，其中每个子集本身又是一棵树，且且称为根的称为根的子树子树。树的表示方法树的表示方法p特点：除根结点外，每个结点都仅有一个前趋(父)结点。p其它表示方法：n嵌套集合表示法嵌套集合表示法n凹入表表示法凹入表表示法参见教材参见教材1

3、20页页AB C DE F G H IJ1层2层3层4层树的一些基本术语树的一些基本术语p结点的度（结点的度（degree）n结点所拥有的子树的数目。结点所拥有的子树的数目。p叶子结点（叶子结点（leaf-又称终端结点又称终端结点 terminal node）n度为零的结点。度为零的结点。p分支结点（分支结点（branch node）n度不为零的结点度不为零的结点p孩子（孩子（ child）n结点的子树的根称为结点的孩子。结点的子树的根称为结点的孩子。树的一些基本术语树的一些基本术语(续续)p双亲（双亲（ parent）n结点是其孩子的双亲。结点是其孩子的双亲。p祖先（祖先（ forefath

4、er）n从树根到双亲的所有结点称为该结点的祖先。从树根到双亲的所有结点称为该结点的祖先。p子孙（子孙（progeny）n以结点为根的子树的所有结点称为该结点的子孙。以结点为根的子树的所有结点称为该结点的子孙。p兄弟（兄弟（sibling）n同一父母的所有孩子互称兄弟。同一父母的所有孩子互称兄弟。p层次（层次（level）n树根为第一层，其孩子为第二层，孙子为第三层，以树根为第一层，其孩子为第二层，孙子为第三层，以此类推。此类推。树的一些基本术语树的一些基本术语(续续)p堂兄弟（堂兄弟（cousin）n双亲在同一层的结点互称堂兄弟。双亲在同一层的结点互称堂兄弟。p深度（深度（depth）n树中结

5、点的最大层次称为树的深度。树中结点的最大层次称为树的深度。p有序树（有序树（ordered tree）n结点各子树从左至右是有秩序的树称为有序树。结点各子树从左至右是有秩序的树称为有序树。p无序树（无序树（unordered tree）n结点各子树没有秩序的树称为无序树。结点各子树没有秩序的树称为无序树。p森林（森林（forest ）n森林是森林是 m (m0) 棵互不相交的树的集合。棵互不相交的树的集合。树的基本操作树的基本操作p初始化操作InitTree(&T)p求根函数 Root(T)p求双亲函数 Parent(T,cur_e)p求左孩子结点函数LeftChild(T,cur_e)p建树

6、函数CreateTree(&T,definiton)p清空树函数ClearTree(&T)p插入子树函数InsertChild(&T,&p,i,c)p删除子树函数DeleteChild(&T,&p,i)p遍历函数TraverseTree(T,visit()p求右兄弟函数RightSibling(T,cur_e)6.2 二叉树二叉树二叉树的定义二叉树的定义p定义n二叉树是二叉树是n(n 0)个结点的有限集合，它或为空个结点的有限集合，它或为空树树(n=0)，或由一个根结点和两棵互不相交的左，或由一个根结点和两棵互不相交的左子树和右子树的二叉树组成。子树和右子树的二叉树组成。p二叉树的特点：n定义

7、是递归的；定义是递归的；n0 结点的度结点的度 2；n是有序树。是有序树。二叉树（续）二叉树（续）p二叉树的五种基本形态p两种特殊的二叉树n满二叉树：每一层上的结点数都是最大结点数。满二叉树：每一层上的结点数都是最大结点数。n完全二叉树：只有最下面两层结点的度可小于完全二叉树：只有最下面两层结点的度可小于2，而最，而最下一层的叶结点集中在左边若干位置上。下一层的叶结点集中在左边若干位置上。12 34 5 6 712 34 5 6 78 9 10二叉树的性质二叉树的性质p性质1n二叉树的第二叉树的第i层上至多有层上至多有2i-1(i 1)个结点。个结点。p性质2n深度为深度为k的二叉树至多有的二

8、叉树至多有2k-1个结点个结点(k 1)。p性质3n对任何一棵二叉树对任何一棵二叉树T，如果其终端结点数为，如果其终端结点数为n0，度为，度为2的的结点数为结点数为n2 ，则，则n0 = n2 + 1。p性质4n具有具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为 log2n +1。二叉树的性质（续）二叉树的性质（续）p性质5n对一棵具有对一棵具有n个结点的完全二叉树个结点的完全二叉树(其深度为其深度为 log2n +1)，对其结点按层从上至下，对其结点按层从上至下(每层从左至右每层从左至右)进行进行0至至n-1的的编号，则对任一结点编号，则对任一结点i(0 i0，则i的双亲是(i-

9、1)/2。p若2i+1n，则i有左孩子，左孩子是2i+1。p若2(i+1)lchild); Preorder(t-rchild); void Inorder(BiTree t) if (t) Inorder(t-lchild); visit(t); Inorder(t-rchild); void Postorder(BiTree t) if (t) Postorder(t-lchild); Postorder(t -rchild); visit( t ); 遍历二叉树的递归算法遍历二叉树的递归算法p利用遍历结果确定二叉树问题n先序序列先序序列+中序序列中序序列n中序序列中序序列+后序序列后序序

10、列n先序序列先序序列+后序序列后序序列 (x) 先序序列: ABCDEFGH 中序序列: BDCEAFHGABFCGDEH思考：层序+先序/中序/后序， 能否确定？如何做？利用遍历结果确定二叉树问题利用遍历结果确定二叉树问题例如：层序ABCDEFGHIJ,中序DBGEHJACIF 根据先序中序求后序的算法根据先序中序求后序的算法void get_post(char *pre, char *in, char *post, int n)if ( n = 0) return;for (k = 0; k n; k+) if (ink = pre0) break;if (! k rchild); pus

11、h(p-lchild); 先序遍历的非递归算法先序遍历的非递归算法(2)非递归算法,考虑取消多余的空指针入栈,空指针个数可观，为n+1个init_stack();p = t;push(NULL); while (p) visit(p); if (p-rchild) push(p-rchild); if (p-lchild) p = p-lchild; else p = pop();init_stack();p = t;while (!stack_empty() | p) visit(p); if (p-rchild) push(p-rchild); if (p-lchild) p = p-lc

12、hild; else p = pop();后序遍历的非递归算法后序遍历的非递归算法后序遍历的非递归算法后序遍历的非递归算法(1)p非递归算法 init_stack();push(root,0);while(!stack_empty() p = pop(&state); if (p = NULL) continue; if (state = 0) push(p, 1); push(p-lchild, 0); else if (state = 1) push(p, 2); push(p-rchild, 0); else visit(p); 后序遍历的非递归算法后序遍历的非递归算法(2)p非递归算法

13、 init_stack();push(root, 0);while(!stack_empty() p = pop(&state); if (p = NULL) continue; if (state = 0) push(p, 2); push(p-rchild, 0); push(p-lchild, 0); else visit(p); 中序遍历的非递归算法中序遍历的非递归算法中序遍历的非递归算法中序遍历的非递归算法(1)p朴素的算法 init_stack();push(root, 0);while(!stack_empty() p = pop(&state); if (p = NULL) c

14、ontinue; if (state = 0) push(p, 1); push(p-lchild, 0); else if (state = 1) visit(p); push(p-rchild, 0); p效率问题效率问题 新压入堆栈的新压入堆栈的state0节点马上弹出然后再次压入作为节点马上弹出然后再次压入作为state1节点节点中序遍历的非递归算法中序遍历的非递归算法(2) init_stack(); p = root; while (p) push(p); p = p-lchild; while(!stack_empty() p = pop(); visit(p); p = p-r

15、child; while (p) push(p); p = p-lchild; init_stack(); p = root; while (p | !stack_empty() if (p) push(p); p = p-lchild; else p = pop(); visit(p); p = p-rchild; 二叉树遍历的应用二叉树遍历的应用二叉树遍历的应用二叉树遍历的应用p在二叉树中查找结点值为x的结点p求二叉树中每个结点所处的层次p求二叉树的高度p复制一棵二叉树6.4 树和森林树和森林树的存储结构树的存储结构:双亲表示法双亲表示法A B C D E F G 0 01033 1 2

16、3 4 5 6ABCEFGD 存储方法：使用顺序结构存储方法：使用顺序结构#define MAX_TREE_SIZE 100typedef struct PTNode TElemType data; int parent; PTNode; /* 节点的存储结构节点的存储结构*/typedef struct /* 顺序存储结构顺序存储结构 */ PTNode nodesMAX_TREE_SIZE; int r, n; /* 根位置和节点数根位置和节点数*/ PTree;优点：简单，紧凑，易于寻找双亲节点优点：简单，紧凑，易于寻找双亲节点缺点：查询某节点的孩子效率低缺点：查询某节点的孩子效率低树的

17、存储结构树的存储结构:孩子表示法孩子表示法 方法一 struct PTNode TElemType data; struct PTNode *childNUM_CHILD; ; 缺点：NUM_CHILD值不容易确定; 空域数目太多方法二： 改进方法1，记录节点的度，分配合适大小的内存方法三： 使用链表勾链，链表的每个节点记录一个孩子指针优缺点比较和其他存储方案 选用的实际存储结构该考虑到可能需要操作（增加，删除，检索）树的存储结构树的存储结构:孩子表示法孩子表示法(方法方法3) ABCEFGDABCDEFG1234650123456 树的存储结构树的存储结构:孩子表示法孩子表示法(方法方法2)

18、 #define MAX_TREE_SIZE 100struct TNode TElemType data; int degree; int child1;struct PTree struct TNode *nodeMAX_TREE_SIZE; int n; PTree;struct TNode *create_tnode(void) struct TNode *p; int k, degree; scanf(“%d”, °ree); p = malloc(sizeof(struct TNode)+(degree-1)* sizeof(int); P-degree = degree;

19、for (k = 0; k childk); input_node_data(p); return(p);树的存储结构树的存储结构(孩子兄弟表示法孩子兄弟表示法)p孩子兄弟表示法ABCDEFGABCEFGD森林与二叉树的转换森林与二叉树的转换p转换原则n按孩子兄弟表示法进行转换。按孩子兄弟表示法进行转换。p树与二叉树的转换DE森林与二叉树的转换森林与二叉树的转换树和森林的遍历树和森林的遍历p树的遍历ABCDE F GABECDFGn先序遍历先序遍历p先访问树的根结点，然后依次先根遍历根的每棵子树； ABEFCDG(二叉树先序)n后序遍历后序遍历p先依次后根遍历根的每棵子树，然后访问树的根结点

20、EFBCGDA(二叉树中序)森林的遍历森林的遍历p先序遍历：n访问森林中第一棵树的根结点；n先序遍历第一棵树中根结点的子树森林；n先序遍历除第一棵树外剩余的树构成的森林；举例：A B C D E F G H I Jp中序遍历n中序遍历森林中第一棵树的根结点的子树森林；n访问第一棵树的根结点；n中序遍历除第一棵树外剩余的树构成的森林举例：B C D A F E H J I G6.5 树的等价问题树的等价问题集合的查找与合并集合的查找与合并p集合的运算nfind(x) 判断元素判断元素x属于哪个集合属于哪个集合nMerge(Si, Sj) 将集合将集合Si和和Sj合并合并p集合的数据结构有多种实现

21、方法n位图法位图法 O(1)n有序表方法有序表方法 O(n)n树型结构表示集合树型结构表示集合p采用的结构取决于集合大小和所进行的操作树的存储结构树的存储结构:双亲表示法双亲表示法A B C D E F G 0 01033 1 2 3 4 5 6ABCEFGD 存储方法：使用顺序结构存储方法：使用顺序结构#define MAX_TREE_SIZE 100typedef struct PTNode TElemType data; int parent; PTNode; /* 节点的存储结构节点的存储结构*/typedef struct /* 顺序存储结构顺序存储结构 */ PTNode node

22、sMAX_TREE_SIZE; int r, n; /* 根位置和节点数根位置和节点数*/ PTree;优点：简单，紧凑，易于寻找双亲节点优点：简单，紧凑，易于寻找双亲节点缺点：查询某节点的孩子效率低缺点：查询某节点的孩子效率低树型结构表示集合树型结构表示集合p采用双亲表示法，存储一个森林type PTree MFSet; int find_mfset(MFSet S, int i) if (i = S.n) return -1; for (j = i; S.nodesj.parent = 0; j = S.nodesj.parent); return j;Status merge_mfset

23、(MFSet S, int i, int j) if (i = S.n | j = S.n) return ERROR; S.nodei.parent = j; return OK;算法分析和改进算法分析和改进p分析算法的效率n合并合并O(1),检索检索O(d)，nd为深度，最糟糕情况下，为深度，最糟糕情况下，d = np改进思路n合并时，将数量少的集合，合并到数量多的集合中合并时，将数量少的集合，合并到数量多的集合中n根的根的parent记录集合中节点个数，为区别于正常记录集合中节点个数，为区别于正常parent值，用负数值，用负数p改进后的分析n合并合并O(1)，树深度低于，树深度低于lo

24、g2n改进后的合并算法改进后的合并算法void mix_mfset(MFSet S, int i, int j) if (S.nodesi.parent S.nodesj.parent) /* i中节点少 */ swap(i, j); /* i中节点多 */ S.nodesi.parent += s.nodesj.parent; S.j.parent = i;改进后的检索算法改进后的检索算法int fix_mfset(MFSet S, int i) for(j=i; S.nodesj.parent=0; j=S.nodesj.parent); for (k = i; k != j; k = t

25、) t = S.nodesk.parent; S.nodesk.parent = j; return j;改进思路： 检索时压缩路径6.6 赫夫曼树及其应用赫夫曼树及其应用赫夫曼树及其应用赫夫曼树及其应用p赫夫曼树n最优树，是一类带权路径长度最短的树；n路径长度p指树中两个结点间路径上所含有的分支数目。n树的路径长度p指从树根到每一结点的路径长度之和。n带权路径长度p指结点的路径长度与该结点的权之积。赫夫曼树赫夫曼树p树的带权路径长度n树中所有叶子结点的带权路径长度；树中所有叶子结点的带权路径长度；p最优二叉树或赫夫曼树nWPL 最小的二叉树最小的二叉树赫夫曼树的特点赫夫曼树的特点p赫夫曼树中

26、除叶子结点外，所有分支结点的度均为2；p叶子结点（外部结点）可看成是由分支结点（内部结点）组成的树扩充出来的（扩充二叉树）赫夫曼树的构造赫夫曼树的构造1.根据给定的n个权值w1,w2,.wn构成n棵二叉树的集合F=T1,T2,.,Tn，其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树均空；2.在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。3.在F中删除这两棵树，同时将新得到的二叉树加入F中；4.重复2和3，直到F中只含一棵树为止；5.这棵树就是赫夫曼树； 例例例例 w=5, 29, 7, 8, 14,

27、23, 3, 11w=5, 29, 7, 8, 14, 23, 3, 1151429 7823 3111429 7823 1135887151429233581111358191429238715113581929 23148715292914871529113581923421135819234229148715295811358192342291487152958100赫夫曼树构造举例赫夫曼树构造举例1赫夫曼编码的赫夫曼编码的存储结构和构造算法存储结构和构造算法p初始有n个叶子结点(0n-1号)，构造出的哈夫曼树有2n-1个结点p用大小m=2n-1的向量存储哈夫曼树（顺序存储） struc

28、t HTNode int weight; int parent, lchild, rchild; *ht;m = 2 * n - 1;ht = malloc(m*sizeof(struct HTNode);for (p=&ht0; p parent = -1;输入ht前n个元素的weight;for (i = n; i m; i+) 在ht的前i个节点中寻找parent为-1且weight最小的两个节点s1,s2 hts1.parent = hts2.parent = i; hti.lchild = s1; hti.rchild = s2; hti.weight = hts1.weight +

29、 hts2.weight;例：例：已知字符 A，B，C，D，E，F，G，使用频度分别为：0.25，0.1，0.15，0.06 ， 0.3 ，0.05，0.09，试以此构造霍夫曼树。GB0.19A0.44FD0.11C0.26E0.5611) 0.25 0.1 0.15 0.06 0.3 0.05 0.092) 0.25 0.1 0.15 0.3 0.09 0.11 3) 0.25 0.15 0.3 0.11 0.19 4) 0.25 0.3 0.19 0.265) 0.3 0.26 0.446) 0.44 0.567) 1.00赫夫曼树构造举例赫夫曼树构造举例11、最佳判定树；2、霍夫曼编码：

30、GBAFDCE000000111111A: 01B: 001C: 101D: 1001E: 11F: 1000G: 000E: 100A: 000B: 001C: 010D: 011F: 101G: 110000000111111GBAFDCE0霍夫曼编码霍夫曼编码霍夫曼编码霍夫曼编码等长编码等长编码等长编码等长编码WPL霍夫曼编码 = 2.56WPL等长编码 = 3 利用霍夫曼编码可提高效率：( 3 - 2.56 ) / 3 15%霍夫曼树的应用霍夫曼树的应用赫夫曼编码赫夫曼编码p主数据结构：构造哈夫曼编码表，使用ht的parent域p辅助数据结构：char cdN;char *get_co

31、de(int i) / 求i号符号的编码串 cdN - 1 = 0; start = N - 1; for (c = i, f = htc.parent; f != -1; c = f, f = htf.parent) cd-start = htf.lchild = c ? 0 : 1; return &cdstart;p解码程序比较简单，从树根出发按1或0分别走向右或左孩子，直到叶子节点，解出编码的符号赫夫曼解码赫夫曼解码decode() / 求i号符号的编码串 k = 2 * n - 2；/* 树根节点 */ for(j = 0; j rcv_buf_len; j+) k = rcvbuf

32、j = 0 ? htk.lchild : htk.rchild; if (k n) out_code(k); /* 解出第k号符号 */ k = 2 * n 2; p解码程序:从树根出发按1或0分别走向右或左孩子，直到叶子节点，解出编码的符号赫夫曼编码的特点赫夫曼编码的特点n赫夫曼编码是不等长编码；赫夫曼编码是不等长编码；n赫夫曼编码是前缀编码，即任一字符的编码都不是另一字赫夫曼编码是前缀编码，即任一字符的编码都不是另一字符编码的前缀；符编码的前缀；n赫夫曼编码树中没有度为赫夫曼编码树中没有度为1的结点。若叶子结点的个数为的结点。若叶子结点的个数为n，则赫夫曼编码树的结点总数为，则赫夫曼编码树

33、的结点总数为 2n-1；n发送过程：根据由赫夫曼树得到的编码表送出字符数据；发送过程：根据由赫夫曼树得到的编码表送出字符数据；n接收过程：按左接收过程：按左0、右、右1的规定，从根结点走到一个叶结的规定，从根结点走到一个叶结点，完成一个字符的译码。反复此过程，直到接收数据结点，完成一个字符的译码。反复此过程，直到接收数据结束；束；作业和上机作业作业和上机作业作业作业1.试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。2.一棵含有n个结点的k叉树，何种形态达到最大深度？何种形态达到最小深度？ 3.假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画

34、出该树。作业（续）作业（续）4.假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10。试为这8个字母设计哈夫曼编码。5.画出下列森林对应的二叉树。12 3 4 5 6 78910111213 14作业（续）作业（续）6.画出和下列二叉树相应的森林 (1) (2) (3) (4) (5)7.画出和下列已知序列对应的森林F： 森林的先序次序访问序列为：ABCDEFGHIJKL 森林的中序次序访问序列为：CBEFDGAJIKLHAA A A AB B B C B CC C D作业（续）作业（续）8

35、. 一棵完全 k 叉树按层次顺序从 1 开始对全部结点编号，若所求结点存在，则： 编号为 n 的结点的父结点的编号是多少？ 结点 n 的第 i 个儿子的编号是多少？ 结点 n 有右兄弟的条件是什么？9. 设计算法将二叉树中所有节点的左右孩子互换。10. 设计算法拷贝二叉树。11. 设计算法判断一个二叉树是否是完全二叉树。二叉树上机作业二叉树上机作业(1) 建立二叉树:两种方法 用先序递归过程建立二叉树 (存储结构：二叉链表) 输入数据按前序遍历所得序列输入，当某结点左子树或右子树为空时，输入*号，如输入abc*d*e*得到的二叉树为：ab ec d 由二叉树的层次序列和中序序列建立一棵二叉树。 对上例：输入abecd和cbdae两个字符串(2) 编写递归算法，先序，后序和后序输出二叉树(3) 计算二叉树中叶子结点的数目，和每个节点的深度。(4) 按凹入表方式输出该二叉树。(5) 按层次遍历的方法输出该二叉树，求出每层的结点个数。测试实例测试实例AB CD EF应当设计多个测试实例，检验程序的正确性。下边是一个例子。