树与二叉树市公开课一等奖省赛课获奖课件

数据结构讲义

第6章树和二叉树树与二叉树第1页

树型结构是一类非常主要非线性结构。直观地，树型结构是以分支关系定义层次结构。树在计算机领域中也有着广泛应用，比如在编译程序中，用树来表示源程序语法结构；在数据库系统中，可用树来组织信息；在分析算法行为时，可用树来描述其执行过程等等。本章将详细讨论树和二叉树数据结构，主要介绍树和二叉树概念、术语，二叉树遍历算法。树和二叉树各种存放结构以及建立在各种存放结构上操作及应用等。树与二叉树第2页6.1

树基本概念1

树定义

树(Tree)是n(n≧0)个结点有限集合T，若n=0时称为空树，不然：⑴有且只有一个特殊称为树根(Root)结点；⑵若n>1时，其余结点被分为m(m>0)个互不相交子集T1,T2,T3…Tm，其中每个子集本身又是一棵树，称其为根子树(Subtree)。这是树递归定义，即用树来定义树，而只有一个结点树必定仅由根组成，如图6-1(a)所表示。

6.1.1

树定义和基本术语树与二叉树第3页2

树基本术语⑴

结点(node)：一个数据元素及其若干指向其子树分支。⑵

结点度(degree)

、树度：结点所拥有子树棵数称为结点度。树中结点度最大值称为树度。

图6-1树示例形式AABDCEGFHIMJNKL(a)

只有根结点(b)普通树树与二叉树第4页

如图6-1(b)中结点A度是3，结点B度是2，结点M度是0，树度是3。⑶

叶子(left)结点、非叶子结点：树中度为0结点称为叶子结点(或终端结点)。相对应地，度不为0结点称为非叶子结点(或非终端结点或分支结点)。除根结点外，分支结点又称为内部结点。如图6-1(b)中结点H、I、J、K、L、M、N是叶子结点，而全部其它结点都是分支结点。(内部结点?)⑷

孩子结点、双亲结点、弟兄结点

一个结点子树根称为该结点孩子结点(child)或子结点；对应地，该结点是其孩子结点双亲结点(parent)或父结点。树与二叉树第5页

如图6-1(b)中结点B、C、D是结点A子结点，而结点A是结点B、C、D父结点；类似地结点E、F是结点B子结点，结点B是结点E、F父结点。同一双亲结点全部子结点互称为弟兄结点。

如图6-1(b)中结点B、C、D是弟兄结点；结点E、F是弟兄结点。⑸

层次、堂弟兄结点

要求树中根结点层次为1，其余结点层次等于其双亲结点层次加1。若某结点在第l(l≧1)层，则其子结点在第l+1层。双亲结点在同一层上全部结点互称为堂弟兄结点。如图6-1(b)中结点G与结点E、F、H、I、J。树与二叉树第6页⑹

结点层次路径、祖先、子孙

从根结点开始，抵达某结点p所经过全部结点成为结点p层次路径(有且只有一条)。

结点p层次路径上全部结点（p除外）称为p祖先(ancester)。以某一结点为根子树中任意结点称为该结点子孙结点(descent)。⑺

树深度(depth)：树中结点最大层次值，又称为树高度，如图6-1(b)中树高度为4。⑻

有序树和无序树：对于一棵树，若其中每一个结点子树（若有）含有一定次序，则该树称为有序树，不然称为无序树。树与二叉树第7页⑼

森林(forest)：是m(m≧0)棵互不相交树集合。显然，若将一棵树根结点删除，剩下子树就组成了森林。3树表示形式⑴倒悬树。是最惯用表示形式，如图6-1(b)。⑵嵌套集合。是一些集合集体，对于任何两个集合，或者不相交，或者一个集合包含另一个集合。图6-2(a)是图6-1(b)树嵌套集合形式。⑶广义表形式。图6-2(b)是树广义表形式。⑷凹入法表示形式。见P120树表示方法多样化说明了树结构主要性。树与二叉树第8页图6-2树表示形式(a)

嵌套集合形式(b)广义表形式(A(B(E(K,L),F),C(G(M,N)),D(H,I,J)HIJDFBKLECMNGA树与二叉树第9页6.1.2

树抽象数据类型定义ADTTree{数据对象D：D是含有相同数据类型数据元素集合。数据关系R：若D为空集，则称为空树；

……基本操作：……}ADTTree详见p118~119。树与二叉树第10页6.2

二叉树6.2.1

二叉树定义1二叉树定义

二叉树(Binarytree)是n(n≥0)个结点有限集合。若n=0时称为空树，不然：⑴

有且只有一个特殊称为树根(Root)结点；⑵

若n>1时，其余结点被分成为二个互不相交子集T1,T2，分别称之为左、右子树，而且左、右子树又都是二叉树。由此可知，二叉树定义是递归。树与二叉树第11页

二叉树在树结构中起着非常主要作用。因为二叉树结构简单，存放效率高，树操作算法相对简单，且任何树都很轻易转化成二叉树结构。上节中引入相关树术语也都适合用于二叉树。2

二叉树基本形态二叉树有5种基本形态，如图6-3所表示。AAAA(a)(b)(c)(d)(e)(a)空二叉树(b)单结点二叉树(c)右子树为空(d)左子树为空(e)左、右子树都不空图6-3

二叉树基本形态树与二叉树第12页6.2.2

二叉树性质性质1：在非空二叉树中，第i层上至多有2i-1个结点(i≧1)。证实：用数学归纳法证实。当i=1时：只有一个根结点，21-1=20=1，命题成立。现假设对i>1时，处于第i-1层上至多有2(i-1)-1个结点。由归纳假设知，第i-1层上至多有2i-2个结点。因为二叉树每个结点度最大为2，故在第i层上最大结点数为第i-1层上最大结点数2倍。即2×2i-2＝2i-1

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

…+2k-1=2k-1证毕

性质3：对任何一棵二叉树，若其叶子结点数为n0，度为2结点数为n2，则n0=n2+1。证实：设二叉树中度为1结点数为n1，二叉树中总结点数为N，因为二叉树中全部结点均小于或等于2，则有：N=n0+n1+n2再看二叉树中分支数：树与二叉树第14页除根结点外，其余每个结点都有唯一一个进入分支，而全部这些分支都是由度为1和2结点射出。设B为二叉树中分支总数，则有：N=B+1

∴

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满二叉树。树与二叉树第15页894101151213614157213894101152112673(a)满二叉树(b)完全二叉树1362455674213(c)非完全二叉树图6-4特殊形态二叉树树与二叉树第16页满二叉树特点：基本特点是每一层上结点数总是最大结点数。满二叉树全部支结点都有左、右子树。可对满二叉树结点进行连续编号，若要求从根结点开始，按“自上而下、自左至右”标准进行。完全二叉树(CompleteBinaryTree)：假如深度为k，由n个结点二叉树，当且仅当其每一个结点都与深度为k满二叉树中编号从1到n结点一一对应，该二叉树称为完全二叉树。或深度为k满二叉树中编号从1到n前n个结点组成了一棵深度为k完全二叉树。其中2k-1≦

n≦2k-1

。树与二叉树第17页

完全二叉树是满二叉树一部分，而满二叉树是完全二叉树特例。完全二叉树特点：

若完全二叉树深度为k，则全部叶子结点都出现在第k层或k-1层。对于任一结点，假如其右子树最大层次为l，则其左子树最大层次为l或l+1。性质4：n个结点完全二叉树深度为：㏒2n

+1。

其中符号：x表示小于x最大整数。

x

表示大于x最小整数。证实：假设完全二叉树深度为k，则依据性质2及完全二叉树定义有：树与二叉树第18页2k-1-1<n≦2k-1

或

2k-1≦n<2k取对数得：k－1<㏒2n<k

因为k是整数。∴k=㏒2n

+1证毕性质5：若对一棵有n个结点完全二叉树(深度为㏒2n+1)结点按层（从第1层到第㏒2n

+1层)序自左至右进行编号,则对于编号为i（1≦i≦n)结点：⑴若i=1：则结点i是二叉树根，无双亲结点；不然，若i>1，则其双亲结点编号是

i/2

。⑵假如2i>n：则结点i为叶子结点，无左孩子；不然，其左孩子结点编号是2i。⑶假如2i+1>n：则结点i无右孩子；不然，其右孩子结点编号是2i+1。树与二叉树第19页

证实：用数学归纳法证实。首先证实⑵和⑶，然后由⑵和⑶导出⑴。当i=1时，由完全二叉树定义知，结点i左孩子编号是2，右孩子编号是3。若2>n，则二叉树中不存在编号为2结点，说明结点i左孩子不存在。若3>n，则二叉树中不存在编号为3结点，说明结点i右孩子不存在。现假设对于编号为j(1≦j≦i)结点，(2)和(3)成立。即：◆

当2j≦n：结点j左孩子编号是2j；当2j>n时，结点j左孩子结点不存在。树与二叉树第20页◆当2j+1≦n：结点j右孩子编号是2j+1；当2j+1>n时，结点j右孩子结点不存在。当i=j+1时，由完全二叉树定义知，若结点i左孩子结点存在，则其左孩子结点编号一定等于编号为j右孩子编号加1，即结点i左孩子编号为：(2j+1)+1=2(j+1)=2i如图6-5所表示，且有2i≦n。相反，若2i>n，则左孩子结点不存在。一样地，若结点i右孩子结点存在，则其右孩子编号为：2i+1，且有2i+1≦n。相反，若2i+1>n，则左孩子结点不存在。结论(2)和(3)得证。再由(2)和(3)来证实(1)。当i=1时，显然编号为1是根结点，无双亲结点。树与二叉树第21页当i>1时，设编号为i结点双亲结点编号为m，若编号为i结点是其双亲结点左孩子，则由(2)有：i=2m，即m=i/2；若编号为i结点是其双亲结点右孩子，则由(3)有：i=2m+1，即m=(i-1)

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

。证毕ii+12i2i+12i+22i+3└i/2┘(a)i和i+1结点在同一层i+12i+22i+3i2i2i+1……(b)i和i+1结点不在同一层图6-5完全二叉树中结点i和i+1左右孩子树与二叉树第22页6.2.3

二叉树存放结构1次序存放结构

二叉树存放结构类型定义：#defineMAX_SIZE100typedeftelemtypesqbitree[MAX_SIZE];用一组地址连续存放单元依次“自上而下、自左至右”存放完全二叉树数据元素。对于完全二叉树上编号为i结点元素存放在一维数组下标值为i-1分量中，如图6-6(c)所表示。对于普通二叉树，将其每个结点与完全二叉树上结点相对照，存放在一维数组中，如图6-6(d)所表示。树与二叉树第23页abcdhiejklfg(a)完全二叉树(b)非完全二叉树abcdefghØØØ123456789101112

abcdefghijkl

(c)完全二叉树次序存放形式1234567891011abcdeØhØ

Ø

fg(d)非完全二叉树次序存放形式图6-6二叉树及其次序存放形式树与二叉树第24页最坏情况下，一个深度为k且只有k个结点单支树需要长度为2k-1一维数组。2链式存放结构

设计不一样结点结构可组成不一样链式存放结构。(1)结点类型及其定义①二叉链表结点。有三个域：一个数据域，两个分别指向左右子结点指针域，如图6-7(a)所表示。typedefstructBTNode{ElemTypedata;structBTNode*Lchild,*Rchild;}BTNode,*BTree;树与二叉树第25页②三叉链表结点。除二叉链表三个域外，再增加一个指针域，用来指向结点父结点，如图6-7(b)所表示。typedefstructBTNode_3{ElemTypedata;structBTNode_3*Lchild,*Rchild,*parent;}BTNode_3;

LchilddataRchildLchilddataparentRchild(a)二叉链表结点(b)三叉链表结点图6-7链表结点结构形式树与二叉树第26页(2)二叉树链式存放形式

例有一棵普通二叉树，如图6-8(a)所表示。以二叉链表和三叉链表方式存放结构图分别如图6-8(b)、6-8(c)所表示。图6-8二叉树及其链式存放结构(a)二叉树afedcbg(c)三叉链表a⋀

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

a⋀

b⋀c⋀

d⋀e⋀g⋀⋀f⋀T树与二叉树第27页6.3

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

所谓访问是指对结点做某种处理。如：输出信息、修改结点值等。二叉树是一个非线性结构，每个结点都可能有左、右两棵子树，所以，需要寻找一个规律，使二叉树上结点能排列在一个线性队列上，从而便于遍历。二叉树基本组成：根结点、左子树、右子树。若能依次遍历这三部分，就是遍历了二叉树。树与二叉树第28页

若以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，则有六种遍历方案：DLR、LDR、LRD、DRL、RDL、RLD。若要求先左后右，则只有前三种情况三种情况，分别是：DLR——先(根)序遍历。LDR——中(根)序遍历。LRD——后(根)序遍历。对于二叉树遍历，分别讨论递归遍历算法和非递归遍历算法。递归遍历算法含有非常清楚结构，但初学者往往难以接收或怀疑，不敢使用。实际上，递归算法是由系统经过使用堆栈来实现控制。而非递归算法中控制是由设计者定义和使用堆栈来实现。树与二叉树第29页6.3.1

先序遍历二叉树1递归算法算法递归定义是：

若二叉树为空，则遍历结束；不然⑴访问根结点；⑵先序遍历左子树(递归调用本算法)；⑶先序遍历右子树(递归调用本算法)。树与二叉树第30页先序遍历递归算法voidPreorderTraverse(BTNode*T){if(T!=NULL){visit(T->data);/*访问根结点*/PreorderTraverse(T->Lchild);PreorderTraverse(T->Rchild);}}/*图6-8(a)二叉树，输出次序是：abccegf*/说明：visit()函数是访问结点数据域，其要求视详细问题而定。树采取二叉链表存放结构，用指针变量T来指向。树与二叉树第31页2非递归算法设T是指向二叉树根结点指针变量，非递归算法是：若二叉树为空，则返回；不然，令p=T；⑴访问p所指向结点；⑵q=p->Rchild，若q不为空，则q进栈；⑶p=p->Lchild，若p不为空，转(1)，不然转(4)；⑷退栈到p，转(1)，直到栈空为止。算法实现：树与二叉树第32页#defineMAX_NODE50voidPreorderTraverse(BTNode*T){BTNode*Stack[MAX_NODE],*p=T,*q;inttop=0;if(T==NULL)printf(“BinaryTreeisEmpty!\n”);else{do{visit(p->data);q=p->Rchild;if(q!=NULL)stack[++top]=q;p=p->Lchild;if(p==NULL){p=stack[top];top--;}}while(p!=NULL);}}树与二叉树第33页6.3.2

中序遍历二叉树1递归算法算法递归定义是：

若二叉树为空，则遍历结束；不然⑴中序遍历左子树(递归调用本算法)；⑵访问根结点；⑶中序遍历右子树(递归调用本算法)。树与二叉树第34页中序遍历递归算法voidInorderTraverse(BTNode*T){if(T!=NULL){InorderTraverse(T->Lchild);visit(T->data);/*访问根结点*/InorderTraverse(T->Rchild);}}

/*图6-8(a)二叉树，输出次序是：cbegdfa*/树与二叉树第35页2非递归算法设T是指向二叉树根结点指针变量，非递归算法是：若二叉树为空，则返回；不然，令p=T⑴若p不为空，p进栈，p=p->Lchild；⑵不然(即p为空)，退栈到p，访问p所指向结点；⑶p=p->Rchild，转(1)；直到栈空为止。算法实现：树与二叉树第36页#defineMAX_NODE50voidInorderTraverse(BTNode*T){BTNode*Stack[MAX_NODE],*p=T;inttop=0,bool=1;if(T==NULL)printf(“BinaryTreeisEmpty!\n”);else{do{while(p!=NULL){stack[++top]=p;p=p->Lchild;}if(top==0)bool=0;else{p=stack[top];top--;visit(p->data);p=p->Rchild;}}while(bool!=0);}}树与二叉树第37页6.3.3

后序遍历二叉树1递归算法算法递归定义是：

若二叉树为空，则遍历结束；不然⑴后序遍历左子树(递归调用本算法)；⑵后序遍历右子树(递归调用本算法)；⑶访问根结点。树与二叉树第38页后序遍历递归算法voidPostorderTraverse(BTNode*T){if(T!=NULL){PostorderTraverse(T->Lchild);PostorderTraverse(T->Rchild);visit(T->data);/*访问根结点*/

}}

/*图6-8(a)二叉树，输出次序是：cgefdba*/遍历二叉树算法中基本操作是访问结点，所以，不论是哪种次序遍历，对有n个结点二叉树，其时间复杂度均为O(n)。树与二叉树第39页6.3.4

层次遍历二叉树

层次遍历二叉树，是从根结点开始遍历，按层次次序“自上而下，从左至右”访问树中各结点。为确保是按层次遍历，必须设置一个队列，初始化时为空。设T是指向根结点指针变量，层次遍历非递归算法是：若二叉树为空，则返回；不然，令p=T，p入队；⑴队首元素出队到p；⑵访问p所指向结点；⑶将p所指向结点左、右子结点依次入队。直到队空为止。树与二叉树第40页#defineMAX_NODE50voidLevelorderTraverse(BTNode*T){BTNode*Queue[MAX_NODE],*p=T;intfront=0,rear=0;if(p!=NULL){Queue[++rear]=p;/*根结点入队*/while(front<rear){p=Queue[++front];visit(p->data);if(p->Lchild!=NULL)Queue[++rear]=p;/*左结点入队*/if(p->Rchild!=NULL)Queue[++rear]=p;/*左结点入队*/}}}树与二叉树第41页

如图6-9所表示二叉树表示表示式：(a+b*(c-d)-e/f)按不一样次序遍历此二叉树，将访问结点按先后次序排列起来次序是：其先序序列为：-+a*b-cd/ef其中序序列为：a+b*c-d-e/f其后序序列为：abcd-*+ef/-－/fe-dcb*a+图6-9

表示式(a+b*(c-d)-e/f)二叉树树与二叉树第42页已知二叉树(存放结构),能够确认先序遍历,中序遍历,后序遍历得到序列结果.若先序遍历(中序遍历,后序遍历)得到序列结果,能够确认二叉树形式?只有已知序遍历与中序遍历,或者中序遍历与后序遍历才能能够确认二叉树.(见练习p41t27,t28)树与二叉树第43页

“遍历”是二叉树最主要基本操作，是各种其它操作基础，二叉树许多其它操作都能够经过遍从来实现。如建立二叉树存放结构、求二叉树结点数、求二叉树深度等。6.3.5

二叉树遍历算法应用树与二叉树第44页二叉树二叉链表创建(1)按先序遍历建立二叉链表(p131)按满二叉树方式建立二叉链表(补充)

在此补充按满二叉树方式对结点进行编号建立链式二叉树。对每个结点，输入i、ch。i：结点编号，按从小到大次序输入ch：结点内容，假设是字符

在建立过程中借助一个一维数组S[n]，编号为i结点保留在S[i]中。算法实现：树与二叉树第45页#defineMAX_NODE50typedefstructBTNode{chardata;structBTNode*Lchild,*Rchild;}BTNode;BTNode*Create_BTree(void)

/*建立链式二叉树，返回指向根结点指针变量*/{BTNode*T,*p,*s[MAX_NODE];charch;inti,j;while(1){scanf(“%d”,&i);if(i==0)break;/*以编号0作为输入结束*/else{ch=getchar();树与二叉树第46页p=(BTNode*)malloc(sizeof(BTNode));

p–>data=ch;p–>Lchild=p–>Rchild=NULL;s[i]=p;if(i==1)T=p;else{j=i/2;/*j是i双亲结点编号*/

if(i%2==0)s[j]->Lchild=p;elses[j]->Rchild=p;}}}return(T);}树与二叉树第47页2求二叉树叶子结点数能够直接利用先序遍历二叉树算法求二叉树叶子结点数。只要将先序遍历二叉树算法中vist()函数简单地进行修改就能够。算法实现：#defineMAX_NODE50intsearch_leaves(BTNode*T){BTNode*Stack[MAX_NODE],*p=T;inttop=0,num=0;if(T!=NULL)树与二叉树第48页{stack[++top]=p;while(top>0){p=stack[top--];if(p->Lchild==NULL&&p->Rchild==NULL)num++;if(p->Rchild!=NULL)stack[++top]=p->Rchild;if(p->Lchild!=NULL)stack[++top]=p->Lchild;}}return(num);}树与二叉树第49页//递归实现voidTraverse(BTNode*T,int&count){if(T!=NULL)

{if(T->Lchild==null&&T->Rchild==null);count++;

Traverse(T->Lchild,count);

Traverse(T->Rchild,count);

}}树与二叉树第50页

用遍历方式求二叉树深度树与二叉树第51页voidTraverse(BTNode*T,int&height){if(T!=NULL)

{if(height>maxH)//maxH是全局变量

maxH=height;

Traverse(T->Lchild,height+1);

Traverse(T->Rchild,height+1);

}}树与二叉树第52页

遍历二叉树是按一定规则将树中结点排列成一个线性序列，即是对非线性结构线性化操作。怎样找到遍历过程中动态得到每个结点直接前驱和直接后继(第一个和最终一个除外)?怎样保留这些信息?设一棵二叉树有n个结点，则有n-1条边(指针连线)

，而n个结点共有2n个指针域(Lchild和Rchild)，显然有n+1个空闲指针域未用。则能够利用这些空闲指针域来存放结点直接前驱和直接后继信息。对结点指针域做以下要求：6.4

线索树树与二叉树第53页◆若结点有左孩子，则Lchild指向其左孩子，不然，指向其直接前驱；◆

若结点有右孩子，则Rchild指向其右孩子，不然，指向其直接后继；为防止混同,对结点结构加以改进，增加两个标志域，如图6-10所表示。LchildLtagdataRchildRtag图6-10线索二叉树结点结构0：Lchild域指示结点左孩子1：Lchild域指示结点前驱Ltag=0：Rchild域指示结点右孩子1：Rchild域指示结点后继Rtag=树与二叉树第54页

这种结点结构中,指向结点前驱和后继指针叫做线索；用这种结点结构组成二叉树存放结构；叫做线索链表；按照某种次序遍历，加上线索二叉树称之为线索二叉树。线索二叉树结点结构与示例typedefstructBiThrNode{ElemTypedata;structBiTreeNode*Lchild,*Rchild;intLtag,Rtag;}BiThrNode;如图6-11是二叉树及对应各种线索树示例。树与二叉树第55页在线索树上进行遍历,只要找到序列中第一个结点,然后依此找到结点后继直至其后继为空时止.那么怎样找结点后继与前驱?;不一样遍历方式找结点后继与前驱规则也不一样.

P133:中序遍历得到线索规则;后序遍历得到线索规则;

树与二叉树第56页AFHIEGBDC(a)二叉树

(b)先序线索树逻辑形式结点序列：ABDCEGFHIAFHIEGBDCNIL(d)后序线索树逻辑形式结点序列：DBGEHIFCA(c)中序线索树逻辑形式结点序列：DBAGECHFIAFHIEGBDCNILNILAFHIEGBDCNIL树与二叉树第57页0A00B10C0⋀1D10E10F0

1G11H11F1⋀(e)中序线索树链表结构图6-11线索二叉树及其存放结构说明：画线索二叉树时，实线表示指针，指向其左、右孩子；虚线表示线索，指向其直接前驱或直接后继。在线索树上进行遍历，只要先找到序列中第一个结点，然后就能够依次找结点直接后继结点直到后继为空为止。树与二叉树第58页

怎样在线索树中找结点直接后继?以图6-11(d)，(e)所表示中序线索树为例：◆树中全部叶子结点右链都是线索。右链直接指示了结点直接后继，如结点G直接后继是结点E。◆树中全部非叶子结点右链都是指针。依据中序遍历规律，非叶子结点直接后继是遍历其右子树时访问第一个结点，即右子树中最左下(叶子)结点。如结点C直接后继：沿右指针找到右子树根结点F，然后沿左链往下直到Ltag=1结点即为C直接后继结点H。树与二叉树第59页

怎样在线索树中找结点直接前驱?若结点Ltag=1，则左链是线索，指示其直接前驱；不然，遍历左子树时访问最终一个结点(即沿左子树中最右往下结点)为其直接前驱结点。对于后序遍历线索树中找结点直接后继比较复杂，可分以下三种情况：

◆若结点是二叉树根结点：其直接后继为空；

◆若结点是其父结点左孩子且其父结点没有右子树或结点是其父结点右孩子：直接后继为其父结点；

◆若结点是其父结点左孩子且其父结点有右子树：直接后继是对其父结点右子树按后序遍历第一个结点。树与二叉树第60页6.4.1

线索化二叉树

二叉树线索化指是依照某种遍历次序使二叉树成为线索二叉树过程。线索化过程就是在遍历过程中修改空指针使其指向直接前驱或直接后继过程。仿照线性表存放结构，在二叉树线索链表上也添加一个头结点head，头结点指针域安排是：

◆Lchild域：指向二叉树根结点；

◆Rchild域：指向中序遍历时最终一个结点；

◆二叉树中序序列中第一个结点Lchild指针域和最终一个结点Rchild指针域均指向头结点head。树与二叉树第61页

如同为二叉树建立了一个双向线索链表，对一棵线索二叉树既可从头结点也可从最终一个结点开始按寻找直接后继进行遍历。显然，这种遍历不需要堆栈，如图6-12所表示。结点类型定义#defineMAX_NODE50typedefenmu{Link,Thread}PointerTag;/*Link=0表示指针，Thread=1表示线索*/typedefstructBiThrNode{ElemTypedata;structBiTreeNode*Lchild,*Rchild;PointerTagLtag,Rtag;}BiThrNode;树与二叉树第62页(a)二叉树(b)中序线索树逻辑形式AFHIEGBDCNILNILAFHIEGBDC图6-12中序线索二叉树及其存放结构(c)中序线索二叉链表0A00B10C01D10E10F0

1G11H11F1Thrt01head树与二叉树第63页1先序线索化二叉树voidpreorder_Threading(BiThrNode*T){BiThrNode*stack[MAX_NODE];BiThrNode

*last=NULL,*p;inttop=0;if(T!=NULL){stack[++top]=T;while(top>0){p=stack[top--];if(p->Lchild!=NULL)p->Ltag=0;else{p->Ltag=1;p->Lchild!=last;}if(last!=NULL)if(last->Rchild!=NULL)last->Rtag=0;树与二叉树第64页else{last->Rtag=1;last->Rchild!=p;}last=p;if(p->Rchild!=NULL)stack[++top]=p->Rchild

;if(p->Lchild!=NULL)stack[++top]=p->Lchild

;}Last->Rtag=1;/*最终一个结点是叶子结点*/}}树与二叉树第65页2中序线索化二叉树voidinorder_Threading(BiThrNode*T){BiThrNode*stack[MAX_NODE];BiThrNode

*last=NULL,*p=T;inttop=0;while(p!=NULL||top>0)if(p!=NULL){stack[++top]=p;p=p->Lchild;}else{p=stack[top--];if(p->Lchild!=NULL)p->Ltag=0;else{p->Ltag=1;p->Lchild!=last;}if(last!=NULL)if(last->Rchild!=NULL)last->Rtag=0;树与二叉树第66页else{last->Rtag=1;last->Rchild!=p;}last=p;P=p->Rchild;}last->Rtag=1;/*最终一个结点是叶子结点*/}}树与二叉树第67页6.4.2

线索二叉树遍历

在线索二叉树中，因为有线索存在，在一些情况下能够方便地找到指定结点在某种遍历序列中直接前驱或直接后继。另外，在线索二叉树上进行某种遍历比在普通二叉树上进行这种遍历要轻易得多，不需要设置堆栈，且算法十分简练。树与二叉树第68页1先序线索二叉树先序遍历voidpreorder_Thread_bt(BiThrNode*T){BiThrNode*p=T;while(p!=NULL){visit(p->data)

;if(p->Ltag==0)p=p->Lchild;elsep=p->Rchild}}树与二叉树第69页2中序线索二叉树中序遍历voidinorder_Thread_bt(BiThrNode*T){BiThrNode*p;if(T!=NULL){p=T;while(p->Ltag==0

)p=p->Lchild;/*寻找最左结点*/while(p!=NULL){visit(p->data)

;if(p->Rtag==1)p=p->Rchild;/*经过右线索找到后继*/else/*不然，右子树最左结点为后继*/{p=p->Rchild;

树与二叉树第70页while(p->Ltag==0)p=p->Lchild;}}}}树与二叉树第71页6.5

树与森林

本节将讨论树存放结构、树及森林与二叉树之间相互转换、树遍历等。树与二叉树第72页6.5.1树存放结构

树存放结构依据应用不一样而不一样。1双亲表示法(次序存放结构)

用一组连续存放空间来存放树结点，同时在每个结点中附加一个指示器(整数域)

，用以指示双亲结点位置(下标值)。数组元素及数组类型定义以下：#defineMAX_SIZE100typedefstructPTNode{ElemTypedata;intparent;}PTNode;树与二叉树第73页typedefstruct{PTNodeNodes[MAX_SIZE];introot;/*根结点位置*/intnum;/*结点数*/

}Ptree;图6-13所表示是一棵树及其双亲表示存放结构。这种存放结构利用了任一结点父结点唯一性质。能够方便地直接找到任一结点父结点，但求结点子结点时需要扫描整个数组。FGHIRABCDE图6-13树双亲存放结构R-10A01B02C03D14E15F36G67H68I69树与二叉树第74页2孩子链表表示法

树中每个结点有多个指针域，每个指针指向其一棵子树根结点。有两种结点结构。⑴定长结点结构

指针域数目就是树度。其特点是：链表结构简单，但指针域浪费显著。结点结构如图6-14(a)所表示。在一棵有n个结点，度为k树中必有n(k-1)+1空指针域。⑵不定长结点结构

树中每个结点指针域数量不一样，是该结点度，如图6-14(b)所表示。没有多出指针域，但操作不便。树与二叉树第75页图6-14孩子表示法结点结构datachild1child2

⋯childk(a)定长结点结构(b)不定长结点结构datakichild1child2

⋯childki⑶复合链表结构(带双亲孩子链表法)

对于树中每个结点，其孩子结点用带头结点单链表表示，表结点和头结点结构如图6-15所表示。n个结点树有n个(孩子)单链表(叶子结点孩子链表为空)，而n个头结点又组成一个线性表且以次序存放结构表示。datafirstchild(a)头结点childnext(b)表结点图6-15孩子链表结点结构树与二叉树第76页数据结构类型定义以下：#defineMAX_NODE100typedefstructCTNode{intchild;/*孩子结点编号*/structCTNode*next;}CTNode;/*表结点结构*/typedefstruct{ElemTypedata;CTNode*firstchild;}CTBox;/*头结点结构*/树与二叉树第77页typedefstruct{CTBoxnodes[MAX_NODE];intr;/*根结点位置*/intn;/*结点数*/}CTree;/*头结点结构*/图6-13所表示树T孩子链表表示存放结构如图6-16所表示。树与二叉树第78页nodes789⋀

35⋀

012⋀

6⋀

0123456789MAX_NODE-1rnAB⋀

CD⋀

E⋀FG⋀H⋀I⋀┇┇R49图6-16图6-13树T孩子链表存放结构树与二叉树第79页3孩子弟兄表示法(二叉树表示法)

以二叉链表作为树存放结构，其结点形式如图6-17(a)所表示。两个指针域：分别指向结点第一个子结点和下一个弟兄结点。结点类型定义以下：typedefstructCSnode{ElemTypedata;structCSnode*firstchild,*nextsibing;}CSNode,*CSTree;图6-17(b)所表示树孩子弟兄表示存放结构如图6-17(c)。树与二叉树第80页图6-17树及孩子弟兄存放结构(b)树

FGRABCDE(c)孩子弟兄存放结构R⋀A⋀DC⋀⋀G⋀B⋀F⋀⋀E⋀孩子结点弟兄结点firstchilddatanextsibing(a)结点结构树与二叉树第81页6.5.2

森林与二叉树转换

因为二叉树和树都可用二叉链表作为存放结构，对比各自结点结构能够看出，以二叉链表作为媒介能够导出树和二叉树之间一个对应关系。◆

从物理结构来看，树和二叉树二叉链表是相同，只是对指针逻辑解释不一样而已。

◆

从树二叉链表表示定义可知，任何一棵和树对应二叉树，其右子树一定为空。图6-18直观地展示了树和二叉树之间对应关系。树与二叉树第82页图6-18树与二叉树对应关系二叉树

CERADBR⋀A⋀D⋀⋀C⋀B⋀E⋀树

RABCDE对应关系R⋀A⋀D⋀⋀C⋀B⋀E⋀⋀C⋀B⋀E⋀RA⋀D⋀存放解释存放解释树与二叉树第83页1树转换成二叉树

对于普通树，能够方便地转换成一棵唯一二叉树与之对应。将树转换成二叉树在“孩子弟兄表示法”中已给出，其详细步骤是：⑴加虚线。在树每层按从“左至右”次序在弟兄结点之间加虚线相连。(注意不是堂弟兄)⑵去连线。除最左第一个子结点外，父结点与全部其它子结点连线都去掉。⑶旋转。将树顺时针旋转450，原有实线左斜。⑷整型。将旋转后树中全部虚线改为实线，并向右斜。该转换过程如图6-19所表示。树与二叉树第84页

这么转换后二叉树特点是：

◆二叉树根结点没有右子树，只有左子树；

◆左子结点依然是原来树中对应结点左子结点，而全部沿右链往下右子结点均是原来树中该结点弟兄结点。图6-19树向二叉树转换过程(a)普通树

FGRABCDEFGRABCDE(b)加虚线，去连线后

(C)转换后二叉树FGRACDBE树与二叉树第85页2二叉树转换成树

对于一棵转换后二叉树，怎样还原成原来树?其步骤是：⑴加虚线。若某结点i是其父结点左子树根结点，则将该结点i右子结点以及沿右子链不停地搜索全部右子结点，将全部这些右子结点与i结点父结点之间加虚线相连，如图6-20(a)所表示。⑵去连线。去掉二叉树中全部父结点与其右子结点之间连线，如图6-20(b)所表示。⑶规整化。将图中各结点按层次排列且将全部虚线变成实线，如图6-20(c)所表示。树与二叉树第86页图6-20二叉树向树转换过程(C)还原后树FGRABCDE(b)去连线后(a)加虚线后FGRACDBECFGRADBE树与二叉树第87页3森林转换成二叉树

当普通树转换成二叉树后，二叉树右子树必为空。若把森林中第二棵树(转换成二叉树后)根结点作为第一棵树(二叉树)根结点弟兄结点，则可导出森林转换成二叉树转换算法以下：设F={T1,T2,⋯,Tn}是森林，则按以下规则可转换成一棵二叉树B=(root，LB，RB)①若n=0，则B是空树。②若n>0，则二叉树B根是森林T1根root(T1)，B左子树LB是B(T11,T12,⋯,T1m)，其中T11,T12,⋯,T1m是T1子树(转换后)，而其右子树RB是从森林F’={T2,T3,⋯,Tn}转换而成二叉树。树与二叉树第88页转换步骤：

①将F={T1,T2,⋯,Tn}中每棵树转换成二叉树。②按给出森林中树次序，从最终一棵二叉树开始，每棵二叉树作为前一棵二叉树根结点右子树，依次类推，则第一棵树根结点就是转换后生成二叉树根结点，如图6-21所表示。ACBDGMLHK(a)森林图6-21森林转换成二叉树过程(b)森林中每棵树对应二叉树ABCDGLKHM(c)森林对应二叉树ABCDGLKHM树与二叉树第89页4二叉树转换成森林

若B=(root，LB，RB)是一棵二叉树，则能够将其转换成由若干棵树组成森林：F={T1,T2,⋯,Tn}。转换算法：①若B是空树，则F为空。②若B非空，则F中第一棵树T1根root(T1)就是二叉树根root，T1中根结点子森林F1是由树B左子树LB转换而成森林；F中除T1外其余树组成森林F’={T2,T3,⋯,Tn}是由B右子树RB转换得到森林。上述转换规则是递归，能够写出其递归算法。以下给出详细还原步骤。树与二叉树第90页①去连线。将二叉树B根结点与其右子结点以及沿右子结点链方向全部右子结点连线全部去掉，得到若干棵孤立二叉树，每一棵就是原来森林F中树依次对应二叉树，如图6-22(b)所表示。②二叉树还原。将各棵孤立二叉树按二叉树还原为树方法还原成普通树，如图6-22(c)所表示。图6-22二叉树还原成森林过程ACBDMGLHK(c)还原成森林(a)二叉树ABCDGLKHM(b)去连线后ABCDMGLKH树与二叉树第91页6.5.3树和森林遍历1树遍历

由树结构定义可知，树遍历有二种方法。⑴

先序遍历：先访问根结点，然后依次先序遍历完每棵子树。如图6-23树，先序遍历次序是：ABCDEFGIJHK⑵

后序遍历：先依次后序遍历完每棵子树，然后访问根结点。如图6-23树，后序遍历次序是：CDBFGIJHEKA树与二叉树第92页说明：◆树先序遍历实质上与将树转换成二叉树后对二叉树先序遍历相同。◆树后序遍历实质上与将树转换成二叉树后对二叉树中序遍历相同。ABDCKGJIFHE图6-23树树与二叉树第93页2森林遍历

设F={T1,T2,⋯,Tn}是森林，对F遍历有二种方法。⑴先序遍历：按先序遍历树方式依次遍历F中每棵树。⑵中序遍历：按后序遍历树方式依次遍历F中每棵树。树与二叉树第94页6.6

赫夫曼树及其应用赫夫曼(Huffman)树又称最优树，是一类带权路径长度最短树，有着广泛应用。树与二叉树第95页6.6.1最优二叉树(Huffman树)1

基本概念①结点路径：从树中一个结点到另一个结点之间分支组成这两个结点之间路径。②路径长度：结点路径上分支数目称为路径长度。③树路径长度：从树根到每一个结点路径长度之和。例图6-23树。A到F：结点路径AEF；路径长度(即边数目)2；树路径长度：31+52+23=19

树与二叉树第96页④

结点带权路径长度：从该结点到树根结点之间路径长度与结点权(值)乘积。权(值)：各种开销、代价、频度等抽象称呼。⑤

树带权路径长度：树中全部叶子结点带权路径长度之和，记做：WPL=w1l1+w2l2+⋯+wnln=∑wili(i=1,2,⋯,n)其中：n为叶子结点个数；wi为第i个结点权值；

li为第i个结点路径长度。⑥

Huffman树：含有n个叶子结点(每个结点权值为wi)二叉树不止一棵，但在全部这些二叉树中，必定存在一棵WPL值最小树，称这棵树为Huffman树(或称最优树)。树与二叉树第97页在许多判定问题时，利用Huffman树能够得到最正确判断算法。如图6-24是权值分别为2、3、6、7，含有4个叶子结点二叉树，它们带权路径长度分别为：(a)WPL=22+32+62+72=36；(b)WPL=21+32+63+73=47；(c)WPL=71+62+23+33=34。其中(c)WPL值最小，能够证实是Huffman树。树与二叉树第98页236736726723(a)(b)(c)图6-24含有相同叶子结点，不一样带权路径长度二叉树2Huffman树结构①依据n个权值{w1,w2,⋯,wn}，结构成n棵二叉树集合F={T1,T2,⋯,Tn}，其中每棵二叉树只有一个权值为wi根结点，没有左、右子树；树与二叉树第99页②在F中选取两棵根结点权值最小树作为左、右子树结构一棵新二叉树，且新二叉树根结点权值为其左、右子树根结点权值之和；③在F中删除这两棵树，同时将新得到树加入F中；④

重复②、③，直到F只含一颗树为止。结构Huffman树时，为了规范，要求F={T1,T2,⋯,Tn}中权值小二叉树作为新结构二叉树左子树，权值大二叉树作为新结构二叉树右子树；在取值相等时，深度小二叉树作为新结构二叉树左子树，深度大二叉树作为新结构二叉树右子树。树与二叉树第100页

图6-25是权值集合W={8,3,4,6,5,5}结构Huffman树过程。所结构Huffman树WPL是：

WPL=62+33+43+82+53+53=79345568第一步5568第二步34768第三步34755108第四步5510634713第六步1111100000855101863471331图6-25Huffman树结构过程第五步8551018634713树与二叉树第101页6.6.2

赫夫曼编码及其算法1Huffman编码

在电报收发等数据通讯中，常需要将传送文字转换成由二进制字符0、1组成字符串来传输。为了使收发速度提升，就要求电文编码要尽可能地短。另外，要设计长短不等编码，还必须确保任意字符编码都不是另一个字符编码前缀，这种编码称为前缀编码。Huffman树能够用来结构编码长度不等且译码不产生二义性编码。设电文中字符集C={c1,c2,⋯,ci,⋯,cn}，各个字符出现次数或频度集W={w1,w2,⋯,wi,⋯,wn}。树与二叉树第102页Huffman编码方法以字符集C作为叶子结点，次数或频度集W作为结点权值来结构Huffman树。要求Huffman树中左分支代表“0”，右分支代表“1”。从根结点到每个叶子结点所经历路径分支上“0”或“1”所组成字符串，为该结点所对应编码，称之为Huffman编码。因为每个字符都是叶子结点，不可能出现在根结点到其它字符结点路径上，所以一个字符Huffman编码不可能是另一个字符Huffman编码前缀。树与二叉树第103页若字符集C={a,b,c,d,e,f}所对应权值集合为W={8,3,4,6,5,5}，如图6-25所表示，则字符a,b,c,d,e,f所对应Huffman编码分别是：10，010，011，00，110，111。2Huffman编码算法实现(1)数据结构设计Huffman树中没有度为1结点棵有n个叶子结点Huffman树共有2n-1个结点，则可存放在大小为2n-1一维数组中。实现编码结点结构如图6-26所表示。原因：◆

求编码需从叶子结点出发走一条从叶子到根路径；树与二叉树第104页◆译码需从根结点出发走一条到叶子结点路径。

结点类型定义：#defineMAX_NODE200/*Max_Node>2n-1

*/

typedefstruct{unsignedintWeight;/*权值域*/unsingedintParent,Lchild,Rchild;}HTNode;WeightParentLchildRchildWeight：权值域；Parent：双亲结点下标Lchild,Rchild：分别标识左、右子树下标图6-26Huffman编码结点结构树与二叉树第105页(2)Huffman树生成算法实现voidCreate_Huffman(unsignedn,HTNodeHT[],unsignedm)

/*创建一棵叶子结点数为nHuffman树*/{unsignedintw;intk,j;for(k=1;k<m;k++){if(k<=n){printf(“\nPleaseInputWeight:w=?”);scanf(“%d”,&w);HT[k].weight=w;}