软件技术基础树

软件技术基础树本章要求1.基本要求（1）掌握树的术语，熟练掌握二叉树的基本概念和性质；掌握树、森林与二叉树之间的转换方法；掌握二叉树的顺序、链式存储结构以及类型定义；掌握建立链式存储结构的二叉树的算法。（2）熟练掌握二叉树的深度优先递归遍历算法及应用，了解广度优先遍历的方法；了解由遍历序列恢复二叉树的方法；了解线索二叉树的概念。（3）掌握哈夫曼树的概念和构造方法，了解哈夫曼编码的概念。（4）掌握二叉排序树的概念和构造二叉排序树的方法，了解删除结点的方法，了解在哪些方面可以应用二叉排序树。2.重点、难点重点：二叉树的性质，建立和遍历二叉树的算法及遍历算法的应用。哈夫曼树的概念、构造及应用。二叉排序树的概念和构造方法。难点：二叉树的建立算法，遍历算法的应用，构造哈夫曼编码，二叉排序树中删除结点的方法。23赌王家族6.1树的基本概念树(Tree)是n(n≥0)个结点的有限集合T。

若n=0时称为空树，否则：(1)有且只有一个特殊的结点时称为树的根(Root)结点；(2)若n>1时，其余的结点被分为m(m>0)个互不相交的子集T1,T2,T3…Tm，其中每个子集本身又是一棵树，称其为根的子树(Subtree)。

这是树的递归定义，即用树来定义树，而只有一个结点的树必定仅由根组成。4树的基本术语(1)结点(node)：包含一个数据元素及若干指向其他结点的分支信息。(2)结点的度(degree)、树的度：结点所拥有的子树的棵数称为结点的度。树中结点度的最大值称为树的度。

如图6-1(b)中结点A的度是3，结点B的度是2，结点M的度是0，树的度是3。AABDCEGFHIMJNKL(a)只有根结点(b)一般的树5图6-1树的示例形式(3)

叶子(left)结点、非叶子结点

树中度为0的结点，即无后继的结点，称为叶子结点(或终端结点)。度不为0的结点称为非叶子结点(或非终端结点或分支结点)。除根结点外，分支结点又称为内部结点。如图中结点F、H、I、J、K、L、M、N是叶子结点，而所有其它结点都是分支结点。6ABDCEGFHIMJNKL7(4)

孩子结点、双亲结点、兄弟结点一个结点的直接后继称为该结点的孩子结点(child)或子结点；相应地，一个结点的直接前趋称为该结点的双亲结点(parent)或父结点。同一双亲结点的所有子结点互称为兄弟结点。如图中结点B、C、D是结点A的子结点，而结点A是结点B、C、D的父结点；类似地结点E、F是结点B的子结点，结点B是结点E、F的父结点。如图中结点B、C、D是兄弟结点；结点E、F是兄弟结点。ABDCEGFHIMJNKL（5）层次、堂兄弟结点规定树中根结点的层次为1，其余结点的层次等于其双亲结点的层次加1。若某结点在第l(l≥1)层，则其子结点在第l+1层。双亲结点在同一层上的所有结点互称为堂兄弟结点。如图6-1(b)中结点E、F、G、H、I、J。（6）树的深度(或高度)：树中结点的最大层次值，又称为树的深度，如图6-1(b)中树的深度为4。8ABDCEGFHIMJNKL第1层第2层第3层第4层(7)结点的（层次）路径、祖先、子孙从根结点开始，到达某结点p所经过的所有结点成为结点p的层次路径(有且只有一条)。结点p的层次路径上的所有结点（p除外）称为p的祖先。以某一结点为根的子树中的任意结点称为该结点的子孙结点。9ABDCEGFHIMJNKL（8）有序树和无序树对于一棵树，若其中每一个结点的子树（若有）具有一定的次序，则该树称为有序树，否则称为无序树。例如：若T1，T2为有序树，它们是两棵不同的树；若T1，T2为无序树，它们是两棵相同的树。ACBABC10（9）森林(forest)：

m(m≥0)棵互不相交的树的集合。

显然，若将一棵树的根结点删除，剩余的子树就构成了森林。11ABDCEGFHIMJNKL12树的表示形式倒悬树。是最常用的表示形式，如图6-1(b)。ABDCEGFHIMJNKL图6.1(b)一般的树圆圈表示结点，结点的名字可写在圆圈内或圆圈旁。连线表示结点之间的关系13树的表示形式嵌套集合:是一些集合的集体，对于任何两个集合，或者不相交，或者一个集合包含另一个集合。右图是图6-1(b)树的嵌套集合形式。嵌套集合形式HIJDFBKLECMNGA圆圈表示结点圆圈的相互包含表示结点之间的关系。ABDCEGFHIMJNKL图6.1(b)一般的树14树的表示形式广义表形式(A(B,C,D))(A(B(E,F),C(G),D(H,I,J)))(A(B(E(K,L),F),C(G(M,N)),D(H,I,J)))括号表示结点括号的相互包含表示结点间的关系。ABDCEGFHIMJNKL图6.1(b)一般的树15树的表示形式目录表示凹入的线条表示结点线条的长短表示结点间的关系，长线条包含短线条。ABCDEFKL…………ABDCEGFHIMJNKL图6.1(b)一般的树16树的存储结构顺序存储顺序存储时，首先必须对树形结构的结点进行某种方式的线性化，使之成为一个线性序列，然后存储。链式存储链式存储时，使用多指针域的结点形式，每一个指针域指向一棵子树的根结点。由于树的分支数不固定，很难给出一种固定的存储结构，通常采用二叉树的形式存储树。6.2二叉树的定义及其性质二叉树的定义我们把满足以下两个条件的树形结构叫做二叉树（binarytree）：（1）每个结点的度都不大于2；（2）每个结点的孩子结点次序不能任意颠倒。由此定义可以看出，一个二叉树中的每个结点只能含有0，1或2个孩子，并且每个孩子有左右之分。

位于左边的孩子叫做左孩子

位于右边的孩子称为右孩子17二叉树的基本形态二叉树有5种基本形态，如图6-3所示。AAAA(a)(b)(c)(d)(e)(a)空二叉树(b)单结点二叉树(c)右子树为空(d)左子树为空(e)左、右子树都不空图6-3二叉树的基本形态1819二叉树与一般树型结构的主要区别树形结构中使用的术语如父母（双亲或前件，前趋）、子女（后件，后继）、祖先、子孙、兄弟和路径等在二叉树中仍然可以沿用，但值得注意的是，二叉树并非一般树形结构的特殊形式，它们属于两种不同的数据结构。

二叉树与一般树型结构的主要区别在于：

（1）二叉树中每个非空结点最多只有两个子女，而一般的树形结构中每个非空结点可以有多个子女；

（2）二叉树中结点的子树要区分左子树和右子树，即使在结点只有一棵子树的情况下也要明确指出是左子树还是右子树。而树则不区分。

二叉树与一般树型结构的主要区别为什么说二叉树不等同于度为2的有序树？答：如果树的根结点只有一棵子树，那么对有序树而言，它就是一个“独生子”，无次序可分，但对二叉树而言，必须明确区分它是根的左子树还是根的右子树，两种情况将构成不同的二叉树。2021性质1：在非空二叉树中，第i层上至多有2i-1个结点(i≥1)。证明：用数学归纳法证明。

1.当i=1时：只有一个根结点，21-1=20=1，命题成立。

2.现假设对i>1时，处在第i-1层上至多有2(i-1)-1个结点。

3.由归纳假设知，第i-1层上至多有2i-2个结点。由于二叉树每个结点的度最大为2，故在第i层上最大结点数为第i-1层上最大结点数的2倍。即2×2i-2＝2i-1

证毕二叉树的性质22二叉树的性质性质2：深度为k的二叉树至多有2k-1个结点（k≥1)。证明：深度为k的二叉树的最大的结点数为二叉树中每层上的最大结点数之和。由性质1知，二叉树的第1层、第2层⋯第k层上的结点数至多有：20、21…2k-1。∴总的结点数至多有：20+21+

…+2k-1=2k-1

证毕23二叉树的性质性质3：对任何一棵二叉树，若其叶子结点数为n0，度为2的结点数为n2，则n0=n2+1。证明：设二叉树中度为1的结点数为n1，二叉树中总结点数为N，因为二叉树中所有结点均小于或等于2，则有：N=n0+n1+n2设B为二叉树中的分支总数，除根结点外，其余每个结点都有唯一的一个进入分支,则有：N=B+1。二叉树中的分支都是由度为1和2的结点发出，所以分支数目为：

∴B＝n1+2n2

整理可得：

N=B+1=n1+2n2+1∴n0+n1+n2=n1+2n2+1

即n0=n2+1

证毕满二叉树满二叉树一棵深度为k且有2k-1个结点的二叉树称为满二叉树(FullBinaryTree)。

如图6-4(a)就是一棵深度为4的满二叉树。24894101151213614157213图6-4(a)满二叉树25满二叉树满二叉树的特点：基本特点是每一层上的结点数总是最大结点数。满二叉树的所有的分支结点都有左、右子树。可对满二叉树的结点进行连续编号，若规定从根结点开始，按“自上而下、自左至右”的原则进行。图6-4(a)中满二叉树的顺序表示为（1,2,3,4,5,6,7,…,14,15）图6-4(a)满二叉树89410115121361415721326完全二叉树完全二叉树(CompleteBinaryTree)：

如果深度为k，由n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应，该二叉树称为完全二叉树。或深度为k的满二叉树中编号从1到n的前n个结点构成了一棵深度为k的完全二叉树，其中2k-1

≤n≤2k-1。完全二叉树是满二叉树的一部分，而满二叉树是完全二叉树的特例。894115211267310136245完全二叉树非完全二叉树567421327二叉树的性质性质4：具有n个结点的完全二叉树的深度为：㏒2n+1。其中x表示不大于x的最大整数，x

表示不小于x的最小整数。证明：假设n个结点的完全二叉树的深度为k

则根据性质2，k-1层满二叉树结点总数为：n1=2k-1-1；k层满二叉树结点总数为：n2=2k-1；

显然n1<n≤n2，

进一步n1+1≤n<n2+1，即2k-1≤n<2k取对数得：k-1≤㏒2n<k因为k是整数。

∴k=㏒2n+1

证毕28二叉树的性质性质5：若对一棵有n个结点的完全二叉树(深度为㏒2n

+1)的结点按层序（从第1层到第㏒2n+1层)自左至右进行编号（从1开始）,则对于编号为i（1≤i≤n)的结点：⑴若i=1：则序号为i的结点是二叉树的根，无双亲结点；

若i>1，则序号为i的结点的双亲结点序号是i/2

。⑵若2i>n，则序号为i的结点无左孩子；

若2i≤n，则序号为i的结点的左孩子的序号为2i。⑶若2i+1>n，则序号为i的结点无右孩子；

若2i+1≤n，则序号为i的结点的右孩子的序号为2i+1。29可以用归纳法证明其中的（2）和（3）：当i=1时，由完全二叉树的定义知，如果2i=2≤n，说明二叉树中存在两个或两个以上的结点，所以其左孩子存在且序号为2；反之，如果2i=2>n，说明二叉树中不存在序号为2的结点，其左孩子不存在。同理，如果2i+1=3≤n，则说明其右孩子存在且序号为3，如果2i+1=3>n，则二叉树中不存在序号为3的结点，其右孩子不存在。现假设对于编号为j(1≤j≤i)的结点，(2)和(3)成立。即：当2j≤n时，其左孩子编号是2j；当2j>n时，其左孩子不存在。当2j+1≤n时，其右孩子编号是2j+1；当2j+1>n时，其右孩子不存在。21330当i=j+1时，由完全二叉树的定义知，若其左孩子结点存在，则其左孩子结点的编号一定等于编号为j的右孩子的编号加1，即其左孩子的编号为：

(2j+1)+1=2(j+1)=2i如图6-5所示，且有2i≤n。相反，若2i>n，则左孩子结点不存在。

同样地，若序号为i的结点的右孩子结点存在，则其右孩子的编号为：2i+1，且有2i+1≤n。相反，若2i+1>n，则左孩子结点不存在。结论(2)和(3)得证。jj+12j2j+12j+22j+3j/2(a)j和j+1结点在同一层j+12j+22j+3j2j2j+1……(b)i和i+1结点不在同一层图6-5完全二叉树中结点i和i+1的左右孩子31再由(2)和(3)来证明(1)。当i=1时，显然编号为1的是根结点，无双亲结点。当i>1时，设编号为i的结点的双亲结点的编号为m，若编号为i的结点是其双亲结点的左孩子，则由(2)有：i=2m，即m=i/2

；若编号为i的结点是其双亲结点的右孩子，则由(3)有：i=2m+1，即m=(i-1)/2

；∴当i>1时，其双亲结点的编号为i/2

。

证毕二叉树的存储结构1顺序存储结构顺序存储时，首先必须对树形结构的结点进行某种方式的线性化，使之成为一个线性序列，然后存储。这种存储结构适用于完全二叉树。用一组地址连续的存储单元依次“自上而下、自左至右”存储完全二叉树的数据元素。3233对于完全二叉树上编号为i的结点元素存储在一维数组的下标值为i-1的分量中，如图(c)所示。对于一般的二叉树，将其每个结点与完全二叉树上的结点相对照，存储在一维数组中，如图(d)所示。abcdhiejklfg(a)完全二叉树(b)非完全二叉树abcdefgh123

456789101112

abcdefghijkl

(c)完全二叉树的顺序存储形式1234567891011abc

de@h@@

f

g(d)非完全二叉树的顺序存储形式@@@二叉树的顺序存储结构利用以上表示方法，可以给出一般二叉树的顺序存储结构的C语言描述如下：

#define maxsize1024;

typedef int datatype;

typedef struct

{

datatypedata[maxsize];//存放二叉树的向量

int last; //最后一个结点的下标

}sequenlist;

34二叉树的存储结构：顺序存储结构最坏的情况下，一个深度为k、且只有k个结点的、单支二叉树需要长度为2k-1的一维数组。DCAB35@@@@@@@@@@@A@B@@@C@@@@@@@D36链式存储结构2链式存储结构

设计不同的结点结构可构成不同的链式存储结构。(1)结点的类型及其定义①二叉链表结点。有三个域：一个数据域，两个分别指向左右子结点的指针域，如图6-7(a)所示。

typedefchardatatype；

typedefstruct

node{

datatypedata；

structnode*lchild，*rchild；

}bitree；

bitree*root;//指向根结点的头指针当二叉树为空时，则root==NULL。若结点的某个孩子不存在，则相应的指针域为空。二叉链表中，如果有n个结点，则有n+1个指针域为空。37链式存储结构②三叉链表结点。除二叉链表的三个域外，再增加一个指针域，用来指向结点的父结点，如图6-7(b)所示。typedefstructBTNode3{datatypedata;structBTNode3*lchild,*rchild,*parent;}BTNode3;lchilddatarchildlchilddatarchildparent(a)二叉链表结点(b)三叉链表结点图6-7链表结点结构形式38链式存储结构(2)二叉树的链式存储形式例有一棵一般的二叉树，如图6-8(a)所示。以二叉链表和三叉链表方式存储的结构图分别如图6-8(b)、6-8(c)所示。图6-8二叉树及其链式存储结构(a)二叉树afedcbg(c)三叉链表

a⋀⋀

b⋀c⋀

d⋀e⋀f⋀⋀g⋀(b)二叉链表

a⋀

b⋀c⋀

d⋀e⋀g⋀⋀f⋀39二叉树建立（二叉链表的建立）算法的基本思想1）按照结点的序号，依次输入结点信息，若输入的结点不是虚结点，则建立一个新结点。2）若新结点是第1个结点，则令其为根结点，否则将新结点作为孩子链接到它的双亲结点上。3）如此反复进行，直到输入结束标志“＃”为止。adcb输入abc@@@d#输入：按照二叉树的层次顺序依次输入结点信息40二叉树建立（二叉链表的建立）adcb输入abc@@@d#01234队列q：rearfront^sch^^sch?=‘@’chq[1].data=aq[1].lchild=^q[1].rchild=^rootrearrearq[2].data=bq[2].lchild=^q[2].rchild=^q[1].lchild=schchrearq[3].data=cq[3].lchild=^q[3].rchild=^q[1].rchild=sfrontchrearq[4]=^q[2].lchild=s二叉树的建立算法bitree*CREATREE()

/*建立二叉树函数，函数返回指向根结点的指针*/

{

char ch；/*结点信息变量*/

bitree*Q[maxsize];

//设置指针类型数组来构成队列

int front,rear;

/*队头和队尾指针变量*/

bitree*root,*s;

/*根结点指针和中间指针变量*/

root=NULL;

/*二叉树置空*/

front=1;rear=0;/*设置队列指针变量初值，向量下标为0的空间未使用*/

/*以上为初始化*/41while(ch=getchar()!=‘#’)/*输入一个字符，当不是结束符时执行以下操作*/

{s=NULL;

if(ch!=‘@’)/*@表示虚结点，当不是虚结点则建立新结点*/

{s=(bitree*)malloc(sizeof(bitree));

s->data=ch;s->lchild=NULL;s->rchild=NULL;

}

rear++;/*队尾指针增1，指向新结点地址应存放的单元*/

Q[rear]=s;/*将新结点地址入队或虚结点指针NULL入队*/

if(rear==1)root=s;/*输入的第一个结点作为根结点*/

else{if(s&&Q[front])/*孩子和双亲结点都不是虚结点*/

{if(rear%2==0)Q[front]->lchild=s;/*新结点是左孩子*/

elseQ[front]->rchild=s;}/*新结点是右孩子*/

if(rear%2==1)

front++;

/*结点*Q[front]的两个孩子处理完毕，出队列*/}

}

returnroot;/*返回根指针*/

}/*CREATREE*/426.3遍历二叉树及其应用遍历二叉树(TraversingBinaryTree)：是指按指定的规律对二叉树中的每个结点访问一次且仅访问一次。

所谓访问是指对结点做某种处理。如：输出信息、修改结点的值等。

为什么需要遍历二叉树？二叉树是一种非线性结构，通过遍历将二叉树中的结点访问一遍，得到访问结点的顺序序列，故遍历的目的在于将非线性化结构变成线性化的访问序列。遍历方式：深度优先遍历广度优先遍历4344深度优先遍历二叉树若以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，则有六种遍历方案：DLR、LDR、LRD、DRL、RDL、RLD。若规定先左后右，则只有前三种情况三种情况，分别是：DLR——先(根)序遍历。LDR——中(根)序遍历。LRD——后(根)序遍历。

对于二叉树的遍历，分别讨论递归遍历算法和非递归遍历算法。递归遍历算法具有非常清晰的结构，但初学者往往难以接受或怀疑，不敢使用。实际上，递归算法是由系统通过使用栈来实现控制的。而非递归算法中的控制是由设计者定义和使用栈来实现的。DataLchildRchild二叉树结点的基本结构45中序遍历二叉树算法6.3中序遍历算法。voidinorder(bitree*p)//中序遍历二叉树，p指向二叉树的根结点

{if(p!=NULL) //二叉树p非空，则执行以下操作

{inorder(p->lchild);//中序遍历左子树

printf(“%c”,p->data);//访问p所指结点

inorder(p->rchild);//中序遍历右子树

}

}中序遍历的过程：从二叉树的根结点开始，向树的左下方移动，直到遇到空结点为止。然后访问空结点的父结点。接着继续遍历该结点的右子树，如果右子树没有子树可以遍历，那么继续遍历上一层最后一个未被访问的结点。46中序遍历结果A/B*C*D+E“表达式的中缀形式”调用inorder根结点的值动作1+2*3*4/5A6NULL5Aprintf7NULL4/printf8B9NULL8Bprintf10NULL3*printf11C12NULL11Cprintf13NULL+**/AEDCB12345678910111213141516171819调用inorder根结点的值动作2*printf14D15NULL14Dprintf16NULL1+printf17E18NULL17Eprintf19NULL算法6.3中序遍历算法。voidinorder(bitree*p)

{if(p!=NULL)

{inorder(p->lchild);

printf(“%c”,p->data);

inorder(p->rchild);

}

}47先序遍历二叉树算法6.2先序遍历算法。

voidpreorder(bitree*p)//先序遍历二叉树，p指向二叉树的根结点

{if(p!=NULL) //二叉树p非空，则执行以下操作

{printf(“%c”,p->data);//访问p所指结点

preorder(p->lchild); //先序遍历左子树

preorder(p->rchild); //先序遍历右子树

}

}先序遍历的过程：先访问根结点，然后访问左分支上遇到的每一个结点。继续这一过程，知道遇到空结点为止。这时，返回到最近的有右儿子的祖先结点，并从该结点的右儿子开始继续遍历。48先序(前序，preorder)遍历先序遍历结果序列为+**/ABCDE“表达式的前缀形式”+**/AEDCB49后序（postorder）遍历后序遍历的过程：从根结点开始，先访问结点的左右儿子，再对该结点进行访问。这就意味着结点的儿子将在该结点之前输出。算法6.4后序遍历算法。

voidpostorder(bitree*p)//后序遍历二叉树，p指向二叉树的根结点

{if(p!=NULL)//二叉树p非空，则执行以下操作

{postorder(p->lchild); //后序遍历左子树

postorder(p->rchild); //后序遍历右子树

printf("%c",p->data); //访问p所指结点

}

}50后序(postorder)遍历后序遍历结果序列为AB/C*D*E+“表达式的后缀形式”+**/AEDCB51非递归遍历方法遍历二叉树的算法中基本操作是访问结点，因此，无论是哪种次序的遍历，对有n个结点的二叉树，其时间复杂度均为O(n)。递归遍历算法的特点是结构紧凑、清晰，但是运行效率较低。仿照递归遍历算法执行过程中栈的状态变化，可以直接写出相应的非递归遍历算法。以中序遍历为例，在遍历左子树之前，先把根结点入栈，当左子树遍历结束后，从栈中弹出并访问，再遍历右子树。52非递归遍历方法：中序优先算法流程图top：栈顶指针算法思想：中序遍历T所指的二叉树，s为存储二叉树结点指针的工作栈。Step1.[初始化]置栈s为空，设置临时指针变量p指向二叉树的根结点；Step2.[判定p==NULL]若p==NULL，则执行Step4；Step3.[P进栈]将p指针入栈，然后置p=p->lchild，返回Step2；Step4.[取栈顶元素，并退栈]若栈s为空，则算法结束，否则，将栈顶元素置指针变量p；Step5.[访问结点p]访问结点p，然后置p=p->rchild，并返回Step2。53非递归遍历方法：中序优先输出序列为：DBACABDC栈S的变化情况BACD算法流程图top：栈顶指针;p:临时指针变量中序遍历非递归算法voidinorder(BiTree*T){ SqStack*S;

BiTree*P=T; InitStack(S);/*顺序栈初始化*/ while(P!=NULL||!Empty(S))

{

if(P!=NULL)

{

Push(S,P);/*根结点入栈*/

P=P->lchild;/*遍历左子树*/}else{

Pop(S,P);/*左子树遍历结束，出栈*/

printf("%c",P->data);

P=P->rchild;/*遍历右子树*/} }}54非递归遍历方法：中序优先算法复杂度：假定二叉树T有n个结点，每个结点都要入栈和出栈一次。因此，入栈和出栈都要执行n次，对结点的访问当然也需执行n次。这样，中序遍历二叉树算法的时间复杂度为O(n)。同理，只要改变对结点的访问位置，就可以容易地写出先序遍历二叉树的非递归算法。二叉树后序遍历的非递归算法要复杂一些，每个结点都要经过进栈—出栈—进栈—出栈这样两个重复过程。第一次出栈是为了能访问右子树，第二次出栈才是访问结点本身。5556广度优先（层次）遍历二叉树广度优先（层次）遍历二叉树，是从根结点开始遍历，按层次次序“自上而下，从左至右”访问树中的各结点。在上层中先被访问的结点，它的下层孩子也必然先被访问，因此在这种遍历算法的实现时，需要使用一个队列。遍历思想：在遍历进行之前，先把二叉树的根结点的存储地址入队然后依次从队列中出队结点的存储地址，每出队一个结点的存储地址则对该结点进行访问然后依次将该结点的左孩子和右孩子的存储地址入队，如此反复，直到队空为止。二叉树的广度优先遍历实例地址入队队列为空，算法结束。输出序列为：A,B,C,D,E,F,G60bitree *Q[maxsize];/*设置指针类型数组来构成队列*/voidLayer(bitree*p)/*层次遍历二叉树，p指向二叉树的根结点*/{bitree *s;if(p!=NULL)

{rear=1;/*队尾指针置初值*/front=0;/*队头指针置初值*/Q[rear]=p;/*根结点入队*/while(front<rear)/*当队非空时,执行以下操作*/

{front++;s=Q[front];/*从队列中出队队头结点*/

printf(“%c”,s->data);/*访问出队结点*/if(s->lchild!=NULL)/*s所指结点的左孩子结点入队*/{rear++;Q[rear]=s->lchild;}if(s->rchild!=NULL)/*s所指的右孩子结点入队*/

{rear++;Q[rear]=s->rchild;}

}//endwhile

}}从遍历序列恢复二叉树先序、中序和后序遍历序列的特点先序遍历序列：第一个结点必然是二叉树的根结点；其余结点可分割为左子树和右子树两部分；对左右子树，可以进行类似的分析中序遍历序列：已知的根结点将中序序列分割为两个子序列，根结点左面的子序列是左子树的中序序列，而在根结点右边的子序列是右子树的中序序列，以此类推后序遍历序列：最后一个结点是根结点；其余结点可以分割为左子树和右子树两部分，以此类推61从遍历序列恢复二叉树可知，对于一个二叉树，由其先序或后序遍历序列可以确定根结点；若已知根结点，则可以利用中序遍历序列确定其左子树和右子树。按照这一思路，可以对这颗二叉树的左子树和右子树再分别确定根结点和左、右子树。重复以上操作，便可以唯一地确定一颗二叉树。先序和后序遍历序列起着相同的作用，都是用来确定根结点。先序和中序遍历序列（或者后序和中序遍历序列）便可以唯一地确定一颗二叉树。先序和后序遍历序列的组合是不可取的。6263例：由先序序列{ABHFDECKG}和中序序列{HBDFAEKCG}恢复二叉树的过程。64从遍历序列恢复二叉树（先序和中序遍历序列）datatypepreod[maxsize]，inod[maxsize];bitree*BPI(datatypepreod[],datatypeinod[],inti,intj,intk,intl)

//i,j,k,l分别是要构造二叉树的先序和中序序列数组的起始和终点下标

{intm;bitree*p;

p=malloc(sizeof(bitree));/*构造根结点*/p->data=preod[i];m=k;while(inod[m]!=preod[i])/*查找根结点在中序序列中的位置*/m++;if(m==k)p->lchild=NULL;/*对左子树进行构造*/

elsep->lchild=BPI(preod,inod,i+1,i+m-k,k,m-1);

if(m==l)p->rchild=NULL;/*对右子树进行构造*/elsep->rchild=BPI(preod,inod,i+m-k+1,j,m+1,l);

return(p);}65二叉树遍历算法的应用1统计二叉树的叶子结点数(后序遍历)intcount=0;//static静态存储单元intcountleaf(bitree*p)

{if(p!=NULL)

{

count=countleaf(p->lchild);

/*对左子树上的叶子结点计数*/

count=countleaf(p->rchild);

/*对右子树上的叶子结点计数*/

if((p->lchild==NULL)&&(p->rchild==NULL))

count=count+1;

}returncount;}请考虑如何统计度为1的结点数，度为2的结点数。66二叉树遍历算法的应用2统计二叉树中度为2的结点数二叉树中2度结点数的递归定义为①当T为空或为叶子时,以T为根的二叉树的2度结点数为0;②当T是2度结点时,以T为根的二叉树的2度结点数为T的左右子树中2度结点数这和再加上T结点本身;③当T是1度结点时,以T为根的二叉树中2度结点数为T的左或子树中2度结点数之和.二叉树遍历算法的应用算法如下:intD2Nodes(BinTreeT){if(!T||!T->lchild&&!T->rchild)//T为空或是叶子return0;if(T->lchild&&T->rchild)//T是2度结点return1+D2Nodes(T->lchild)+D2Nodes(T->rchild);else//T是1度结点returnD2Nodes(T->lchild)+D2Nodes(T->rchild);}67二叉树遍历算法的应用2求二叉树深度intPostTreeDepth(BiTreep)//后序遍历求二叉树的高度递归算法{inthl,hr,max;if(p!=NULL)

{hl=PostTreeDepth(p->lchild);

hr=PostTreeDepth(p->rchild);max=hl>hr?hl:hr;return(max+1);

}

return(0);}68p左子树右子树hlhrHigh=max(hl,hr)+1二叉树遍历算法的应用3求二叉树结点个数intSize(BiTree*T){if(T==NULL)

return(0);else

return(1+Size(T->lchild)+Size(T->rchild));//二叉树的结点个数是根结点、左右子树结点个数之和}696.4线索二叉树二叉树的遍历运算是将二叉树中结点按一定规律线性化的过程。中序遍历：D,B,E,A,L,F,C,G可以从中找到任何一个结点的前趋和后继70716.4线索二叉树对二叉树本身（二叉链表作为存储结构），只能找到结点的左、右孩子信息，而不能直接得到结点在遍历序列中的前趋和后继信息。要得到这些信息可采用以下方法：将二叉树遍历一遍，在遍历过程中便可得到结点的前趋和后继，但这种动态访问浪费时间；给每个结点再增加两个域：一个指向结点的前趋，一个指向结点的后继，这样每个结点有4个域，有些浪费存储空间。充分利用二叉链表中的空链域(,C.Thornton)，将遍历过程中结点的前趋、后继信息保存下来。6.4线索二叉树在有n个结点的二叉链表中共有2n个链域，但只有n-1个有用的非空链域，其余n+1个链域是空的。我们可以利用剩下的n+1个空链域来存放遍历过程中结点的前趋和后继信息。现作如下规定：若结点有左子树，则其lchild域指向其左孩子，否则lchild域指向其前趋结点；若结点有右子树，则其rchild域指向其右孩子，否则rchild域指向其后继结点。726.4线索二叉树为了区分孩子结点和前趋、后继结点，为结点结构增设两个标志域，如下所示：73lchildltagdatartagrchildltag=0lchild域指示结点的左孩子ltag=1lchild域指示结点的前趋rtag=0rchild域指示结点的右孩子rtag=1rchild域指示结点的后继线索二叉树的结点结构C语言描述的线索二叉树的结点结构：

typedefintdatatype;

typedefstructBiThrNode

{

datatypedata;

structBiThrNode*lchild,*rchild;

intltag,rtag;

}BiThrNode;74线索二叉树的概念

线索：在这种存储结构中，指向前趋和后继结点的指针叫做线索。

线索链表：以这种结构组成的二叉链表作为二叉树的存储结构，叫做线索链表。线索化：对二叉树以某种次序进行遍历并且加上线索的过程叫做线索化。线索二叉树：线索化了的二叉树称为线索二叉树。7576中序遍历二叉树：dbace实线为指针（指向左右子树）虚线为线索（指向（遍历）前趋和（遍历）后继）aedcb0a00b11c01d11e1线索二叉树的二叉链表表示后继后继后继前趋前趋前趋若结点有左子树，则其lchild域指向其左孩子，否则lchild域指向其前趋结点；若结点有右子树，则其rchild域指向其右孩子，否则rchild域指向其后继结点。ltag=0lchild域指示结点的左孩子ltag=1lchild域指示结点的前趋rtag=0rchild域指示结点的右孩子rtag=1rchild域指示结点的后继lchildltagdatartagrchild线索二叉树的基本操作：线索化线索化本质上是将二叉链表中的空指针域填上相应结点的遍历前趋和后继结点的地址。前趋和后继的地址只能在动态的遍历过程中才能得到。因此，线索化的过程即为在遍历中修改空指针域的过程。不同的遍历次序线索化得到不同的线索二叉树：先序线索二叉树中序线索二叉树后序线索二叉树。7778线索二叉树的基本操作：线索化算法6.10建立中序线索二叉树

BiThrNode*pre=NULL;//指向结点p的前趋voidInThreading(BiThrNode*p){if(p!=NULL)

{InThreading(p->lchild);//线索化左子树

if(p->lchild==NULL)

{p->ltag=1;p->lchild=pre;}//置前趋线索

if(p->rchild==NULL)p->rtag=1;

if(pre!=NULL&&pre->rtag==1)//置后继线索pre->rchild=p;

pre=p；//保持pre指向p的前驱

InThreading(p->rchild);//线索化右子树}}在遍历的过程中，先遍历某结点，然后才会遍历其后继。因此，在遍历过程中修改指针时，遍历某结点时只修改其前趋的指针。它的后继要在遍历后继结点时再修改建立中序线索二叉树7980线索二叉树的基本操作2-(1).在中序(LDR)线索二叉树中查找结点的前趋若结点p的左子树为空，即p->ltag==1，则p->lchild直接指示了结点的前趋（黄色结点）；若结点p的左子树为非空，

即p->ltag==0，根据中序遍历的规律可知，结点p的前趋应是遍历其左子树时访问的最后一个结点，即左子树中最右下的结点。（绿色结点）

0a01b01c01d11e1中序遍历二叉树：bdaecf线索二叉树的基本操作中序线索二叉树中查找结点前趋BiThrNode*InPre(BiThrNode*p){

BiThrNode*pre,*q;

if(p->ltag==1)//左孩子为空

pre=p->lchild;//直接利用线索

else{//在p的左子树中查找最右下端的结点

for(q=p->lchild;q->rtag==0;q=q->rchild)

pre=q;}

return(pre);}81中序线索二叉树中查找结点前趋8283线索二叉树的基本操作2-(2).在中序(LDR)线索二叉树中查找结点的后继若结点p的右子树为空，即p->rtag==1，则p->rchild直接指示了结点的后继（黄色结点）；若结点p的右子树为非空，

即p->rtag==0，根据中序遍历的规律可知，结点p的后继应是遍历其右子树时访问的第一个结点，即右子树中最左下的结点。（绿色结点）

0a00b10c01d11f11e1中序遍历二叉树：dbaecf线索二叉树的基本操作算法6.11中序线索二叉树中查找结点后继。

BiThrNode*InOrderNext(BiThrNode*p)

{BiThrNode*q;

q=p->rchild;

if(p->rtag!=1)//右子树非空的情况{while(q->ltag==0)//q结点的左子树非空

q=q->lchild；}//查找q的最左下结点

return(q);

}//InOrderNext84中序线索二叉树中查找结点后继85线索二叉树的基本操作在先序(DLR)线索树中查找结点的后继若p的左子树非空，则p的左孩子结点即为p的后继；若p的左子树为空，右子树非空，则p的右孩子结点即为p的后继；右孩子为空，则p->rchild指针域所指的结点即为p的后继；If(p->ltag==0)q=p->lchild;elseq=p->rchild;86线索二叉树的基本操作在先序(DLR)线索树中查找结点的前趋若结点p为二叉树的根，则p的前趋为空；若p是其双亲结点的左孩子，或者p是其双亲结点的右孩子并且其双亲无左孩子，则p的前趋是其双亲结点；若p是双亲结点的右孩子，且双亲有左孩子，则p的前趋是其双亲的左孩子中按先序遍历时最后访问的那个结点。87线索二叉树的基本操作总结：在后序线索树中查找结点的后继在先序线索树中查找结点的前趋这两种情况需要知道双亲结点，适于采用带双亲指针的三叉链表。88线索二叉树的基本操作3．遍历中序线索二叉树首先，从二叉树的根结点开始，沿左子树找下去，一直找到ltag为1的结点（即叶子结点，也是线索化的第一个结点）。接着从该结点开始，依次查找中序序列的后继结点。算法6.12遍历中序线索二叉树voidInThredTraverse(BiThrNode*p){if(p!=NULL){while(p->ltag==0)p=p->lchild;//查找开始结点

do{

printf(“%c”,p->data);

p=InOrderNext(p);//在中序二叉树中查找后继结点

}while(p!=NULL)}}89O(n)906.5树和森林树的三种存储结构1.双亲表示法

树的每个结点(除根以外)都只有唯一的双亲。基于这一性质，可以用一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在链表中的位置。#defineMAXSIZE100typedefstruct//结点结构{

datatypedata;

intparent;//双亲位置域}PTNode；typedefstruct//树的结构{

PTNodenodes[MAXSIZE];intn;//结点数

}PTreeCAEDBFIGJH912

孩子（双亲）表示法把所有结点以单链表形式储存，同时以每个结点作为头结点，对其孩子结点另建立一个孩子链表。CAEDBFIGJH923.孩子兄弟表示法以二叉链表作树的存储结构，二叉链表中结点的两个指针域命名为child域和next域，分别指向该结点的最左孩子结点和右邻兄弟结点。CAEDBFIGJHCAEDBFIGH93树和二叉树间的转换将一棵树转换为二叉树的方法是：(1)在兄弟之间增加一条连线；(2)对每个结点，除了保留与其左孩子的连线外，除去与其它孩子之间的连线；(3)以树的根结点为轴心，将整个树顺时针旋转45度。CAEDBFIGHCAEDBFIGH94树和二叉树间的转换说明：(1)树中的任意一个结点都对应于二叉树中的一个结点。(2)对树中某个结点，其第一个孩子在二叉树中是相应结点的左孩子，其右兄弟结点在二叉树中是相应结点的右孩子。即在二叉树中，左分支上的各结点在原来的树中是父子关系，而右分支上的各结点在原来的树中是兄弟关系。(3)树的根没有兄弟，因此转换后的二叉树的根结点的右孩子必然为空。树和二叉树间的转换从一棵二叉树到树的转换规则是：(1)若结点X是双亲Y的左孩子，则把X的右孩子，右孩子的右孩子…都与Y用连线相连；（X的右孩子、右孩子的右孩子…是X的兄弟）(2)去掉原有的双亲到右孩子的连线。95CAEDBFIGHCAEDBFIGH96深林与二叉树之间的转换深林转化为二叉树的方法：（1）把每一棵树依次转化为二叉树；（2）将转换得到的二叉树的各个根视为兄弟并加上连线；（3）以第一棵树的根为轴，顺时针旋转45度。abcdefghiabcdefghiabcdefghiabcdefghijkjkjkjk深林与二叉树之间的转换说明：将森林F看作数的有序集F={T1,T2,…,TN}，它对应的二叉树为B(F)：（1）若N=0，则B(F)为空；（2）若N>0，二叉树B(F)的根为森林中第一棵树T1的根，B(F)的左子树为B({T11,T12,…,T1m})，其中T11,T12,…,T1m是T1的子树森林，B(F)的右子树是B({T2,T3,…,TN})。97二叉树转换成森林二叉树转换成森林规则：（1）从二叉树的根结点开始，沿右指针向下走，直到为空，途经的结点即位森林中每棵树的根结点，断开这些根结点与双亲的连线。（2）再利用二叉树转换成树的规则转换。98abcdefghiabcdefghijkjk树、二叉树、森林之间的转换996.7哈夫曼树及其应用哈夫曼树─即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。

在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称“熵编码法”,在这个技术中一段文字中的每个字母被一段不同长度的比特（Bit）所代替,每个字母按照其出现的可能性所获得的最佳比特数取决于熵），用于数据的无损压缩。一般用来压缩文本和程序文件。100基本概念路径：从一个祖先结点到子孙结点之间的分支构成这两个结点间的路径；路径长度：路径上的分支数目称为路径长度；树的路径长度：树根到树中每一个结点的路径长度之和。结点的权：根据应用的需要可以给树的结点赋权值(具有某种应用意义)；结点的带权路径长度：从根到该结点的路径长度与该结点权的乘积；101基本概念设路径长度用PL表示，则这两棵树的路径长度分别为：PL=0+1+1+2=4；PL=0+1+2+3=6；

102ABCDABCD103树的带权路径长度(WeightedPathLength,WPL)二叉树的带权(外部)路径长度是树的各叶子结点所带的权值wi

与该结点到根的路径长度li

的乘积的和。222444555777WPL=2*2+WPL=2*1+WPL=7*1+4*2+5*2+

4*2+5*3+5*2+2*3+7*2=367*3=464*3=35带权路径达到最小哈夫曼树的定义假设有n个权值(w1,w2,…,wn)，构造有n个叶子结点的二叉树，每个叶子结点有一个wi

作为它的权值。则带权路径长度WPL最小的二叉树称为哈夫曼树，又称最优二叉树。为了使WPL=wi

li最小，必须使wi

li最小，由于权值是确定的，所以只能调整叶子结点的路径长度li来使乘积最小。也就是说，当一个叶子结点的权值比较大时，应让其尽可能靠近根结点，这样就减少了路径长度，从而减少WPL的值。104二叉树的路径长度(a)WPL＝1×2＋1×2＋1×2＋1×2＝8；(b)WPL＝1×3＋1×3＋1×2＋1×1＝9。105abcd1111bacd1111结点具有相同权值，完全二叉树具有最小路径，是最优二叉树哈夫曼树(a)WPL＝2×2＋4×2＋5×2＋7×2＝36；(b)WPL＝2×3＋4×3＋5×2＋7×1＝35。106abcd2457bacd4257结点具有不同权值，完全二叉树不是最优二叉树哈夫曼树:不唯一性权值为w1,w2,…,wn

的n个叶子结点形成的二叉树，可以具有多种形态，其中能被称为哈夫曼树的二叉树并不是唯一的。如下图。(a)WPL=3×2＋4×2＋5×2＋7×2＝38；(b)WPL=3×3＋4×3＋5×2＋7＝38。107abcd3457abcd3457(a)(b)哈夫曼树的构造算法(1)根据给定的n个权值{w1,w2,…,wn}，构造具有n棵二叉树的森林F＝{T1,T2,…,Tn},其中Ti中只有一个权值为wi的根结点，左、右子树均为空。(2)在F中选取两棵根结点的权值为最小、次最小的树作为左、右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为左、右子树上根结点的权值之和。(3)在F中删除这两棵树，同时将新得到的二叉树加入F中。(4)重复(2)、(3)直到F中仅剩一棵树为止。这棵树就是哈夫曼树。108举例：哈夫曼树的构造过程109F:{7}{5}{2}{4}F:{7}{5}{6}F:{7}{11}初始合并{2}{4}6F:{18}116合并{5}{6}合并{7}{11}611187524752475247524举例：哈夫曼树的构造过程754267564211756421118用哈夫曼算法构造哈夫曼树的过程111哈夫曼树的构造一个有n个叶子结点的初始集合，要生成哈夫曼树共要进行n-1次合并，产生n-1个新结点。最终求得的哈夫曼树共有n+n-1=2n-1个结点，并且哈夫曼树中没有度为1的分支结点。我们常称没有度为1的结点的二叉树为严格二叉树。112哈夫曼树的构造实例权值为0.4、0.3、0.1、0.1、0.02、0.08的6个叶子结点A、B、C、D、E、F构造哈夫曼树，观察哈夫曼树的构造过程，如下图所示。w=

(40,30,10,10,2,8)113114AEBFCD4030101028（1）AEBFCD（2）10AEBFCD（3）1020AEBFCD（4）102030403010102840301010284030281020AEBFCD（5）102030604030281010A（6）6010040EBFCD10203030281010构造哈夫曼树算法中的数据结构#definen叶子数目

#definem2*n-1/*结点总数*/

typedefchardatatype;

typedefstruct

{

floatweight;

datatypedata;intlchild,rchild,parent;

}hufmtree;

hufmtreetree[m];115116哈夫曼树的构造算法VoidCreatHufman(hufmtreetree[]){inti,j,p1,p2;charch;//p1,p2表示最小权值和次最小权值