数据结构学习考 复习课(2) 主要内容： 第三部分：树、二叉树、森林

第六章 树和二叉树 考核内容及要求： 熟练掌握树的基本概念； 熟练掌握二叉树的概念、性质 熟练掌握二叉树的遍历方法，各种线索树、树与二叉树的转换、最优二叉树及HUFFUMAN编码； 掌握各种树操作特性、性质、实现方法

1 树的基本概念、性质 树：n个结点的有限集； 在非空树中： A B C D E F G H I J K L M 有且仅有一个根结点（Root）; 当n>1时，其余结点可以分为m个(m>0)互不相交的有限集T1,T2,···,Tm,其中Ti为根的子树 A B C D E F G H I J K L M

A B C D E F G H I J K L M 树结构中的基本术语 结点：一个数据元素及指向其子树的分支 树的度：树内各结点的度的最大值 结点的度：结点拥有的子树数 叶子结点：度为0 的结点 分支结点：度不为0的结点 树的度：树内各结点的度的最大值 孩子：结点的子树的根 父亲(双亲)： 兄弟：同一父亲的孩子 祖先：从根到该结点所经分支上的所有结点 子孙：以某结点为根的子树中的任一结点 层次：根为第一层，根的孩子为第二层··· 堂兄弟：双亲在同一层的结点互为堂兄弟 深度：树中结点的最大层次 有序树：将树的结点的各个子树都看成是有序的，则 无序树 森林 A B C D E F G H I J K L M

2 二叉树的概念、性质 二叉树的定义 每个结点至多有两棵子树(即度<=2),子树有左右之分。 二叉树的五种基本形态 左子树为空的二叉树 空二叉树 仅有根结点的二叉树 左、右子树都不空的二叉树 右子树为空的二叉树

二叉树的性质 证明：归纳法 i=1时，命题显然成立，2i-1=20=1 假设所有的1≤j<i都成立，那么证明当j=i时命题也成立： 性质1 在二叉树的第i层上至多有2i-1个结点（i≥1） 证明：归纳法 i=1时，命题显然成立，2i-1=20=1 假设所有的1≤j<i都成立，那么证明当j=i时命题也成立： 由假设知，第i-1层上的结点个数为2i-2,而在二叉树中第i层上结点的个数最多是上一层结点数的2倍，即为 2×2i-2=2i-1

性质2 深度为k的二叉树至多有2k-1个结点，（k≥1） 证明：利用性质1 的结论

性质3 对任何一棵二叉树T，如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1 分析二叉树种的分叉数B： n=B+1 B=n1+2n2 所以有n=n1+2n2+1 故：n0=n2+1

满二叉树：一棵深度为k且有2k-1个结点的二叉树 完全二叉树：深度为k有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，成为完全二叉树。 性质4 具有n个结点的完全二叉树的深度为 log2n ＋1

1 2 3 4 5 6 7 12 11 10 9 8 14 13 15 1 2 3 4 5 6 7 12 11 10 9 8 完全二叉树 满二叉树 1 2 3 5 7 6 1 2 3 5 6 4 非完全二叉树

性质5 如果对一棵有n个结点的完全二叉树（其深度为 层， 每层从左到右），则对任一结点i(1≤i≤n),有： (1) 如果i＝1，则结点i是二叉树的根，无双亲；若i>1,则其双亲parent(i)是结点 (2) 如果2i>n,则结点i无左孩子(结点i为叶子结点)；否则其左孩子LCHILD(i)是结点2i. (3) 如果2i+1>n,则结点i无右孩子；否则其右孩子RCHILD(i)是结点2i+1. log2n ＋1 i/2 i/2 i i+1 2i+1 2i+3 2i 2i+2

3 二叉树的存储结构 顺序存储结构 #define MAX_TREE_SIZE 100; Typedef TElem Type SqBiTree[MAX_TREE_SIZE ]； SqBiTree bt; 将完全二叉树上编号为i的结点元素存储在一维数组的下标为i-1的分量中。

链式存储结构 ——二叉链表 在含有n个结点的二叉链表中有n+1个空链域 Data LCHILD RCHILD PARENT Data

二叉链表的定义 Typedef struct BiTNode{ TElemType data; struct BiTNode *lchild, *rchild; }BiTNode, *BiTree; 二叉树的基本操作： CreatBiTree(BiTree &T);//按先序顺序构造一棵二叉树 PreOrderTraverse(BiTree T)；//先序遍历二叉树 InOrderTraverse(BiTree T)；//中序遍历二叉树 PostOrderTraverse(BiTree T)；//后序遍历二叉树 LevelOrderTraverse(BiTree T)；//层次遍历二叉树

4 遍历二叉树和线索二叉树 遍历二叉树 先序（根）遍历 后序（根）遍历 中序（根）遍历 （1）访问根结点 （2）先序遍历左子树 （3）先序遍历右子树 先序（根）遍历 （1）后序遍历左子树 （2）后序遍历右子树 （3）访问根结点 后序（根）遍历 （1）中序遍历左子树 （2）访问根结点 （3）中序遍历右子树 中序（根）遍历

例:表达式(a+b*(c-d)-e/f)的二叉树 － ＋ / a × f e b c d 先序遍历二叉树： -+a*b-cd/ef 中序遍历二叉树： a+b*c-d-e/f 后序遍历二叉树： abcd-×＋ef/-

遍历二叉树的过程 － － ＋ / a b － － － ＋ / a × ＋ + ＋ / ＋ / b a b a a b

线索二叉树 非线性结构的线性化操作 增加两个指针：分别指向结点的前驱和后继 利用二叉链表的n+1个空链域 线索链表 线索二叉树 lchild rchild LTag RTag data 线索链表 线索二叉树 LTag= 0 lchild指示左孩子 1 lchild指示结点的前驱 RTag= 0 rchild指示右孩子 1 rchild指示结点的后继

中序线索链表 1 thrt bt － / ＋ 1 a * 1 e 1 f 1 b － 1 － 1 －

在中序线索二叉树中找结点的后继 中序线索二叉树中找结点的前驱： a × f e b c d 中序线索二叉树 叶子结点的后继：右链域指示 非终端结点：其右子树的第一个结点 中序线索二叉树中找结点的前驱： 左标志域为1：左链域指示 左标志域为0：左子树的最后一个结点。 － ＋ / a × f e b c d NIL NIL 中序线索二叉树

typedef enum PointerTag{Link,Thread}; //Link==0:指针;Thread==1:线索 线索链表的存储结构 typedef enum PointerTag{Link,Thread}; //Link==0:指针;Thread==1:线索 typedef struct BiThrNode{ TElemType data; struct BiThrNOde *lchild,*rchild;//左右孩子指针 PointerTag LTag,RTag;//左右标志 }//BiThrNode, *BiThrTree; 双向线索链表： 添加头结点：lchild域指向二叉树的根结点； rchild域指向中序遍历时访问的最后结点

5 树和森林 树的存储结构： 双亲表示法：除根结点外的每个结点都只有唯一的双亲 R D C F H G K A B E 数组下标 R A B －1 3 1 6 数组下标 2 4 5 7 8 9 R A B C D E F G H K

树的双亲表存储表示 #define MAX_TREE_SIZE 100; Typedef struct PTNode{ TElemType data; int patent; }//PTNode; Typedef struct{ PTNode nodes[MAX_TREE_SIZE]; int r,n; }//PTree; 优点：parent(T,x),Root(x)操作容易实现 确定：求结点的孩子时需要遍历整个结构

孩子表示法： D为树的度，结点同构，空间浪费 结点不同构，空间不浪费，操作不方便 R D C F H G K A B E data child1 child2 child3 childd ······ 结点不同构，空间不浪费，操作不方便 data degree child1 child2 childd ······ R D C F H G K A B E 1 2 3 4 5 6 7 8 9 ^ 适用于涉及孩子的操作

树的孩子链表存储表示 Typedef struct CTNode{ //孩子结点 int child; struct CTNode *next; }*childptr; Typedef struct{ TElemType data; childptr firstchild; //孩子链表头指针 }CTBox; CTBox nodes[MAX_TREE_SIZE]; int n,r; //结点数和根的位置； }//CTree;

孩子表示法和双亲表示法结合起来，即带双亲的孩子链表 R D C F H G K A B E 4 －1 2 6 3 5 ^ 1 7 8 9 带双亲的孩子链表

孩子兄弟表示法：以二叉链表表示 Typedef struct CSNode{ ElemType data; 两个链域：firstchild和nextsibling：第一个孩子结点和下一个兄弟结点 R ^ A D B E C F G H K Typedef struct CSNode{ ElemType data; Struct CSNode *firstchild,*nextsibling; }CSNode,*CSTree;

任何一棵与树对应的二叉树，其右子树都为空 森林与二叉树的转换 A B C E D A B C E D ^ A B C D E 任何一棵与树对应的二叉树，其右子树都为空

森林与二叉树的对应关系 A B C D E F G I H J E F G I H J A B C D 森林与二叉树 树与二叉树对应 A B

树和森林的遍历 树的遍历： 森林的遍历： 先根遍历 后根遍历 先序遍历森林 中序遍历森林： （1）中序遍历森林中的第一颗树的根结点的子树森林； （2）访问第一颗树的根结点； （3）中序遍历剩余的树构成的森林。 E F G I H J A B C D

6 哈夫曼树及其应用 最优二叉树（哈夫曼树） 哈夫曼树：最优树，带权路径长度最短的树。 路径：从树中一个结点到另一个结点之间的分支构成两个结点之间的路径； 路径长度：路径上的分支数目； 树的路径长度：从树根到每一个结点的路径长度之和 树的带权路径长度： 其中：wk为k个结点的权值 最优二叉树(哈夫曼树)：带权路径长度WPL最小的二叉树

构造哈夫曼树的过程 a b c d a b c d c d a b c d b a 7 5 2 4 7 5 2 4 18 2 4 7 5 6 11 a 7

哈夫曼算法： (1)根据给定的n个权值{w1,w2,···,wn}构成n棵二叉树的集合F={T1,T2,···,Tn}，其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树均空。 (2)在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 (3)在F中删除这两棵树，同时将新得到的二叉树加入F中。 (4)重复(2)(3),直到F只含一棵树为止。这颗树就是哈夫曼树。 c d 2 4 a b 7 5 6 a b c d 7 5 2 4

哈夫曼编码 A B C D 哈夫曼树的特点： 没有度为1 的结点，称为严格的二叉树 编码 A(0) B(10) C(110) 1 哈夫曼树的特点： 没有度为1 的结点，称为严格的二叉树

例如： A B C D 哈夫曼树与哈夫曼编码的存储表示 Typedef struct{ unsigned int weight; unsigned int parent,lchild,rchild; }HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树 Typedef char *HuffmannCode;//动态分配哈夫曼编码表 例如： A B C D 1 1 2 3 4 5 6 7 7 5 6 2 4 3 11 17 1

构造哈夫曼树，求哈夫曼编码的算法 void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n){ //w存放n个字符的权值，构造哈夫曼树HT,求n个字符的哈夫曼编码表 if (n<=1) return; m=2*n-1; //n个字符的哈夫曼树有（2*n-1）个结点 HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); for (p=HT,i=1;i<=n;++i,++p,++w) *p={*w,0,0,0}; for (;i<=m;++i,++p) *p={0,0,0,0}; for (i=n+1;i<=m;++i){ //构造哈夫曼树 select (HT,i-1,s1,s2);//选择parent为0且权值最小的两个结点：s1,s2 HT[s1].parnet=i; HT[s2].parent=i; HT[i].child=s1;HT[i].rchild=s2; HT[i].weight=HT[s1].weight+ HT[s1].weight; }

//从叶子到根逆向求每个字符的哈夫曼编码 HC=(HuffmanCode)malloc((n+1)*sizeof(char *)); cd=(char*)malloc(n*sizeof(char)); cd[n-1]=“\0”； for(i=1;i<=n;++i){ start=n-1; for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) if (HT[f].lchild==c) cd[--start]=“0”; else cd[--start]=“1”; Hc[i]=(chat *)malloc((n-start)*sizeof(char)); atrcpy(HC[i],&cd[start]); } free(cd); }//HuffmanCoding 1 2 3 4 5 6 7 7 5 6 2 4 3 11 17 1

从根结点遍历哈夫曼树，求哈夫曼编码 A B C D 1 1 2 3 4 5 6 7 7 5 6 2 4 3 11 17 1

算法： HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); P=m; cdlen=0; For(i=1;i<=m;++i) HT[i].weight=0; While(p){ if(HT[p].weight==0){ HT[p].weight=1; if (HT[p].lchild!=0) {p=HT[p].lchild; cd[cdlen++]=“0”;} else if (HT[p].rchild==0){ HC[p]=(char *)malloc((cdlen+1)*sizeof(char)); cd[cdlen]=“\0”;atrcpy(HC[p],cd); } }else if (HT[p].weight==1{ HT[p].weight=2; if(HT[p].rchild!=0){p=HT[p].rchild; cd[cdlen++]=“1”;} }else {HT[p].weight=0;p=HT[p].parent;--cdlen;} }//while

典型例题 6.2 一个度为2的树与一棵二叉树有何区别？ 答：二叉树的度小于等于2，二叉树的子树有左右之分，而度为2的树的子树不一定是有序的。 6.7 一棵含有n个结点的k叉树，可能达到的最大深度和最小深度各是多少？ 答：最大n, 最小logkn+1

证明： 在含有n个结点的二叉链表中有n+1个空链域 证明: 除根结点均有分支引出,故有n-1个分支, 占用n-1个子域,n个结点共有2n个子域.故空域共2n-(n-1)=n+1个.

6.10 对于那些所有非叶子结点均有非空左右子树的二叉树： 有n个叶子结点的树中共有多少个结点？ 性质3 对任何一棵二叉树T，如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1

6.14 找出满足下列条件的二叉树 1）先序和中序遍历，得到的结点访问顺序一样。 2）后序和中序遍历，得到的结点访问顺序一样。 3）先序和后序遍历，得到的结点访问顺序一样。 答：1）无左子树 2）无右子树 3）仅一个结点

6.17 阅读下列算法，若有错，则改正。 BiTree InSucc(BiTree q){ //已知q是指向中序线索二叉树上某个结点的指针， r=q->rchild; if (!r->rtag) while (!r->rtag) r=r->rchild; return r; }//InSucc

6.19 分别画出和下列树对应的各个二叉树 6.22 对于下列树分别求出以下遍历序列： (1) 先根序列 (2)后根序列 A B C A A (1) 先根序列 (2)后根序列 A B C A A B C A B C D E F G H I J K

6.21 画出和下列二叉树对应的森林： A B C A B C A B C

6. 24 画出和下列已知序列对应的森林F: 森林的先序次序访问序列为：ABCDEFGHIJKL 森林的中序次序访问序列为：CBEFDGAJIKLH 原则：森林的先序/中序遍历，即对应二叉树的先序/中序 遍历 先做二叉树： a a b cbefdg jiklh h c efdg jikl

a 先ABCDEFGHIJKL 中CBEFDGAJIKLH b h c d i g j kl ef a 二叉树 b h c d i g j k e f l

森林 a h b d l g i k c e f j 6.23 画出和下列已知序列对应的树T 树的先根次序访问序列为：GFKDAIEBCHJ 树的后根次序访问序列为：DIAEKFCJHBG 思路：树的先根为二叉树的先序 树的后根为二叉树的中序 求出二叉树然后化为树

6.42 编写递归算法，计算二叉树中叶子结点的数目。 Status PreOrderTraverse(BiTree T, int s) { //s为叶子数目，初值为0 if (T) { if (!T->lchild) && (!T->rchild) s++; PreOrderTraverse(T->lchild, s); PreOrderTraverse(T->rchild, s); }//if return OK; }//PreOrderTraverse

6.47 编写按层次顺序（同一层自左至右）遍历二叉树的算法 Status LevelTraverse(BiTree T, status (*visit)(TElemType e) { InitQueue(Q); if (T) EnQueue(Q,T); while (!QueueEmpty(Q)) { DeQueue(Q,e); if (!visit(e->data)) return ERROR; if (e->lchild) EnQueue(Q,e->lchild); if (e->rchild) EnQueue(Q,e->rchild); } return OK; }//LevelTraverse

习题6.39 假设在二叉链表中增设两个域：双亲域指示双亲结点；标志域(mark取值0··2)以区分在遍历过程中到达该结点时应该向左、向右或访问该结点。试以此存储结构编写不用栈的后序遍历算法。 － ＋ / a × mark= 0 则访问左子树，同时mark变为1 1 则访问右子树，同时mark 变为2 2 访问根结点 data lchild parent rchild mark

Status exercise_6.39(BiTree T,){ //后序遍历二叉树，二叉树的结点有五个域：data,parent,lchild,rchild,mark;mark初始值为0 P=T; while (P){ swich (p->mark){ case 0: p->mark=1; if (p->lchild) p=p->lchild; break; case 1: p->mark=2; if (p->rchild) p=p->rchild; break; case 2: p->mark=0;visit(P); p=p->parent; break; default: ; }

6.62 对一个以孩子兄弟链表表示的树，计算它的深度 R ^ A D B E C F G H K

Typedef struct CSNode{ ElemType data; 队列中数据元素的类型定义 Typedef struct QNode{ QElemtype data; int lay; struct QNode *next; }Qnode,*QueuePtr; 链队列的存储 Typedef struct{ QueuePtr front; QueuePtr rear; } LinkQueue; Typedef struct CSNode{ ElemType data; Struct CSNode *firstchild,*nextsibling; }CSNode,*CSTree;

Status D_S_6.62(CSTree tr;int layer){ if tr=null return 0; IniQueue(Q) p=tr; InQueue(Q,p,1); layer=1; while (!EmptyQueue(Q)){ OutQueue(Q,r); if (!r->firstchild) {if r->lay>layer layer=r->lay;} if (r->firstchild) {k=r->lay+1;p=r->firstchild; while (p) {InQueue(Q,p,k); p=p->nextsibling;} } return layer;

6. 26 假设用于通信的电文仅由7个字母组成，字母在电文中出现的频率分别为0. 07,0. 19,0. 02,0. 06,0. 32, 0 6.26 假设用于通信的电文仅由7个字母组成，字母在电文中出现的频率分别为0.07,0.19,0.02,0.06,0.32, 0.21,0.10，试为这7个字母设计哈夫曼编码。使用0～7的二进制表示形式是另一种编码方案。比较两种方案的优缺点。 解题时注意哈夫曼树的最初存储结构和构造哈夫曼树的算法过程 树的带权路径长度WPL=SUM(权值×路径长度) 首先设7个字符的权分别为w={7, 19, 2, 6 ,32, 7， 21, 10} n=7,则m=13，即在有7个叶子结点的哈夫曼树上有13个结点 然后构造一棵哈夫曼树：

0.07,0.19,0.02,0.06,0.32, 0.21,0.10， 7 19 2 6 32 21 10 32 10 7 2 6 8 15 25 19 21 40 7 19 32 21 10 2 6 8 19 32 21 10 7 2 6 8 15 19 21 40 32 10 7 2 6 8 15 25 60 19 32 21 10 7 2 6 8 15 25

19 21 40 32 10 7 2 6 8 15 25 60 100 最后得出字母的编码分别为： （0.07,0.19,0.02,0.06,0.32, 0.21,0.10） 1110 11 11110 11111 10 110