第6章树与二叉树B

1第6章树和二叉树（Tree&BinaryTree）6.1树的基本概念6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林6.5赫夫曼树及其应用（本章及本课程的重点）上机内容：

Huffman编/译码器的设计与实现（实验要求参见严题集P149）26.2二叉树为何要重点研究每结点最多只有两个“叉”的树？二叉树的结构最简单，规律性最强；可以证明，所有树都能转为唯一对应的二叉树，不失一般性。1. 二叉树的定义2. 二叉树的性质3. 二叉树的存储结构（二叉树的运算见下一节）32.二叉树的性质(3+2)性质1:在二叉树的第i层上至多有2i-1个结点（i>0）。性质2:深度为k的二叉树至多有2k-1个结点（k>0）。性质3:对于任何一棵二叉树，若2度的结点数有n2个，则叶子数（n0）必定为n2＋1（即n0=n2+1）课堂练习：1.树Ｔ中各结点的度的最大值称为树Ｔ的

。

Ａ)高度Ｂ)层次Ｃ)深度Ｄ)度2.深度为k的二叉树的结点总数，最多为

个。

Ａ)２k-1

Ｂ)log2kＣ)２k－１Ｄ)２k3.深度为9的二叉树中至少有

个结点。

Ａ)２9

Ｂ)２8

Ｃ)９Ｄ)２9－1√√√4对于两种特殊形式的二叉树（满二叉树和完全二叉树），还特别具备以下2个性质：性质4:具有n个结点的完全二叉树的深度必为log2n＋1性质5:对完全二叉树，若从上至下、从左至右编号，则编号为i

的结点，其左孩子编号必为2i，其右孩子编号为2i＋1；其双亲的编号必为i/2（i＝1时为根,除外）。证明：根据性质2，深度为k的二叉树最多只有2k-1个结点，且完全二叉树的定义是与同深度的满二叉树前面编号相同，即它的总结点数n位于k层和k-1层满二叉树容量之间，即2k-1-1<n≤2k-1或2k-1≤n<2k三边同时取对数，于是有：k-1≤log2n<k因为k是整数，所以k=log2n+1可根据归纳法证明。5课堂讨论：Q1：满二叉树和完全二叉树有什么区别？A1：满二叉树是叶子一个也不少的树，而完全二叉树虽然前n-1层是满的，但最底层却允许在右边缺少连续若干个结点。

满二叉树是完全二叉树的一个特例。Q3:设一棵完全二叉树具有1000个结点，则它有

个叶子结点，有

个度为2的结点，有

个结点只有非空左子树，有

个结点只有非空右子树。48948810Q2：为什么要研究满二叉树和完全二叉树这两种特殊形式？A1：因为只有这两种形式可以实现顺序存储！由于最后一层叶子数为489个，是奇数，说明有1个结点只有非空左子树；而完全二叉树中不可能出现非空右子树(0个)。A3：易求出总层数和末层叶子数。总层数k=log2n＋1=10;且前9层总结点数为29-1=511

(完全二叉树的前k-1层肯定是满的)所以末层叶子数为1000-511=489个。6请注意叶子结点总数≠末层叶子数！还应当加上第k-1层（靠右边）的0度结点个数。分析：末层的489个叶子只占据了上层的245个结点（489/2)上层（k=9)右边的0度结点数还有29-1-245=11个！另一法：可先求2度结点数,再由此得到叶子总数。首先，k-2层的28-1（255）个结点肯定都是2度的（完全二叉）另外，末层叶子（刚才已求出为489）所对应的双亲也是度＝2，（共有489/2＝244个）。所以，全部2度结点数为255(k-2层)＋244(k-1层)=499个；总叶子数＝2度结点数＋1=500个。第i层上的满结点数为2i-1所以，全部叶子数＝489(末层)＋11(k-1层)=500个。度为2的结点＝叶子总数－1=499个。74.二叉树的存储结构一、顺序存储结构按二叉树的结点“自上而下、从左至右”编号，用一组连续的存储单元存储。ABCDEFGHI[1][2][3][4][5][6][7][8][9]ABCGEIDHF问：顺序存储后能否复原成唯一对应的二叉树形状？答：若是完全/满二叉树则可以做到唯一复原。而且有规律：下标值为i的双亲，其左孩子的下标值必为2i，其右孩子的下标值必为2i＋1（即性质5）例如，对应[2]的两个孩子必为[4]和[5],即B的左孩子必是D,右孩子必为E。T[0]一般不用8讨论：不是完全二叉树怎么办？答：一律转为完全二叉树！方法很简单，将各层空缺处统统补上“虚结点”，其内容为空。AB^C^^^D^…E[1][2][3][4][5][6][7][8][9].[16]ABECD缺点：①浪费空间；②插入、删除不便

9二、链式存储结构

用二叉链表即可方便表示。dataleft_childright_childdataleft_childright_child二叉树结点数据类型定义：typedefstructnode*tree_pointer;typedefstructnode{intdata;tree_pointerleft_child,right_child;}node;一般从根结点开始存储。

（相应地，访问树中结点时也只能从根开始）注：如果需要倒查某结点的双亲，可以再增加一个双亲域（直接前趋）指针，将二叉链表变成三叉链表。10例：

ABECD^AB^D^C^^E^116.3遍历二叉树和线索二叉树一、遍历二叉树（TraversingBinaryTree）遍历定义——指按某条搜索路线遍访每个结点且不重复（又称周游）。遍历用途——它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。

遍历方法——牢记一种约定，对每个结点的查看都是“先左后右”。12遍历规则———二叉树由根、左子树、右子树构成，定义为D、

L、RD、L、R的组合定义了六种可能的遍历方案：LDR,LRD,DLR,DRL,RDL,RLD若限定先左后右，则有三种实现方案：

DLRLDRLRD先(根)序遍历中(根)序遍历后(根)序遍历

注：“先、中、后”的意思是指访问的结点D是先于子树出现还是后于子树出现。13例1：先序遍历的结果是：中序遍历的结果是：后序遍历的结果是：ABCDEABDECDBEACDEBCA口诀：DLR—先序遍历，即先根再左再右LDR—中序遍历，即先左再根再右LRD—后序遍历，即先左再右再根14+*A*/EDCB先序遍历+**/ABCDE前缀表示中序遍历A/B*C*D+E中缀表示后序遍历AB/C*D*E+后缀表示层序遍历+*E*D/CAB例2：用二叉树表示算术表达式15遍历的算法实现：用递归形式格外简单！回忆1：二叉树结点的数据类型定义：typedefstructnode*tree_pointer;typedefstructnode{intdata;tree_pointerleft_child,right_child;}node;则三种遍历算法可写出:回忆2：第1章自测卷4.2题：longintfact(n)//求n!intn;{longf;if(n>1)f=n*fact(n-1);elsef=1;return(f);}16先序遍历算法DLR(liuyu*root){if(root!=NULL)//非空二叉树

{printf(“%d”,root->data);//访问DDLR(root->lchild);//递归遍历左子树DLR(root->rchild);//递归遍历右子树

}return(0);}中序遍历算法LDR(x*root){if(root!=NULL){LDR(root->lchild);printf(“%d”,root->data);

LDR(root->rchild);}return(0);}后序遍历算法LRD(x*root){if(root!=NULL)

{LRD(root->lchild);LRD(root->rchild);printf(“%d”,root->data);}return(0);}结点数据类型自定义typedefstructliuyu{intdata;structliuyu*lchild,*rchild；}liuyu;liuyu*root;

17对遍历的分析：1.

从前面的三种遍历算法可以知道：如果将print语句抹去，从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的访问路径是相同的，只是访问结点的时机不同。从虚线的出发点到终点的路径上，每个结点经过3次。AFEDCBG第1次经过时访问＝先序遍历第2次经过时访问＝中序遍历第3次经过时访问＝后序遍历2.二叉树遍历的时间效率和空间效率时间效率:O(n)

//每个结点只访问一次空间效率:O(n)

//栈占用的最大辅助空间（精确值：树深为k的递归遍历需要k+1个辅助单元！）18例：【严题集6.42③】编写递归算法，计算二叉树中叶子结点的数目。

思路：输出叶子结点比较简单，用任何一种遍历算法，凡是左右指针均空者，则为叶子，将其统计并打印出来。DLR(liuyu*root)//采用中序遍历的递归算法{if(root!=NULL)//非空二叉树条件，还可写成if(root){if(!root->lchild&&!root->rchild)//是叶子结点则统计并打印

{sum++;printf("%d\n",root->data);}

DLR(root->lchild);//递归遍历左子树，直到叶子处；

DLR(root->rchild);}//递归遍历右子树，直到叶子处；}return(0);}19注：要实现遍历运算必须先把二叉树存入机内。思路：利用前序遍历来建树

（结点值陆续从键盘输入，用DLR为宜）BintreecreateBTpre(){BintreeT;charch;scanf(“%c”,&ch);if(ch==’’)T=NULL;else{T=(Bintree)malloc(sizeof(BinTNode));T->data=ch;T->lchild=createBTpre();T->rchild=createBTpre();}returnT;}怎样建树？见教材P131程序。20习题讨论：1.求二叉树深度，或从x结点开始的子树深度。

算法思路：只查各结点后继链表指针，若左(右)孩子的左(右)指针非空，则层次数加1；否则函数返回。技巧：递归时应当从叶子开始向上计数，层深者保留。否则不易确定层数。2.按层次输出二叉树中所有结点。

算法思路：既然要求从上到下，从左到右，则利用队列存放各子树结点的指针是个好办法，而不必拘泥于递归算法。技巧：当根结点入队后，令其左、右孩子结点入队，而左孩子出队时又令它的左右孩子结点入队，……由此便可产生按层次输出的效果。ABCDE213中序遍历的非递归(迭代)算法算法思路：若不用递归，则要实现二叉树遍历的“嵌套”规则，必用堆栈。可直接用while语句和push/pop操作。参见教材P130-131程序。4.判别给定二叉树是否为完全二叉树（即顺序二叉树）。

算法思路：完全二叉树的特点是：没有左子树空而右子树单独存在的情况(前k-1层都是满的，且第k层左边也满）。技巧:按层序遍历方式，先把所有结点（不管当前结点是否有左右孩子）都入队列.若为完全二叉树,则层序遍历时得到的肯定是一个连续的不包含空指针的序列.如果序列中出现了空指针，则说明不是完全二叉树。22特别讨论：若已知先序/后序遍历结果和中序遍历结果，能否“恢复”出二叉树？【严题集6.31④】

证明：由一棵二叉树的先序序列和中序序列可唯一确定这棵二叉树。

例：已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG

和DECBHGFA，请画出这棵二叉树。分析：①由后序遍历特征，根结点必在后序序列尾部（即A）；②由中序遍历特征，根结点必在其中间，而且其左部必全部是左子树子孙（即BDCE），其右部必全部是右子树子孙（即FHG）；③继而，根据后序中的DECB子树可确定B为A的左孩子，根据HGF子串可确定F为A的右孩子；以此类推。23中序遍历：BDCEAFHG

后序遍历：DECBHGFA（BDCE）（FHG）ABF

（DCE）

（HG）CDEGHABBFF24问：用二叉链表法（l_child,r_child）存储包含n个结点的二叉树，结点的指针区域中会有多少个空指针？分析：用二叉链表存储包含n个结点的二叉树，结点必有2n个链域（见二叉链表数据类型说明）。 最坏情况：除根结点外，二叉树中每一个结点有且仅有一个双亲（直接前驱），所以只会有n－1个结点的链域存放指针，指向非空子女结点（即直接后继）。思考：二叉链表空间效率这么低，能否利用这些空闲区存放有用的信息或线索？——我们可以用它来存放当前结点的直接前驱和后继等线索，以加快查找速度。所以，空指针数目＝2n－(n-1)=n+1个。n+125二、线索二叉树（ThreadedBinaryTree）普通二叉树只能找到结点的左右孩子信息，而该结点的直接前驱和直接后继只能在遍历过程中获得。若将遍历后对应的有关前驱和后继预存起来，则从第一个结点开始就能很快“顺藤摸瓜”而遍历整个树了。两种解决方法增加两个域：fwd和bwd；利用空链域（n+1个空链域）存放前驱指针存放后继指针如何预存这类信息？例如中序遍历结果：BDCEAFHG，实际上已将二叉树转为线性排列，显然具有唯一前驱和唯一后继！可能是根、或最左（右）叶子26规定：1）若结点有左子树，则lchild指向其左孩子；否则，lchild指向其直接前驱(即线索)；2）若结点有右子树，则rchild指向其右孩子；否则，rchild指向其直接后继(即线索)

。为了避免混淆，增加两个标志域，如下图所示：lchildLTagdataRTagrchild约定:当Tag域为0时,表示正常情况;当Tag域为1时,表示线索情况.27有关线索二叉树的几个术语：

线索链表：用前页结点结构所构成的二叉链表线索：指向结点前驱和后继的指针线索二叉树：加上线索的二叉树（图形式样）线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程注：在线索化二叉树中，并不是每个结点都能直接找到其后继的，当标志为0时，则需要通过一定运算才能找到它的后继。28dataAGEIDJHCFBltag0011110101rtag0001010111AGEIDJHCFB例1：带了两个标志的某先序遍历结果如表所示，请画出对应二叉树。29ABCGEIDHFroot悬空？悬空？解：该二叉树中序遍历结果为:

H,D,I,B,E,A,F,C,G所以添加线索应当按如下路径进行：例2：画出以下二叉树对应的中序线索二叉树。为避免悬空态，应增设一个头结点30对应的中序线索二叉树存储结构如图所示：00A00C00B11E11F11G00D11I11H注：此图中序遍历结果为:H