第六章 树和二叉树 6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.6 赫夫曼树及其应用

6.1 树的定义和基本术语 树(Tree)是n（n≥0）个结点的有限集。当n=0时， 称为空树；当n>0时，该集合满足如下条件：  其中必有一个称为根（root）的特定结点，它没有直接前驱，但有零个或多个直接后继。  当n>1时，其余结点可以划分成m（m>0）个互不相交的有限集T1，T2，T3，…，Tm，其中Ti（1≤i ≤ m）又是一棵树，称为根的子树（SubTree）。

层次 1 2 3 4 A B C A D E F G H I (a) 只有根结点的树 (b) 一般的树 图6.1 树的图示方法

树的结点包含一个数据元素及若干指向其子树的分支。 结点的度：一个结点的子树个数称为此结点的度。  叶子或终端结点：度为0的结点，即无后继的结点。 分支结点或非终端结点：度不为0的结点。  孩子结点：一个结点的直接后继称为该结点的孩子结点。在图6.1(b)中， B、C是A的孩子。  双亲结点：一个结点的直接前驱称为该结点的双亲结点。在图6.1(b)中，A 是B、C的双亲。  兄弟结点：同一双亲结点的孩子结点之间互称兄弟结点。在图6.1(b)中，结点H、I互为兄弟结点。

祖先结点：一个结点的祖先结点是指从根结点到该结点的路径上的所有结点。在图6.1(b)中，结点H的祖先是A、B、E。 子孙结点：一个结点的直接后继和间接后继称为该结点的子孙结点。在图6.1(b)中，结点B的子孙是D、E 、F、 H、I。  树的度：树中所有结点的度的最大值。  结点的层次：从根结点开始定义，根结点的层次为1，根的直接后继的层次为2，依此类推(见图6.1(b))。  树的高度（深度）：树中所有结点的层次的最大值。  有序树：在树T中，如果各子树Ti之间是有先后次序的（即不能互换），则称为有序树。  森林：m（m≥0）棵互不相交的树的集合。将一棵非空树的根结点删去，树就变成一个森林；反之，给森林增加一个统一的根结点，森林就变成一棵树。

数据对象D：D是具有相同特性的数据元素的集合。 ADT Tree { 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R：若D为空集，则称为空树。若D中仅含有一个数据元素，则R为空集，否则R={H}，H是如下的二元关系： 在D中存在唯一的称为根的数据元素root，它在关系H下没有前驱。  除root以外，D中每个结点在关系H下都有且仅有一个前驱。

基本操作 P: InitTree(&T): 将T初始化为一棵空树。 DestoryTree (&T): 树T存在,销毁树T。  CreateTree (&T, definition): 按definition创建树T。 ClearTree(&T): 树T存在,将树T清为空树。 TreeEmpty(T): 树T存在,若T为空则返回TRUE，否则返回FALSE。 TreeDepth(T): 树T存在,返回T的深度。 Root(T): 树T存在,返回树T的根。

Value(T, cur_e): 树T存在，cur_e是T中某个结点，返回cur_e的值。 Assign(T, cur_e, value): 树T存在, cur_e是T中的某个 结点，结点cur_e赋值为value。 Parent(T, cur_e): 树T存在, cur_e是T中的某个结点。cur_e为非根结点，则返回它的双亲，否则函数值为“空” 。 LeftChild(T, cur_e): 树T存在，cur_e是T中的某个结点。若cur_e为非叶子结点，则返回它的最左孩子，否则返回“空”。 RightSibling(T, cur_e): 树T存在，cur_e是T中的某个结点。若cur_e有右兄弟，则返回它的右兄弟，否则函数值为“空”。 

InsertChild(&T, &p, i, c): 树T存在，p指向T中某个结点。非空树c与T不相交。插入c为T中p指向结点的第i棵子树。  DeleteChild(&T, &p, i): 树T存在，p指向T中某个结点， 1≤i≤p所指向结点的度。删除T中p所指向结点的第i棵子树。 TraverseTree(T，visit()): 树T存在，visit()是对结点进行访问的函数。按照某种次序对树T的每个结点调用visit()函数访问一次且最多一次。若visit()失败，则操作失败。 } ADT Tree

树的表示方法 树的表示形式有多种, 常见的几种方法是:  (1) 倒挂树法, 如图6.1所示。 (2) 文氏图法（集合包含关系）, 如图6.2(a)所示。  (3) 凹入表示法, 如图6.2(b)所示。  (4) 嵌套括号法，如(A(B(D,E(H,I),F),C(G)))。

第六章 树和二叉树 6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.6 赫夫曼树及其应用

6.2.1 二叉树的定义与基本操作 二叉树(Binary Tree)是另一种树型结构，其特点是： 每个结点的度都不大于2；  每个结点的孩子结点次序不能任意颠倒。  即一个二叉树中的每个结点只能含有0、 1或2个孩子，而且每个孩子有左右之分。我们把位于左边的孩子叫做左孩子，位于右边的孩子叫做右孩子。

二叉树的基本操作与树的基本操作类似（见p.121)，有关树的术语也都适用于二叉树。 A A A A B B B C (b) 根和空的左右子树 (c) 根和左子树 (a) 空二叉树 (d) 根和右子树 (e) 根和左右子树 图6.3 二叉树的5种基本形态 二叉树的基本操作与树的基本操作类似（见p.121)，有关树的术语也都适用于二叉树。

6.2.2 二叉树的性质 性质1: 在二叉树的第i层上至多有2i-1个结点(i≥1)。  证明：用数学归纳法。  6.2.2 二叉树的性质 性质1: 在二叉树的第i层上至多有2i-1个结点(i≥1)。  证明：用数学归纳法。  归纳基础：当i=1时，整个二叉树只有一根结点，此时2i-1=20=1，结论成立。 归纳假设：假设i=k时结论成立，即第k层上结点总数最多为2k-1个。  现证明当i=k+1时，结论成立:因为二叉树中每个结点的度最大为2，则第k+1层的结点总数最多为第k层上结点最大数的2倍，即2×2k-1=2(k+1)-1，故结论成立。

性质2: 深度为k的二叉树至多有2k-1个结点（k≥1）。 故结论成立。

性质3: 对任意一棵二叉树T，若终端结点数为n0，而其度数为2的结点数为n2，则n0=n2+1。 设二叉树中分支数目为B，因为除根结点外，每个结点均对应一个进入它的分支，所以有 n=B+1

又因为二叉树中的分支都是由度为1和度为2的结点发出， 所以分支数目为 B=n1+2n2 整理上述两式可得到 n=B+1=n1+2n2+1 将n=n0+n1+n2代入上式，得出n0+n1+n2=n1+2n2+1，整理后得n0=n2+1，故结论成立。

满二叉树： 深度为k且有2k-1个结点的二叉树。在满二叉树中，每层结点都是满的，即每层结点都具有最大结点数。图6.3(a)所示的二叉树，即为一棵满二叉树。 满二叉树的顺序表示，即从二叉树的根开始，层间从上到下，层内从左到右，逐层进行编号（1，2，…，n）。例如图6.3(a)所示的满二叉树的顺序表示为(1，2，3，4，5，6，7，8，9，10，11，12，13，14，15)。

完全二叉树： 深度为k，结点数为n的二叉树，如果其结点1至n的位置序号分别与深度为k的满二叉树的结点1至n的位置序号一一对应，则为完全二叉树， 如图6.3(b)所示。 满二叉树必为完全二叉树， 而完全二叉树不一定是满二叉树。

1 1 2 3 2 3 4 5 6 7 4 5 6 7 8 9 10 11 12 13 14 15 8 9 10 11 12 13 14 (a) 满二叉树 (b)完全二叉树 图6.4 满二叉树与完全二叉树

性质4：具有n个结点的完全二叉树的深度为 +1。 证明：假设n个结点的完全二叉树的深度为k，根据性质2可知，k-1层满二叉树的结点总数为 n1=2k-1-1 k层满二叉树的结点总数为 n2=2k-1 显然有n1<n≤n2，进一步可以推出n1+1≤n<n2+1(这里可以从k层完全二叉树结点总数n的特点来分析)。 将n1=2k-1-1和n2=2k-1代入上式，可得2k-1≤n<2k，即k-1≤log2n<k。因为k是整数，所以k-1= ，k= +1, 故结论成立。 

性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到第 +1层，每层从左到右),则对任一结点i（1≤i≤n),有： （1）如果i＝1，则结点i无双亲，是二叉树的根；如果i>1，则其双亲是结点 。 （2）如果n<2i，则结点i无左孩子；否则，其左孩子是结点2i。 （3）如果n<2i＋1，则结点i无右孩子；否则，其右孩子是结点2i＋1。

可以用归纳法证明其中的（2）和（3）：  归纳基础:当i=1时，由完全二叉树的定义知，如果n≥ 2×i=2，说明二叉树中存在两个或两个以上的结点，所以其左孩子存在且序号为2；反之，如果n < 2，说明二叉树中不存在序号为2的结点，其左孩子不存在。同理，如果n ≥ 2×i+1=3，说明其右孩子存在且序号为3；如果n < 3，则二叉树中不存在序号为3的结点，其右孩子不存在。  归纳假设:假设对于序号为j(1≤j≤i)的结点，当n≥ 2×j时，其左孩子存在且序号为2×j，当n < 2×j时，其左孩子不存在；当n≥ 2×j+1时，其右孩子存在且序号为2×j+1，当n < 2×j+1时，其右孩子不存在。

当i=j+1时，根据完全二叉树的定义，若其左孩子存在， 则其左孩子结点的序号一定等于序号为j的结点的右孩子的序号加1，即其左孩子结点的序号等于（2×j+1）+1=2（j+1）=2×i，且有n≥ 2×i；如果n < 2×i，则左孩子不存在。若右孩子结点存在，则其右孩子结点的序号应等于其左孩子结点的序号加1，即右孩子结点的序号为2×i+1，且有n≥ 2×i+1；如果n < 2×i+1，则右孩子不存在。  故（2）和（3）得证。

由（2）和（3）我们可以很容易证明（1）。  当i=1时，显然该结点为根结点，无双亲结点。当i>1时，设序号为i的结点的双亲结点的序号为m，如果序号为i的结点是其双亲结点的左孩子，根据（2）有i=2×m，即m=i/2; 如果序号为i的结点是其双亲结点的右孩子，根据（3）有i=2×m+1， 即m=（i-1）/2=i/2-1/2，综合这两种情况，可以得到，当i>1时，其双亲结点的序号等于 。证毕。

6.2.3 二叉树的存储结构 1.顺序存储结构 用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树的结点元素，即将完全二叉树上编号为i的结点存储在如下定义的一维数组中下标为i-1的分量中。 //--------------二叉树的顺序存储表示-------------// #define MAX_TREE_SIZE 100 typedef TElemType SqBiTree[MAX_TREE_SIZE]; SqBiTree bt;

H I J K L D E B A C F G (a) 完全二叉树 (b) 二叉树的顺序存储结构 图6.5 完全二叉树及其顺序存储结构

对于一般二叉树,则应将其每个结点与完全二叉树上的结点相对照,存储在一维数组的相应分量中。

A B C D (a) 单支二叉树 (b) 单支二叉树的顺序存储结构 图6.6 单支二叉树及其顺序存储结构 从树根起，自上层至下层，每层自左至右的给所有结点编号的缺点是有可能对存储空间造成极大的浪费。在最坏的情况下，一个深度为H且只有H个结点的右单支树却需要2H-1个结点存储空间。而且，若经常需要插入与删除树中结点时，顺序存储方式不是很好。

2. 链式存储结构 对于任意的二叉树来说，每个结点只有两个孩子结点和一个双亲结点。我们可以设计每个结点至少包括三个域：数据域、左孩子域和右孩子域： lchild data rchild 其中，lchild域指向该结点的左孩子，data域记录该结点的信息，rchild域指向该结点的右孩子。这样的结点结构所得的二叉树的存储结构称为二叉链表。

用C语言可以这样声明二叉树的二叉链表结点的结构： typedef struct BiTNode { TelemType data; struct BiTNode *lchild,*rchild; } BiTNode,*BiTree; 有时，为了便于找到双亲结点，可以增加一个parent域，parent域指向该结点的双亲结点，这种结点的结构(所得二叉树的存储结构称为三叉链表)如下： lchild data parent rchild

链表的头指针 B C D G E F A (a) 二叉树T (b) 二叉树T的二叉链表 图6.7 二叉树和二叉链表

容易证得，若一个二叉树含有n个结点，则它的二叉链表中必含有2n个指针域，其中必有n＋1个空的链域。 此结论证明如下：  证明：分支数目B=n-1，即非空的链域有n-1个，故空链域有2n-(n-1)=n+1个。  不同的存储结构实现二叉树的操作也不同。如要找某个结点的双亲结点，在三叉链表中很容易实现；在二叉链表中则需从根指针出发一一查找。可见，在具体应用中，需要根据二叉树的形态和需要进行的操作来决定二叉树的存储结构。

第六章 树和二叉树 6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.6 赫夫曼树及其应用

6.3.1 遍历二叉树 在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。这就引入了遍历二叉树的问题，即如何按某条搜索路径巡访树中的每一个结点，使得每一个结点均被访问一次，且仅被访问一次。 假如以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，且规定先左后右，遍历整个二叉树则有三种遍历方案，分别规定为： DLR——先（根）序遍历， LDR——中（根）序遍历， LRD——后（根）序遍历。

1. 先序遍历二叉树的操作定义为： 若二叉树为空，则空操作；否则 （1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。 2. 中序遍历二叉树的操作定义为： （1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。 3. 后序遍历二叉树的操作定义为： （1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。

先序遍历： A、 B、 D、 F、 G、 C、 E、 H  中序遍历： B、 F、 D、 G、 A、 C、 E、 H  对于下图所示的二叉树， 其先序、中序、后序遍历的序列如下：  先序遍历： A、 B、 D、 F、 G、 C、 E、 H  中序遍历： B、 F、 D、 G、 A、 C、 E、 H  后序遍历： F、 G、 D、 B、 H、 E、 C、 A C E H G F B D A

例:如图6.9所示的二叉树表达式 (a+b*(c-d)-e/f) 若先序遍历此二叉树,按访问结点 的先后次序将结点排列起来, 其先序序列为： 按中序遍历,其中序序列为： a+b*c-d-e/f 按后序遍历,其后序序列为： abcd-*+ef/- － / ＋ e f a * b - c d 图6.9表达式(a+b*(c-d)-e/f)的二叉树

中序遍历二叉树(I) 1. 中序遍历二叉树的操作定义为： 若二叉树为空，则空操作；否则 （1）中序遍历左子树； A （2）访问根结点； （3）中序遍历右子树。 2. 中序遍历左子树时访问的第 一个结点是根结点的最左下方的 子孙结点B。 为找到此结点考虑使用栈，将 根结点、根结点的左孩子、左孩子的 左孩子、…直到该结点均压入栈中； A C B F G E H I J K

中序遍历二叉树(II) 弹出当前的栈顶元素（即B)并访问之 然后中序遍历结点B的右子树， 将结点B右子树的根结点压入栈中， 先退栈弹出刚才压入的空指针，再次 退栈则访问该结点的上一层的 根结点A 3. 对以E为根的子树的中序遍历 过程与上述过程类似： A C B F G E H I J K

中序遍历二叉树(III) 首先找到该子树最左下方的 子孙结点（例如H)，此过程通过 将子树根结点E、E的左孩子、 左孩子的左孩子、…均压入 栈来实现。 弹出当前的栈顶元素（即H) 并访问之 然后中序遍历结点H的右子树， 将H的右子树的根结点压入栈中， 如果H没有右子树，则先退栈弹出刚才 压入的空指针，再次退栈则访问该 结点的上一层的根结点E A C B F G E H I J K

Status InOrderTraverse(BiTree T, Status ( Status InOrderTraverse(BiTree T, Status (*Visit)(TElemType e)) { // 中序遍历二叉树的非递归算法 InitStack (S); Push(S, T); //根指针进栈  while (!StackEmpty(S)){ while (GetTop(S, p) && p) Push(S, p->lchild); // 向左走到尽头  Pop(S, p); // 空指针退栈   if (!StackEmpty(S)){//访问结点，向右一步 Pop(S, p); if (!Visit(p->data)) return ERROR; Push(S, p->rchild); } // if }// while return OK; } //InOrderTraverse a c e d b 算法6.2

Status InOrderTraverse(BiTree T, Status ( Status InOrderTraverse(BiTree T, Status (*Visit)(TElemType e)) { // 中序遍历二叉树的非递归算法，空指针不进栈 InitStack (S); p=T;  while(p || !StackEmpty(S)){ //访问根结点后栈为空，此时p非空 if (p) { // 根指针进栈，遍历左子树 // Push(S, p);  p=p->lchild;  } else { //根指针退栈，访问根结点，遍历右子树// Pop(S, p); if (!Visit(p->data)) return ERROR;  p=p->rchild;  }//else } //while return OK; } //InOrderTraverse 算法6.3

Status PreOrderTraverse(BiTree T, Status ( Status PreOrderTraverse(BiTree T, Status (*Visit((TElemType e)) { // 先序遍历二叉树的非递归算法 InitStack (S); Push(S, T); //根指针进栈 while (!StackEmpty(S)){ while (GetTop(S, p) && p) { if (!Visit(p->data)) return ERROR; Push(S, p->lchild); // 向左走到尽头 }  Pop(S, p); // 空指针退栈   if (!StackEmpty(S)){//访问结点，向右一步 Pop(S, p); //中序：if (!Visit(p->data)) return ERROR; Push(S, p->rchild); } // if }// while return OK; } //PreOrderTraverse a c e d b

Status PreOrderTraverse(BiTree T, Status ( Status PreOrderTraverse(BiTree T, Status (*Visit)(TElemType e)) { // 先序遍历二叉树的非递归算法  InitStack (S); p=T;  while(p || !StackEmpty(S)){ if (p) { // 根指针进栈，遍历左子树 // if (!Visit(p->data)) return ERROR; Push(S, p); p=p->lchild;  } else { //根指针退栈，访问根结点，遍历右子树// Pop(S, p); //中序：if (!Visit(p->data)) return ERROR;  p=p->rchild;  }//else } //while return OK; } //PreOrderTraverse

遍历二叉树的算法中的基本操作是访问结点，因此不论按哪一种次序进行遍历，对含n个结点的二叉树，其时间复杂度为O(n)。

先序遍历二叉树的递归算法 void PreOrder(BiTree root) { if (root! =NULL) { Visit(root ->data); /*访问根结点*/ PreOrder(root ->lchild); /*先序遍历左子树*/ PreOrder(root ->rchild); /*先序遍历右子树*/ } }

中序遍历二叉树的递归算法 void InOrder(BiTree root) { if (root! =NULL) { InOrder(root ->lchild); /*中序遍历左子树*/ Visit(root ->data); /*访问根结点*/ InOrder(root ->rchild); /*中序遍历右子树*/ } }

后序遍历二叉树的递归算法 void PostOrder(BiTree root) { if (root! =NULL) { PostOrder(root ->lchild); /*后序遍历左子树*/ PostOrder(root ->rchild); /*后序遍历右子树*/ Visit(root ->data); /*访问根结点*/ } }

遍历算法应用 1. 输出二叉树中的结点 遍历算法将走遍二叉树中的每一个结点，故输出二叉树中的结点并无次序要求，因此可用三种遍历中的任何一种算法完成。下面写出先序遍历的实现算法。

/* 先序遍历输出二叉树结点, root为指向二叉树根结点的指针 */ void PreOrder(BiTree root) { /* 先序遍历输出二叉树结点, root为指向二叉树根结点的指针 */ if (root! =NULL) { printf (root ->data); /* 输出根结点 */ PreOrder(root ->lchild); /* 先序遍历左子树 */ PreOrder(root ->rchild); /* 先序遍历右子树 */ } } 【先序遍历输出二叉树中的结点】

2. 输出二叉树中的叶子结点 输出二叉树中的叶子结点与输出二叉树中的结点相比，它是一个有条件的输出问题，即在遍历过程中走到每一个结点时需进行测试，看是否有满足叶子结点的条件。

void PreOrder(BiTree root) { if (root! =NULL) { if (root ->lchild==NULL && root ->rchild==NULL) printf (root ->data); /* 输出叶子结点 */ PreOrder(root ->lchild); /* 先序遍历左子树 */ PreOrder(root ->rchild); /* 先序遍历右子树 */ } } 【先序遍历输出二叉树中的叶子结点】

void leaf(BiTree root){ 3. 统计叶子结点数目 void leaf(BiTree root){ /* LeafCount是保存叶子结点数目的全局变量, 调用之前初始化值为0 */ if (root! =NULL) { leaf(root->lchild);  leaf(root->rchild);  if (root ->lchild==NULL && root ->rchild==NULL) LeafCount++;  } } 【后序遍历统计叶子结点数目(1)】

/* 采用递归算法，如果是空树，返回0；如果只有一个结点，返回1；否则为左右子树的叶子结点数之和 */ int leaf(BiTree root) { int LeafCount;  if (root==NULL)  LeafCount =0;  else if((root->lchild==NULL)&&(root->rchild==NULL)) LeafCount =1;  else  LeafCount =leaf(root->lchild)+leaf(root->rchild);  /* 叶子数为左右子树的叶子数目之和 */ return LeafCount;  } 【后序遍历统计叶子结点数目(2)】

4. 建立二叉链表方式存储的二叉树 给定一棵二叉树，我们可以得到它的遍历序列；反过来，给定一棵二叉树的遍历序列，我们也可以创建相应的二叉链表。这里所说的遍历序列是一种“扩展的遍历序列”。在通常的遍历序列中，均忽略空子树，而在扩展的遍历序列中，必须用特定的元素表示空子树。例如，下图中二叉树的“扩展先序遍历序列”为： AB.DF..G..C.E.H.. 其中用小圆点表示空子树。

void CreateBiTree(BiTree &T) { char ch; ch=getchar();  if (ch==′.′) T=NULL;  else { if (!(T=(BiTree)malloc(sizeof(BiTNode)))) exit(OVERFLOW);  T->data=ch;  CreateBiTree(T->lchild);  CreateBiTree(T->rchild);  } } 【用“扩展的先序遍历序列”创建二叉链表】

5. 求二叉树深（高）度 设函数表示二叉树T的高度，则递归定义如下:  若T为空，则高度为0。 bt 左子树 右子树 hl hr height=max(hl, hr) + 1

设根结点为第1层的结点，所有h层的结点的左右孩子结点在h+1层，则可以通过后序遍历计算二叉树中的每个结点的层次，其中最大值即为二叉树的高度。 二叉树的高度 (深度) 为二叉树中结点层次的最大值，结点的层次自根结点起递推。 设根结点为第1层的结点，所有h层的结点的左右孩子结点在h+1层，则可以通过后序遍历计算二叉树中的每个结点的层次，其中最大值即为二叉树的高度。

【后序遍历求二叉树的高度的递归算法】 int PostTreeDepth(BiTree bt) { /* 后序遍历求二叉树的高度的递归算法 */ int hl, hr, max; if (bt! =NULL) { hl=PostTreeDepth(bt->lchild); /* 求左子树的深度 */ hr=PostTreeDepth(bt->rchild); /* 求右子树的深度 */ max=hl>hr?hl: hr; /* 得到左、右子树深度较大者*/ return(max+1); /* 返回树的深度 */ } else return 0; /* 如果是空树， 则返回0 */ } 【后序遍历求二叉树的高度的递归算法】

6. 按层次遍历二叉树 void LayerOrder(BiTree T) { //层序遍历二叉树    InitQueue(Q); //建立工作队列    EnQueue(Q,T);    while(!QueueEmpty(Q)) {     DeQueue(Q,p);    visit(p);    if (p->lchild) EnQueue(Q,p->lchild);      if (p->rchild) EnQueue(Q,p->rchild);   } }//LayerOrder

6.3.2 线索二叉树 lchild LTag data RTag rchild 6.3.2 线索二叉树 以二叉链表作为存储结构时,只能找到结点的左、右孩子的信息,而不能得到结点的任一（前序、中序或后序）序列的前驱与后继信息,这种信息只有在遍历的动态过程中才能得到,为了保存所需的信息,可增加标志域。 lchild LTag data RTag rchild 其中: lchild域指示结点的左孩子 lchild域指示结点的前驱 rchild域指示结点的右孩子 rchild域指示结点的后继

以前述结点结构构成的二叉链表作为二叉树的存储结构,叫做线索链表,其中指向结点前驱与后继的指针叫做线索。 加上线索的二叉树称之为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。

在中序线索二叉树中找前驱结点 根据线索二叉树的基本概念和存储结构可知，对于结点p，当p->LTag=1时，p->lchild指向p的前驱。当p->LTag=0时，p->lchild指向p的左孩子。 由中序遍历的规律可知，作为根p的前驱结点，它是中序遍历p的左子树时访问的最后一个结点，即左子树的“最右下端”结点。 a c e d b f

在中序线索二叉树中找后继结点 对于结点p，若要找其后继结点，当p->RTag=1时， p->rchild即为p的后继结点；当p->RTag=0时，说明p有右子树，此时p的中序后继结点即为其右子树的“最左下端”的结点。 a c e d b f

在先序线索二叉树中找前驱结点 在先序线索树中找结点的前驱比较困难。 若结点p是二叉树的根，则p的前驱为空； 若p是其双亲的左孩子，或者p是其双亲的右孩子并且其双亲无左孩子，则p的前驱是其双亲结点； 若p是双亲的右孩子且双亲有左孩子，则p的前驱是其双亲的左子树中按先序遍历时最后访问的那个结点。 a c e d b f

在先序线索二叉树中找后继结点 根据先序线索树的遍历过程可知， 若结点p存在左子树，则p的左孩子结点即为p的后继； 若结点p既没有左子树，也没有右子树，则结点p的rchild指针域所指的结点即为p的后继。 a c e d b f

在后序线索二叉树中找前驱结点 根据后序线索树的遍历过程可知， 若结点p存在右子树，则右子树的根即为p的前驱； 若结点p既无左子树、又无右子树，则p->lchild即为它的前驱。 a c e d b f

在后序线索二叉树中找后继结点 可分为3种情况： 若结点p是二叉树的根，则其后继为空； a c e d b f

二叉树的二叉线索存储表示 typedef enum PointerTag {Link,Thread}; typedef struct BiThrNode { TelemType data; struct BiThrNode *lchild,*rchild; PointerTag LTag, Rtag; }BiThrNode,*BiThrTree;

Thrt 1 在二叉树的线索链表上添加一个头结点,令其lchild域的指针指向二叉树的根结点,其rchild域的指针指向中序遍历时访问的最后一个结点;同时,令二叉树中序序列中的第一个结点lchild域的指针和最后一个结点rchild域的指针均指向头结点，好比为二叉树建立双向线索链表。 A B C D E F G H I J K L M N

A H Thrt 1 中序遍历二叉线索树的过程分析(I) 如果用指针p从头结点（T指向该 头结点）开始访问，则遍历过程 结束时，p==T。 中序遍历二叉线索树的过程分析(I) A 如果用指针p从头结点（T指向该 头结点）开始访问，则遍历过程 结束时，p==T。 从根结点A开始，找到其左孩子， 左孩子的左孩子，…，直到某个 结点(即D)的LTag==1。 B C D E F G H I J K L M N

A H 中序遍历二叉线索树的过程分析(II) Thrt 1 访问该结点，如果该结点的RTag==1 (说明该结点有直接后继)，且该结点的rchild不指向头结点T（即该结点不是中序遍历的最后一个结点），则沿着该结点的rchild找到后继结点、后继结点的后继结点，…，并访问之。 如果某个结点的RTag==0则说明 该结点有右子树，此时应该访问 其右子树。 A B C D E F G H I J K L M N

A H 中序遍历线索二叉树的过程分析(III) Thrt 1 如果某个结点的rchild指向T,即该 结点是中序遍历的最后一个结点， 此时说明遍历过程应该结束。 A B C D E F G H I J K L M N

Status InOrderTraverse_Thr(BiThrTree T, Status(*Visit)(TElemType)) { //T指向头结点,头结点的lchild左链指向根结点 //中序遍历二叉线索树的非递归算法,对每个数据元素调用函数Visit p=T–>lchild; //p指向根结点 while (p!=T) { //空树或遍历结束时p==T while (p –>LTag ==0) p=p –>lchild; if (!Visit(p –>data)) return ERROR;//访问左子树为空的结点 while (p –>RTag ==1 && p –>rchild!=T) { p=p –>rchild; Visit(p –>data); // 访问后继结点 } p= p–>rchild; //如果p->RTag==Link,则从其右子树开始 return OK; }//InOrderTraverse_Thr

线索化的实质是将二叉链表中的空指针改为指向前驱 或后继的线索 前驱或后继的信息只有在遍历时才能得到 因此，线索化的过程即为在遍历过程中修改空指针的 过程

Status InOrderThreading(BiThrTree &Thrt, BiThrTree T) { //中序遍历二叉树T,并将其中序线索化，Thrt指向头结点 if (!Thrt = (BiThrTree)malloc(sizeof(BiThrNode))) exit (OVERFLOW); Thrt->LTag=0; Thrt->RTag=1; //建立头结点 Thrt->rchild=Thrt; //右指针回指 if (!T) Thrt->lchild=Thrt; //若二叉树空，左指针回指 else { Thrt->lchild=T; pre=Thrt; //pre指向前驱结点 InThreading(T); //中序遍历进行中序线索化 pre->rchild=Thrt; //最后一个结点线索化 pre->RTag=1; Thrt->rchild=pre; } return OK; }//InOrderThreading

Status InThreading(BiThrTree &p) { //中序遍历进行中序线索化 if (p) { InThreading(p->lchild); //左子树线索化 if (!p->lchild) { //无左孩子才能加前驱 p->LTag=1; p->lchild=pre;} //前驱线索 if (!pre->rchild) { //无右孩子才能加后继 pre->RTag=1; pre->rchild=p;}//后继线索 pre=p; //保持pre指向p的前驱 InThreading(p->rchild); //右子树线索化 } return OK; }//InOrderThreading

由先序和中序序列构造一棵二叉树 由定义可知，二叉树的先序（即前序）遍历是先访问根，其次遍历左子树L，最后遍历右子树R。即在结点的先序序列中，第一个结点必为根D。（ ABCDEFG） 由于中序遍历是先遍历左子树L，然后访问根D，最后遍历右子树R，则根结点D将中序序列分成两部分：在D之前是左子树中结点的中序序列，在D之后是右子树中的中序序列。（ CBEDAFG） 反过来，根据左子树的中序序列中结点的个数，又可将先序序列除根以外分成左子树的先序序列和右子树的先序序列。

例6-5 已知结点的前序序列和中序序列分别为： 前序序列：ABCDEFG 中序序列：CBEDAFG 依此类推，可递归得到整棵二叉树。 例6-5 已知结点的前序序列和中序序列分别为： 前序序列：ABCDEFG 中序序列：CBEDAFG 要求按上述分解求得整棵二叉树，其构造过程参见教材p.154

第六章 树和二叉树 6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.6 赫夫曼树及其应用

6.4.1 树的存储结构 1. 双亲表示法 这种方法用一组连续的空间来存储树中的结点，在保存每个结点的同时附设一个指示器来指示其双亲结点在表中的位置，其结点的结构如下： 数据 双亲 data parent

//------------树的双亲表存储表示---------------- #define MAX_TREE_SIZE 100 typedef struct PTNode { //结点结构 TElemType data; int parent; //双亲位置域 }PTNode; typedef struct { //树结构 PTNode nodes[MAX_TREE_SIZE]; int r,n; //根的位置和结点数 }PTree; data parent A -1 B C D 1 E F G 2

A -1 B C D 1 E F G 2 1 2 3 4 5 6 B C E D F G 数组下标 data parent A C D 1 E F G 2 A B C E D F G 1 2 3 4 5 6 树的双亲表示法

2. 孩子表示法 这种方法通常是把每个结点的孩子结点排列起来，构 成一个单链表，称为孩子链表。n个结点共有n个孩子链表（叶子结点的孩子链表为空表），而n个结点的数据和n个孩子链表的头指针又组成一个顺序表。

数组下标 a b c e d f g a b c d e f g 1 2 1 2 3 4 5 6 3 4 5 6 树的孩子表示法

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

3. 孩子兄弟表示法 又称为二叉树表示法或二叉链表表示法，即以二叉链表作为树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。 //--------------树的二叉链表（孩子-兄弟）存储表示---------- typedef struct CSNode { ElemType data;  Struct CSNode *firstchild, *nextsibling; }CSNode, *CSTree; 

1 1 2 3 5 4 6 7 2 4 3 5 7 6 树的孩子兄弟表示法

6.4.2 森林与二叉树的相互转换 树转换为二叉树 将一棵树转换为二叉树的思路, 主要根据树的孩 子-兄弟存储方式而来的,方法是： 树中所有相邻兄弟之间加一条连线。  对树中的每个结点，只保留其与第一个孩子结点之间的连线，删去其与其它孩子结点之间的连线。  以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明(注意保证每个结点的左孩子、右兄弟的关系)。

A B D E F C G H 树到二叉树的转换

树和二叉树的对应关系示例

2. 森林转换为二叉树 森林是若干棵树的集合。树可以转换为二叉树，森林同样也可以转换为二叉树。因此，森林也可以方便地用孩子兄弟链表表示。森林转换为二叉树的方法如下：  将森林中的每棵树转换成相应的二叉树。 第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连在一起后，所得到的二叉树就是由森林转换得到的二叉树。

(a) 森林 (b) 森林中每棵树对应的二叉树 (c) 森林对应的二叉树 A E G B C D F H I J A B E A E G C

森林与二叉树转换的形式定义如下： 如果F={T1，T2，… , Tm}是森林，它对应的二叉树为B=(root，LB, RB)。  若m=0， 则B为空树。  若m≠0，则二叉树B的根为森林中第一棵树T1的根； B的左子树LB是从T1中根结点的子树森林F1={T11， T12, …，T1m1}转换而成的二叉树，右子树RB是从森林F’={T2，T3，…，Tm}转化而成的二叉树。 树和森林都可以转换为二叉树，二者的不同是: 树转换成的二叉树, 其根结点必然无右孩子，而森林转换后的二叉树，其根结点有右孩子。

3. 二叉树还原为树或森林 将一棵二叉树还原为树或森林，具体方法如下： 若某结点是其双亲的左孩子，则把该结点的右孩子、 右孩子的右孩子……都与该结点的双亲结点用线连起来。 删掉原二叉树中所有双亲结点与右孩子结点的连线。 整理由①②两步所得到的树或森林，使之结构层次分明。

A B E C F G H I J D (a) 添加连线 (b) 删除右孩子结点的连线 (c) 整理 二叉树到森林的转换示例

二叉树与森林转换的形式定义如下： 若B=(root, LB, RB)是一棵二叉树，B对应的森林F={T1，T2，… , Tm},则有：  若B为空，则F为空；  若B非空，则F中第一棵树T1的根为二叉树B的根root；T1中根结点的子树森林F1由B的左子树LB转换而成；B的右子树RB转换为F中其余树组成的森林，即F’＝{T2, T3, …, Tm}。 

6.4.3 树与森林的遍历 1. 树的遍历 由树结构的定义可引出两种次序遍历树的方法： 先根（序）遍历：先访问树的根结点，然后依次先根遍历根结点的每一棵子树。  后根（序）遍历：先依次后根遍历每棵子树，然后访问根结点。

对左图中的树进行先根遍历，得到树的先根序列为： A B C D E 若对此树进行后根遍历，得到树的后根序列为： B D C E A A E B C D

2. 森林的遍历 森林的遍历方法主要有以下两种：  先序遍历 若森林非空，则遍历方法为： 访问森林中第一棵树的根结点。  先序遍历第一棵树的根结点的子树森林。  先序遍历除去第一棵树之后剩余的树构成的森林。 中序遍历 中序遍历第一棵树的根结点的子树森林。 访问森林中第一棵树的根结点。 中序遍历除第一棵树之后剩余的树构成的森林。 

对上图中的森林进行先序遍历，得到森林的先序序列为： ABCDEFGHIJ 若对此森林进行中序遍历，得到森林的中序序列为： BCDAFEHJIG

由森林与二叉树之间的转换规则可知，当森林转换成二叉树时，其第一棵子树森林转换成左子树，剩余树的森林转换成右子树，因此森林的先序和中序遍历即为对应的二叉树的先序和中序遍历。 以二叉链表作为树的存储结构时，树的先根遍历和后根遍历可借用二叉树的先序遍历和中序遍历的算法实现。

第六章 树和二叉树 6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.6 赫夫曼树及其应用

6.6 赫夫曼树及其应用 6.6.1 最优二叉树（赫夫曼树） 1. 路径和路径长度 路径是指从一个结点到另一个结点之间的分支序列， 路径长度是指从一个结点到另一个结点所经过的分支数目。

2. 结点的权和带权路径长度 在实际的应用中，人们常常给树的每个结点赋予一个具有某种实际意义的实数，我们称该实数为这个结点的权。在树形结构中，从树根到某一结点的路径长度与该结点的权的乘积，叫做该结点的带权路径长度。

3. 树的带权路径长度 树的带权路径长度为树中所有叶子结点的带权路径长度之和，通常记为： 其中n为叶子结点的个数，wi为第i个叶子结点的权值，li为第i个叶子结点的路径长度。 

具有不同带权路径长度的二叉树 WPL(a)=7×2＋5×2＋2×2＋4×2＝36 WPL(b)=4×2＋7×3＋5×3＋2×1＝46 C A 4 5 7 5 2 4 B D 2 A B C D 7 5 4 C D A B (a) 带权路径长度为36 (b) 带权路径长度为46 (c)带权路径长度为35 具有不同带权路径长度的二叉树 WPL(a)=7×2＋5×2＋2×2＋4×2＝36 WPL(b)=4×2＋7×3＋5×3＋2×1＝46 WPL(c)=7×1＋5×2＋2×3＋4×3＝35

4. 赫夫曼树 假设有n个权值(w1, w2, w3,…, wn)，试构造一棵具有n个叶子结点的二叉树，每个叶子结点带权为wi,其中带权路径长度WPL最小的二叉树称为最优二叉树或赫夫曼树。

在森林F中选出两棵根结点的权值最小的树作为一棵新树的左、右子树，且置新树的根结点的权值为其左、右子树上根结点的权值之和； 构造赫夫曼树的步骤如下: 根据与n个权值{w1,w2,…,wn}对应的n个结点构成具有n棵二叉树的森林F={T1,T2,…,Tn},其中每棵二叉树Ti (1≤i≤n)都只有一个权值为wi的根结点，其左、右子树均为空； 在森林F中选出两棵根结点的权值最小的树作为一棵新树的左、右子树，且置新树的根结点的权值为其左、右子树上根结点的权值之和； 4 b a d c 2 5 9

从F中删除构成新树的两棵树，同时把新树加入到F中;

构造赫夫曼树的过程 4 b a d c 2 5 9 d a b c 4 5 2 6 9 d a b c 4 9 5 2 6 11 20 d

6.5.2 赫夫曼编码 表6 – 1 指令的使用频率 指令 使用频率(Pi） I1 0.40 I2 0.30 I3 0.15 I4 0.05 6.5.2 赫夫曼编码 指令 使用频率(Pi） I1 0.40 I2 0.30 I3 0.15 I4 0.05 I5 0.04 I6 0.03 I7 表6 – 1 指令的使用频率

若要设计长短不等的编码,则必须是任一个字符的编码都不是另外一个字符编码的前缀,这种编码称做前缀编码。 表6 – 2 指令的变长编码 指令 变长编码 I1 I2 1 I3 00 I4 01 I5 000 I6 001 I7 010 若要设计长短不等的编码,则必须是任一个字符的编码都不是另外一个字符编码的前缀,这种编码称做前缀编码。

构造赫夫曼树示例

可以验证，该编码是前缀编码。 表6 – 3 指令的赫夫曼编码 指令 赫夫曼编码 I1 I2 10 I3 110 I4 11100 I5 I2 10 I3 110 I4 11100 I5 11101 I6 11110 I7 11111 表6 – 3 指令的赫夫曼编码 可以验证，该编码是前缀编码。

若一段程序有1000条指令， 其中I1大约有400条，I2大约有300条，I3大约有150条，I4大约有50条，I5大约有40条，I6大约有30条，I7大约有30条。对于定长编码，该段程序的总位数大约为3×1000＝3000。采用赫夫曼编码后，该段程序的总位数大约为 1×400＋2×300＋3×150＋5×（50＋40＋30＋30）＝2200。

可见，赫夫曼编码中虽然大部分编码的长度大于定长编码的长度3，却使得程序的总位数变小了。可以算出该赫夫曼编码的平均码长为：

举例：数据传送中的二进制编码,要传送数据 state, seat, act, tea, cat, set, a, eat，如何使传送的长度最短？ 首先规定二叉树的构造为左走0，右走1。 为了保证长度最短，先看字符出现的次数，然后将出现次数当作权，如下图所示。 字 符 s t a e c 字符出现次数 3 8 7 5 2

构造赫夫曼树的过程 按规定：左0右1，则有 所以有state 的编码为00111101101,stat的编码为001111011。 000 2 3 5 7 8 c s e a t

前述构造满足赫夫曼编码的最短最优性质： 若di≠dj（字母不同），则对应的树叶不同，因此前缀码（任一字符的编码都不是另一个字符编码）不同，一个路径不可能是其它路径的一部分，所以字母之间可以完全区别。  将所有字符变成二进制的赫夫曼编码，使带权路径长度最短。

6.6.3 赫夫曼编码算法的实现 由于赫夫曼树中没有度为1的结点，则一棵有n个叶子的赫夫曼树共有2n-1个结点，可以用一个大小为2n-1的一维数组存放赫夫曼树的各个结点。由于每个结点同时还包含其双亲信息和孩子结点的信息，所以构成一个静态三叉链表。 N=n0+n1+n2 n1=0 (无度为1的结点) n0+n1+n2 N=2n0-1=2n-1

//--------------赫夫曼树和赫夫曼编码的存储表示--------------- typedef struct { unsigned int weight ; /* 用来存放结点的权值*/ unsigned int parent, lchild, rchild ; /*指向双亲、孩子结点的指针*/ }HTNode, * HuffmanTree; /*动态分配数组存储赫夫曼树*/ typedef char * *HuffmanCode ; /*动态分配数组存储赫夫曼编码表*/

求赫夫曼编码的算法如下： void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int * w, int n){ //w存放n个字符的权值, 构造赫夫曼树HT, 并求出n个字符的赫夫曼编码HC。  if (n<=1) return; m=2*n-1; //m是总的结点数 HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /*0号单元未使用*/  for (p=HT+1,i=1; i<=n; ++i, ++p, ++w) *p={ *w, 0, 0, 0}; /*叶子结点初始化*/ for (i=n+1; i<=m; ++i, ++p) *p={0, 0, 0, 0}; /*非叶子结点初始化*/ 

HT[s1].parent=i; HT[s2].parent=i;  for (i=n+1; i<=m; ++i) { /*建赫夫曼树*/ /*在HT[1..i-1]选择parent为0且weight最小的两个结点，其序号分别为s1、s2*/ Select(HT, i-1, s1, s2);  HT[s1].parent=i; 　HT[s2].parent=i;  HT[i].lchild=s1; HT[i].rchild=s2;  HT[i].weight=HT[s1].weight+HT[s2].weight; } /*赫夫曼树建立完毕*/

HC=(HuffmanCode)malloc((n+1)*sizeof(char *)); /*分配n个字符编码的头指针向量*/ /*从叶子结点到根，逆向求每个叶子结点对应的赫夫曼编码*/ HC=(HuffmanCode)malloc((n+1)*sizeof(char *)); /*分配n个字符编码的头指针向量*/ cd=(char * )malloc(n * sizeof(char )); /*分配求当前编码的工作空间*/ cd[n-1]＝ ”\0”； /*从右向左逐位存放编码，首先存放编码结束符*/

start=n-1; /*初始化编码起始指针*/ for (i=1; i<=n; ++i) { /*求n个叶子结点对应的赫夫曼编码*/ 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”; /*左分支标0*/  else cd[--start]=“1”; /*右分支标1*/ HC[i]=(char *)malloc((n-start)*sizeof(char));/*为第i个编码分配空间,(n-start)为编码长度*/ strcpy(HC[i], &cd[start]); //从cd复制编码串到HC } free(cd); } //HuffmanCoding

例：已知某系统在通信联络中只可能出现8种字符，其概率分别为{0. 15, 0. 19, 0. 07, 0. 18, 0. 04, 0 例：已知某系统在通信联络中只可能出现8种字符，其概率分别为{0.15, 0.19, 0.07, 0.18, 0.04, 0.23, 0.03, 0.11}，试设计赫夫曼编码，并计算对应赫夫曼树的带权路径长度。 1.0 0.19 0.58 0.42 0.23 0.25 0.33 0.11 0.14 0.15 0.18 0.07 0.03 0.04 WPL=0.19*2+0.23*2+0.11*3+0.03*5 +0.04*5+0.07*4+0.15*3+0.18*3 =2.79

复 习 题 在下列存储中，______不是树的存储形式。 对于一棵具有n个结点、度为4的树来说_____。 A A. 树的高度至多是n-3 B. 树的高度至多是n-4 C. 第i层上至多有4*(i-1)个结点 D. 至少在某一层上正好有4个结点 在下列存储中，______不是树的存储形式。 A. 双亲表示法 B. 孩子链表示法 C. 孩子兄弟链表示法 D. 顺序存储表示法 A D

复 习 题 用双亲存储结构表示树，其优点之一是：比较方便_____。 A A. 找指定结点的双亲结点 B. 找指定结点的孩子结点 C. 找指定结点的兄弟结点 D. 判断某结点是不是叶子结点 用孩子链存储结构表示树，其优点是______比较方便。 A. 判断两个指定结点是不是兄弟 B. 找指定结点的双亲 C. 判断指定结点在第几层 D. 计算指定结点的度数 A D

复 习 题 如果在树的孩子兄弟链存储结构中有6个空的左指针域，7个空的右指针域，5个结点的左、右指针域都为空，则该树中树叶的个数是______。 A. 7个 B. 6个 C. 5个 D. 不能确定 如果用孩子兄弟链来表示一棵具有n(n>1)个结点的树，则在该存储结构中_____。 A. 至多有n-1个非空的右指针域 B. 至少有2个空的右指针域 C. 至少有2个非空的左指针域 D. 至多有n-1个空的右指针域 B B A B C (A) D A B C (C) A B (D)

复 习 题 如果用孩子兄弟链来表示一棵具有n(n>1)个结点的树，则在该存储结构中_____。 A. 至多有n-1个非空的右指针域 B. 至少有2个空的右指针域 因为结点总数>1，所以至少根结点和第2层中最右边的结点均没有右兄弟，即至少有2个空的右指针域 A B C (A) D

复 习 题 如果用孩子兄弟链来表示一棵具有n(n>1)个结点的树，则在该存储结构中_____。 C. 至少有2个非空的左指针域 这句话的意思是至少有两个结点有孩子，但是从图上可以看出当结点总数>1时，至少有1个结点（即根结点）是有孩子的，即至少有1个非空的左指针域 D. 至多有n-1个空的右指针域 这句话的意思是至多有n-1个结点没有右兄弟，但是从图上可以看出，至多有n个结点可以没有右兄弟 A B C (C) A B (D)

复 习 题 设森林F中有3棵树，第1、2和3棵树的结点个数分别为m1、m2和m3。与森林F对应的二叉树根结点的右子树上的结点个数是______。 A. m1 B. m1+m2 C. m3 D. m2+m3 如果T1是由有序树T转换而来的二叉树，那么T中结点的后根序列就是T1中结点的_____序列。 A. 先序 B. 中序 C. 后序 D. 层次 D B

复 习 题 设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树结点个数为n，森林F中第一棵树的结点个数是______。 A. m-n B. m-n-1 C. n+1 D. 无法确定 一棵完全二叉树上有1001个结点，其中叶子结点的个数是_____。 A. 250 B. 501 C. 254 D. 505 A B

复 习 题 一棵有124个叶子结点的完全二叉树，最多有______个结点。 B A. 247 B. 248 C. 249 D. 250 在高度为h的完全二叉树中，_____。 A. 度为0的结点都在第h层上 B. 第i （1≤i ≤ h）层上结点都是度为2的结点 C.第i （1≤i < h）层上有2i-1个结点 D. 不存在度为1的结点 B C

复 习 题 若二叉树的中序遍历序列是abcdef，且c为根结点，则______。 A A. 结点c有两个孩子 B. 二叉树有两个度为0的结点 A. 结点b一定在结点a的前面 B. 结点a一定在结点c的前面 C. 结点b一定在结点c的前面 D. 结点a一定在结点b的前面 A C

复 习 题 设n、m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是______。 C A. n在m的右方 B. n是m的祖先 C. n在m的左方 D. n是m的子孙 如果在一棵二叉树的先序序列、中序序列和后序序列中，结点a、b的位置都是a在前、b在后（形如…a…b…），则_____。 A. a、b可能是兄弟 B. a可能是b的双亲 C. a可能是b的孩子 D.不存在这样的二叉树 C A

复 习 题 设有13个值，用它们来组成一棵赫夫曼树，则该树共有______个结点。 D A. 13 B. 12 C. 26 D. 25 根据使用频率为5个字符设计的赫夫曼编码不可能是_____。 A. 111，110，10，01，00 B. 000，001，010，011，1 C. 100，11，10，1，0 D. 001，000，01，11，10 D C

复 习 题 非空二叉树共有______种基本形态。 4 若用孩子兄弟链存储结构来存储具有m个树叶、n个分支 结点的树，则孩子兄弟链存储结构中有  个左指针域 为空，有  个右指针域为空的结点。 n个结点的二叉树中如果有m个树叶，则一定有  个度为1 的结点，  个度为2的结点。 8层完全二叉树至少有  个结点，拥有100个结点 的完全二叉树的最大层数为 。 4 m n+1 n-2m+1 m-1 128 7

复 习 题 若一个二叉树的叶子结点是某子树的中序遍历序列中的最 后一个结点，则它必是该子树的__________序列中的最后 一个结点。 若以{4，5，6，7，8}作为叶子结点的权值构造赫夫曼树， 则其带权路径长度是  ，各结点对应的赫夫曼编 码是  。 先序遍历 69 010、011、10、11、00

复 习 题 判断以下叙述的正确性。 树型结构中每个结点都有一个前驱结点。 度为m的树中至少有一个度为m的结点。 (  ) 在树型结构中，处于同一层上的各结点之间具有兄弟关系。 不存在这样的二叉树，它有n个度为0的结点，n-1个度为1的结点，n-2个度为2的结点。 在任何一棵完全二叉树中，终端结点或者和分支结点一样多，或者只比分支结点多1个。 (  ) (  ) (  ) ( ) (  )

复 习 题 在赫夫曼树中，权值相同的树叶结点都在同一层上。 (  ) 若一个树叶是某二叉树先序遍历序列中的最后一个结点，则它必是该树中序遍历序列中的最后一个结点。 二叉树就是度为2的树。 对于二叉树在后序遍历序列中，任意一个结点的后面都不会出现它的子孙结点。 在赫夫曼编码中，当两个字符出现的频率相同时，其编码也相同。 (  ) (  ) ( ) (  ) (  )

复 习 题 假设二叉树采用二叉链存储结构存储，请编写一个算法，给出二叉树中一个非根结点（由指针p所指），求它的兄弟结点（用某指针指向之，若没有兄弟结点，则该指针为空）。 BiTNode * FindParent(BiTNode *b, BiTNode *p, char &tag) { /*在二叉树b中找到结点*p的双亲结点，tag指明*p是其双亲的左孩子还是右孩子*/ …………… }

复 习 题 BiTNode * FindParent(BiTNode *b, BiTNode *p, char &tag) { /*在二叉树b中找到结点*p的双亲结点，tag指明*p是其双亲的左孩子还是右孩子*/ if (b == NULL) return NULL; if (b->lchild == p) {tag = ‘L”; return b;} if (b->rchild == p) {tag = ‘R’; return b;} FindParent(b->lchild, p, tag); //在左子树中查找 FindParent(b->rchild, p, tag); //在右子树中查找 }// end of FindParent

BiTNode * FindBrother(BiTNode *b, BiTNode *p) { /* 返回兄弟结点的指针 */ q = FindParent(b, p, tag); if (q) { if (tag == ‘R’) return q->lchild; else return q->rchild; } return NULL;