数据结构第六章树与二叉树

数据结构第六章树与二叉树本章主要内容：本章主要内容：

1、树的定义和存储结构2、二叉树的定义、性质、存储结构3、二叉树的遍历、线索4、树和二叉树的转换5、赫夫曼树及其应用本章重点难点：本章重点难点：

1、二叉树的遍历

2、线索算法

3、赫夫曼树及其应用6.1树的概念和定义1、树的定义2、树的其它表示法

3、树的基本术语4、树的抽象数据类型定义1、树的定义树是n（n≥0）个结点的有限集合T。当n=0时，称为空树；当n>0时，该集合满足如下条件：其中必有一个称为根（root）的特定结点，它没有直接前驱，但有零个或多个直接后继。(2)其余n-1个结点可以划分成m（m≥0）个互不相交的有限集T1，T2，T3，…，Tm，其中Ti又是一棵树，称为根root的子树。每棵子树的根结点有且仅有一个直接前驱，但有零个或多个直接后继。

ABCHGFEDJIABCDEFGHIJMKL例如:2、树的其它表示法

（1）嵌套集合法嵌套集合法也称为文氏图法，它是用集合以及集合的包含关系来描述树形结构，每个圆圈表示一个集合，套起来的圆圈表示包含关系。ABCDEFGHIJMKL例如:

ABDFLKCEHIJMG(2)圆括号表示法圆括号表示法也称为广义表表示法，它是使用括号将集合层次与包含关系显示出来。

2、树的其它表示法

ABCDEFGHIJMKLA(B(E,F(K,L)),C(G),D(H,I,J(M)))T1T3T2树根例如:(3)凹入法凹入法是用不同宽度的行来显示各结点，而行的凹入程度体现了各结点集合的包含关系。树的凹入表示法主要用于树的屏幕显示和打印输出。2、树的其它表示法

ABCDEFGHJMKL例如:ABCFELJGHDKM结点:结点的度:树的度:叶子结点（终端结点）

:分支结点(非终端结点):数据元素+若干指向子树的分支分支的个数树中所有结点的度的最大值度为零的结点度大于零的结点DHIJM3、树的基本术语(从根到结点的)路径：孩子结点、双亲结点兄弟结点、堂兄弟祖先结点、子孙结点结点的层次:树的深度：由从根到该结点所经分支和结点构成ABCDEFGHIJMKL假设根结点的层次为1，第l层的结点的子树根结点的层次为l+1树中叶子结点所在的最大层次森林：是m（m≥0）棵互不相交的树的集合ArootBCDEFGHIJMKLF在数据结构中，树和森林并不象自然界里有一个明显的量的差别。任何一棵树，只要删去根结点就成了森林。有序树：子树之间存在确定的次序关系。无序树：子树之间不存在确定的次序关系。数据对象D：D是具有相同特性的数据元素的集合。

若D为空集，则称为空树。否则:(1)在D中存在唯一的称为根的数据元素root；(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。

数据关系R：4、树的抽象数据类型定义

基本操作：查找类插入类删除类4、树的抽象数据类型定义

Root(T)//求树的根结点

查找类：Value(T,cur_e)//求当前结点的元素值

Parent(T,cur_e)//求当前结点的双亲结点LeftChild(T,cur_e)//求当前结点的最左孩子RightSibling(T,cur_e)//求当前结点的右兄弟TreeEmpty(T)//判定树是否为空树TreeDepth(T)//求树的深度TraverseTree(T,Visit())//遍历InitTree(&T)//初始化置空树

插入类：CreateTree(&T,definition)//按定义构造树Assign(T,cur_e,value)//给当前结点赋值InsertChild(&T,&p,i,c)//将以c为根的树插入为结点p的第i棵子树

ClearTree(&T)//将树清空

删除类：DestroyTree(&T)//销毁树的结构DeleteChild(&T,&p,i)//删除结点p的第i棵子树对比树型结构和线性结构的结构特点~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~线性结构树型结构第一个数据元素(无前驱)

根结点(无前驱)最后一个数据元素(无后继)多个叶子结点(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)6.2二叉树为何要重点研究每结点最多只有两个“叉”的树？二叉树的结构最简单，规律性最强；可以证明，所有树都能转为唯一对应的二叉树，不失一般性。6.2二叉树6.2.1 二叉树的定义6.2.2 二叉树的性质6.2.3二叉树的存储结构1、定义：二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。6.2.1 二叉树的定义ABCDEFGHK根结点左子树右子树6.2.1 二叉树的定义逻辑结构：一对二（1:2）基本特征:①每个结点最多只有两棵子树（不存在度大于2的结点）；②左子树和右子树次序不能颠倒。6.2.1 二叉树的定义2、二叉树的五种基本形态：N空树只含根结点NNNLRR右子树为空树L左子树为空树左右子树均不为空树6.2.1 二叉树的定义问：具有3个结点的二叉树可能有几种不同形态？有5种一般的树有几种？6.2.1 二叉树的定义3、二叉树的抽象数据类型定义ADTBinaryTree{数据对象D:数据关系R:基本操作P：}ADTBinaryTreeD是具有相同特性的数据元素的集合。若D=Φ，则R=Φ；若D≠Φ，则R={H}；存在二元关系：①root唯一//关于根的说明②Dj∩Dk=Φ//关于子树不相交的说明③……//关于数据元素的说明④……//关于左子树和右子树的说明//至少有20个，如返回某结点的左孩子，或中序遍历，等等

性质1：在二叉树的第i层上至多有2i-1个结点。(i≥1)二叉树的性质(3+2)用归纳法证明：

归纳基：

归纳假设：

归纳证明：i=1层时，只有一个根结点：2i-1=20=1；假设对所有的j，1≤j

i，命题成立；二叉树上每个结点至多有两棵子树，则第i层的结点数=2i-22=2i-1

。二叉树的性质(3+2)性质2：

深度为k的二叉树上至多含2k-1个结点（k≥1）。证明：

基于上一条性质，深度为k的二叉树上的结点数至多为

20+21++2k-1=2k-1。二叉树的性质(3+2)

性质3：

对任何一棵二叉树，若它含有n0个叶子结点、n2个度为2的结点，则必存在关系式：n0=n2+1。二叉树的性质(3+2)设二叉树中结点总数为n，n1为二叉树中度为1的结点总数。因为二叉树中所有结点的度小于等于2，所以有 n=n0+n1+n2设二叉树中分支数目为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，故结论成立。二叉树的性质(3+2)证明：两类特殊的二叉树：满二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二叉树：树中所含的n个结点和满二叉树中编号为1至n的结点一一对应。123456789101112131415abcdefghij性质4：

具有n个结点的完全二叉树的深度为log2n

+1

。二叉树的性质(3+2)证明：设n个结点的完全二叉树的深度为k，根据性质2可知，k-1层满二叉树的结点总数为：2k-1-1k层满二叉树的结点总数为：2k-1显然有：2k-1-1<n2k-12k-1

n<2k取对数有：k-1log2n<k因为k是整数，所以k-1=log2n，k=㏒2n+1结论成立。二叉树的性质(3+2)性质5：若对含n个结点的完全二叉树从上到下且从左至右进行1至n的编号，则对完全二叉树中任意一个编号为i的结点：

(1)若i=1，则该结点是二叉树的根，无双亲， 否则，编号为i/2的结点为其双亲结点；

(2)若2i>n，则该结点无左孩子，

否则，编号为2i的结点为其左孩子结点；

(3)若2i+1>n，则该结点无右孩子结点，

否则，编号为2i+1的结点为其右孩子结点。二叉树的性质(3+2)研究生试题【2009】已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则完全二叉树的结点个数最多是A.39

B.52

C.111

D.119

【2010】在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶节点个数是

A.41

B.82

C.113

D.122

【2011】若一个完全二叉树有768个结点，则该二叉树中叶子结点的个数是A.257

B.258

C.384

D.385二叉树的存储结构2、二叉树的链式存储表示1、二叉树的顺序存储表示1、二叉树的顺序存储表示

二叉树的顺序存储表示

所谓二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。一般是按照二叉树结点从上至下、从左到右的顺序存储。#defineMAX_TREE_SIZE100//二叉树的最大结点数typedefTElemTypeSqBiTree[MAX_TREE_SIZE];//0号单元存储根结点SqBiTreebt;1、二叉树的顺序存储表示例如:ABCDEF

ABDCEF

0123456789101112131401326对于一般的二叉树，我们必须按照完全二叉树的形式来存储，就会造成空间的浪费。单支树就是一个极端情况。ABCDA^B^^^C^^^^^^^D单支树012345678910111213142、二叉树的链式存储表示（1）二叉链表（2）三叉链表ADEBCFrootlchilddatarchild结点结构:1.二叉链表typedefstructBiTNode{//结点结构TElemTypedata;

structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;lchilddatarchild结点结构:C语言的类型描述如下:结论：若一个二叉树含有n个结点，则它的二叉链表中必含有2n个指针域，其中必有n＋1个空的链域。证明结论：分支数目B=n-1，即非空的链域有n-1个，故空链域有2n-(n-1)=n+1个。ADEBCFroot2．三叉链表parentlchilddatarchild结点结构:

typedefstructTriTNode{//结点结构TElemTypedata;

structTriTNode*lchild,*rchild;//左右孩子指针

structTriTNode

*parent;//双亲指针

}TriTNode,*TriTree;parentlchilddatarchild结点结构:C语言的类型描述如下:6.3二叉树的遍历和线索二叉树6.3.1二叉树的遍历6.3.2线索二叉树6.3.1二叉树的遍历一、问题的提出

二、先左后右的遍历四、递归算法三、二叉树的建立五、中序遍历算法的非递归描述六、层次遍历一、问题的提出

“遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构，每个结点有两个后继，则存在如何遍历即按什么样的搜索路径遍历的问题。对“二叉树”而言，可以有三条搜索路径：1先上后下的按层次遍历；2先左（子树）后右（子树）的遍历；3先右（子树）后左（子树）的遍历。一、问题的提出

二、先左后右的遍历先（根）序的遍历中（根）序的遍历后（根）序的遍历

若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。先（根）序的遍历二、先左后右的遍历对于如下图的二叉树，其先序遍历的序列为：A、B、D、F、G、C、E、H。ABCDFGEH二、先左后右的遍历

若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。中（根）序的遍历二、先左后右的遍历对于如下图的二叉树，其中序遍历的序列为：中序遍历：B、F、D、G、A、C、E、H。ABCDFGEH二、先左后右的遍历

若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。后（根）序的遍历二、先左后右的遍历对于如下图的二叉树，其后序遍历的序列为：后序遍历：F、G、D、B、H、E、C、A。ABCDFGEH二、先左后右的遍历若u和v是二叉树的两个结点u是v的祖先结点

u在v的左边

u和v是叶子结点ABCDFGEH研究生试题【2009】给定二叉树图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3，1，7，5，6，2，4，则其遍历方式是A．LRN

B.NRL

C.RLN

D.RNL

1324567三、二叉树的建立由表达式建树由二叉树的先序和中序序列建树由二叉树的先序和中序序列建树二叉树的先序序列二叉树的中序序列左子树右子树根左子树右子树根abcdefgcbdaegf例如:aabbccddeeffggabcdefg^^^^^^^^先序序列中序序列

先序和中序序列相同二叉树的树形后序和中序序列相同二叉树的树形先序和后序序列相同二叉树的树形先序和中序序列相反二叉树的树形后序和中序序列相反二叉树的树形先序和后序序列相反二叉树的树形研究生试题【2011】若一个二叉树的前序遍历序列和后序遍历序列分别为1,2,3,4和4,3,2,1，则该二叉树的后序遍历序列不会是（）A.1,2,3,4B.2,3,4,1C.3,2,4,1D.4,3,2,1a+b(a+b)×c–d/ea+b×c分析表达式和二叉树的关系:ab+abc×+abc×+(a+b)×cabcde-×+/对应表达式(a+b)×c–d/e的二叉树abcde-×+/特点：

操作数为叶子结点运算符为分支结点--/-×/-×/-×/-×/-×/-e×/de×/cde×/+cde×/+cde×/+cde×/b+cde×/ab+cde×/先序遍历序列：-*+abc/de中序序遍历序列：a+b*c-d/e后序遍历序列：ab+c*de/-前缀表达式（波兰式）中缀表达式后缀表达式（逆波兰式）二叉树的二叉链表结点结构typedefstructBiTNode{//结点结构TElemTypedata;

structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;四、递归算法

若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。四、递归算法1、先序遍历二叉树四、递归算法voidPreorder(BiTreeT,

void(*visit)(TElemType&e)){

if(T){visit(T->data);//访问结点Preorder(T->lchild,visit);//遍历左子树Preorder(T->rchild,visit);//遍历右子树

}}1、先序遍历二叉树2、统计二叉树中叶子结点的个数算法基本思想:先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增1。四、递归算法先序遍历统计叶子结点个数voidCountLeaf(BiTreeT,int&count){

if(T){

if((!T->lchild)&&(!T->rchild))count++;//对叶子结点计数CountLeaf(T->lchild,count);CountLeaf(T->rchild,count);}//if}//CountLeafvoidCountLeaf(BiTreeT,int*count){

if(T){

if((!T->lchild)&&(!T->rchild))(*count)++;//对叶子结点计数CountLeaf(T->lchild,count);CountLeaf(T->rchild,count);}//if}//CountLeaf先序遍历统计叶子结点个数后序遍历统计叶子结点个数intleaf(BiTreeroot){intLeafcount;if(root==NULL)LeafCount=0;elseif((root->lchild==NULL)&&(root->rchild==NULL))LeafCount=1;elseLeafCount=leaf(root->lchild)+leaf(root->rchild);returnLeafcount;}3、求二叉树的深度(后序遍历)算法基本思想:首先分析二叉树的深度和它的左、右子树深度之间的关系。四、递归算法从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加1。四、递归算法intDepth(BiTreeT){//返回二叉树的深度

if(!T)depthval=0;else{depthLeft=Depth(T->lchild);depthRight=Depth(T->rchild);depthval=1+(depthLeft>depthRight?depthLeft:depthRight);

}

returndepthval;}3、复制二叉树其基本操作为：生成一个结点。根元素T左子树右子树根元素NEWT左子树右子树(后序遍历)四、递归算法BiTNode*GetTreeNode(TElemTypeitem,BiTNode*lptr,BiTNode*rptr){

if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))

exit(1);T->data=item;T->lchild=lptr;T->rchild=rptr;

returnT;}生成一个二叉树的结点(其数据域为item,左指针域为lptr,右指针域为rptr)BiTNode*CopyTree(BiTNode*T){

if(!T)returnNULL;

if(T->lchild)

newlptr=CopyTree(T->lchild);//复制左子树

elsenewlptr=NULL;

if(T->rchild)

newrptr=CopyTree(T->rchild);//复制右子树

elsenewrptr=NULL;newT=GetTreeNode(T->data,newlptr,newrptr);

returnnewT;}//CopyTreeABCDEFGHK^D^C^^B^H^^K^G^F^E^A例如：下列二叉树的复制过程如下：newT4、建立二叉树的存储结构不同的定义方法相应有不同的存储结构的建立四、递归算法

以字符串的形式根左子树右子树定义一棵二叉树例如:ABCD以空白字符“”表示A(B(,C(,)),D(,))空树只含一个根结点的二叉树A以字符串“A”表示以下列字符串表示StatusCreateBiTree(BiTree&T){scanf(&ch);

if(ch=='')T=NULL;

else{

if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))

exit(OVERFLOW);T->data=ch;//生成根结点CreateBiTree(T->lchild);//构造左子树CreateBiTree(T->rchild);//构造右子树

}

returnOK;}//CreateBiTreeStatusCreateBiTree(BiTree*T){scanf(&ch);

if(ch=='')*T=NULL;

else{

if(!(*T=(BiTNode*)malloc(sizeof(BiTNode))))

exit(OVERFLOW);(*T->data)=ch;//生成根结点CreateBiTree(&((*T)->lchild));//构造左子树CreateBiTree(&((*T)->rchild));//构造右子树

}

returnOK;}//CreateBiTreeAB

C

D

ABCD算法执行过程举例如下：ATBCD^^^^^StatusInorderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){//中序遍历二叉树T的非递归算法，采用二叉链表存储结构Inistack(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))returnerror;Push(S,p->rchild);}}returnOK;}五、中序遍历算法的非递归描述五、中序遍历算法的非递归描述StatusInorderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){//中序遍历二叉树T的非递归算法，采用二叉链表存储结构Inistack(S);p=T;while(p||!StackEmpty(S)){if(p){Push(S,p);p=p->lchild);}//根指针进栈，遍历左子树else{Pop(S,p);//根指针退栈，访问根结点，遍历右子树if(!Visit(p->data))returnerror;p=p->rchild;}}returnOK;}五、中序遍历算法的非递归描述BiTNode*GoFarLeft(BiTreeT,Stack*S){

if(!T)returnNULL;

while(T->lchild){Push(S,T);T=T->lchild;

}

returnT;}voidInorder_I(BiTreeT,void(*visit)(TelemType&e)){Stack*S;t=GoFarLeft(T,S);//找到最左下的结点

while(t){visit(t->data);

if(t->rchild)t=GoFarLeft(t->rchild,S);

elseif(!StackEmpty(S))//栈不空时退栈

t=Pop(S);

elset=NULL;//栈空表明遍历结束}//while}//Inorder_I

按照自上而下（从根结点开始），从左到右（同一层）的顺序逐层访问二叉树上的所有结点，这样的遍历称为按层次遍历。六、层次遍历

层次遍历的序列：ABCDEFGHABCDFGEH按层次进行遍历时，当一层结点访问完后，接着访问下一层的结点先遇到的结点先访问这与队列的操作原则是一致的。ABCDFGEH

遍历从二叉树的根结点开始，首先将根结点指针入队列

从队头取出一个元素，每取一个元素执行下面两个操作：

（1）访问该元素所指结点；（2）若该元素所指结点的左、右孩子结点非空，则将该元素所指结点的左孩子指针和右孩子指针依次入队。此过程不断进行，直到队空为止。

在进行层次遍历时可设置一个数组来模拟队列，用于保存被访问结点的子结点的地址。以二叉链表方式存储，一维数组q[MAXLEN]用以实现队列，lchild和rchild分别是被访问结点的左、右指针。voidLevelorder(BiTreeT) {//按层次遍历二叉树Tinti,j;BiTreeq[MAXLEN];//设置数组来模拟队列BiTreep;p=T;if(p)//若二叉树非空，根结点地址入队{i=0;q[i]=p;j=1;}

while(i!=j){p=q[i];i++；printf(p->data);//访问队头结点的数据域if(p->lchild)//将原队头结点的左孩子入队{q[j]=p->lchild;j++;}if(p->rchild)//将原队头结点的右孩子入队{q[j]=p->rchild；j++；}}}

何谓线索二叉树？线索链表的遍历算法如何建立线索链表？线索常见算法线索二叉树一、何谓线索二叉树？遍历二叉树的结果是求得结点的一个线性序列。ABCDEFGHK例如:先序序列:

ABCDEFGHK中序序列:

BDCAHGKFE后序序列:

DCBHKGFEA指向该线性序列中的“前驱”和“后继”的指针，称作“线索”与其相应的二叉树，称作“线索二叉树”包含“线索”的存储结构，称作“线索链表”ABCDEFGHK^D^

C^^B

E^对线索链表中结点的约定：在二叉链表的结点中增加两个标志域，并作如下规定：若该结点的左子树不空，则Lchild域的指针指向其左子树，且左标志域的值为“指针Link”；否则，Lchild域的指针指向其“前驱”，且左标志的值为“线索Thread”

。若该结点的右子树不空，则rchild域的指针指向其右子树，且右标志域的值为“指针Link”；否则，rchild域的指针指向其“后继”，且右标志的值为“线索Thread”。

如此定义的二叉树的存储结构称作“线索链表”。typedefstructBiThrNod{TElemTypedata;

structBiThrNode*lchild,*rchild;//左右指针PointerThrLTag,RTag;//左右标志}BiThrNode,*BiThrTree;线索链表的类型描述：typedefenum{Link,Thread}PointerThr;

//Link==0:指针，Thread==1:线索LChildLtagDataRtagRChild为了区分孩子结点和前驱、后继结点，为结点结构增设两个标志域，如下图所示：其中：Ltag=0LChild域指示结点的左孩子1LChild域指示结点的遍历前驱Rtag=0RChild域指示结点的右孩子1RChild域指示结点的遍历后继二、线索链表的遍历算法:for(p=firstNode(T);p;p=Succ(p))Visit(p);由于在线索链表中添加了遍历中得到的“前驱”和“后继”的信息，从而简化了遍历的算法。例如:对中序线索化链表的遍历算法

※中序遍历的第一个结点？

※在中序线索化链表中结点的后继？左子树上处于“最左下”（没有左子树）的结点。若无右子树，则为后继线索所指结点；否则为对其右子树进行中序遍历时访问的第一个结点。voidInOrderTraverse_Thr(BiThrTreeT,

void(*Visit)(TElemTypee)){p=T->lchild;//p指向根结点

while(p!=T){

//空树或遍历结束时，p==Twhile(p->LTag==Link)p=p->lchild;//第一个结点while(p->RTag==Thread&&p->rchild!=T){p=p->rchild;Visit(p->data);//访问后继结点

}p=p->rchild;//p进至其右子树根

}}//InOrderTraverse_Thr在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的“前驱”和“后继”信息。遍历过程中，附设指针pre,并始终保持指针pre指向当前访问的、指针p所指结点的前驱。三、如何建立线索链表？voidInThreading(BiThrTreep){

if(p){//对以p为根的非空二叉树进行线索化InThreading(p->lchild);//左子树线索化

if(!p->lchild)//建前驱线索

{p->LTag=Thread;p->lchild=pre;}

if(!pre->rchild)//建后继线索

{pre->RTag=Thread;pre->rchild=p;}

pre=p;//保持pre指向p的前驱InThreading(p->rchild);//右子树线索化

}//if}//InThreadingStatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){//构建中序线索链表if(!(Thrt=(BiThrTree)malloc(

sizeof(BiThrNode))))

exit(OVERFLOW);Thrt->LTag=Link;Thrt->RTag=Thread;Thrt->rchild=Thrt;//添加头结点returnOK;}//InOrderThreading……if(!T)Thrt->lchild=Thrt;else{Thrt->lchild=T;pre=Thrt;InThreading(T);pre->rchild=Thrt;//处理最后一个结点pre->RTag=Thread;Thrt->rchild=pre;}下面是对同一棵二叉树的遍历方法不同得到的不同线索树。NULL(a)二叉树ABCDGEFH(b)先序线索二叉树ABCDGEFHNULLNULL（c）中序线索二叉树ABCDGEFH（d）后序线索二叉树NULLABCDGEFH研究生试题【2010】下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是（

）四、线索常见算法1、在线索二叉树中找前驱、后继结点2、线索二叉树的插入、删除运算1、在线索二叉树中找前驱、后继结点2）在中序线索树中找结点后继1）在中序线索树中找结点前驱根据线索二叉树的基本概念和存储结构可知，对于结点p，当p->Ltag=1时，p->LChild指向p的前驱。当p->Ltag=0时，p->LChild指向p的左孩子。由中序遍历的规律可知，作为根p的前驱结点，它是中序遍历p的左子树时访问的最后一个结点，即左子树的“最右下端”结点。1）在中序线索树中找结点前驱在中序线索树中找结点前驱算法：voidInPre(BiTNode*p,BiTNode*pre)/*在中序线索二叉树中查找p的中序前驱,并用pre指针返回结果*/{if(p->Ltag==1)pre=p->LChild;/*直接利用线索*/else{/*在p的左子树中查找“最右下端”结点*/for(q=p->LChild;q->Rtag==0;q=q->RChild);pre=q;}}2）在中序线索树中找结点后继对于结点p，若要找其后继结点，当p->Rtag=1时，p->RChild即为p的后继结点；当p->Rtag=0时，说明p有右子树，此时p的中序后继结点即为其右子树的“最左下端”的结点。voidInSucc(BiTNode*p,BiTNode*succ)/*在中序线索二叉树中查找p的后继结点，并用succ指针返回结果*/{if(p->Rtag==1)succ=p->RChild;/*直接利用线索*/else{/*在p的右子树中查找“最左下端”结点*/for(q=p->RChild;q->Ltag==0;q=q->LChild);succ=q;}}在中序线索树中找结点后继算法2、线索二叉树的插入、删除运算

二叉树加上线索之后，当插入或删除一结点时，可能会破坏原树的线索。所以在线索二叉树中插入或删除结点的难点在于：插入一个结点后，仍要保持正确的线索。主要以中序线索二叉树为例，说明线索二叉树的插入和删除运算。1）插入结点运算在中序线索二叉树中插入结点可分为两种情况：第一种：将新的结点插入到二叉树中，作某结点的左孩子；第二种：将新的结点插入到二叉树中，作某结点的右孩子。我们仅讨论后一种情况。1）插入结点运算InsNode(BiTNode*p,BiTNode*r)表示在线索二叉树中插入r所指向的结点，做p所指结点的右孩子。（1）若结点p的右孩子为空，则插入结点r的过程很简单。原来p的后继变为r的后继，结点p变为r的前驱，结点r成为p的右孩子。结点r的插入对p原来的后继结点没有任何的影响。prpr结点的右孩子为空时的插入过程为：插入前插入后（2）若p的右孩子不为空，则插入后，p的右孩子变为r的右孩子结点，p变为r的前驱结点，r变为p的右孩子结点。这时还需要修改原来p的右子树中“最左下端”结点的左指针域，使它由原来的指向结点p变为指向结点r。插入过程为：prpr插入前插入后上述过程用C语言描述为：voidInsNode(BiTNode*p,BiTNode*r){if(p->Rtag==1)/*p无右孩子*/{ r->RChild=p->RChild;/*p的后继变为r的后继*/ r->Rtag=1; p->RChild=r;/*r成为p的右孩子*/ r->LChild=p;/*p变为r的前驱*/ r->Ltag=1;}else/*p有右孩子*/

{

s=p->RChild;while(s->Ltag==0) s=s->LChild;/*查找p结点的右子树的“最左下端”结点*/r->RChild=p->RChild;/*p的右孩子变为r的右孩子*/r->Rtag=0;r->LChild=p;/*p变为r的前驱*/r->Ltag=1;p->RChild=r;/*r变为p的右孩子*/s->LChild=r;/*r变为p原来右子树的“最左下端”结点的前驱*/}}2）删除结点运算

与插入操作一样，在线索二叉树中删除一个结点也会破坏原来的线索，所以需要在删除的过程中保持二叉树的线索化。

2）删除结点运算在中序线索二叉树中删除结点r的过程为：rp(b)删除后pr(a))删除前

6.4树和森林

1树的三种存储结构2树、森林和二叉树的对应关系3树和森林的遍历、树的三种存储结构一、双亲表示法二、孩子链表表示法三、树的孩子-兄弟(二叉链表）表示法ABCDEFG0A-11B02C03D04E25F26G5r=0n=6dataparent一、双亲表示法:

typedefstructPTNode{Elemdata;

intparent;//双亲位置域

}PTNode;

dataparent#defineMAX_TREE_SIZE100结点结构:C语言的类型描述:typedefstruct{PTNodenodes[MAX_TREE_SIZE];

intr,n;//根结点的位置和结点个数

}PTree;树结构:ABCDEFG0A-11B02C03D04E25F26G5r=0n=6dataparentABCDEFG0A1B2C3D4E5F6Gr=0n=6datafirstchild123456二、孩子链表表示法:ABCDEFG0A1B2C3D4E5F6Gr=0n=6dataparent123456-1000224typedefstructCTNode{

intchild;

structCTNode*next;

}*ChildPtr;孩子结点结构:

childnextC语言的类型描述:

typedefstruct{Elemdata;ChildPtrfirstchild;//孩子链的头指针

}CTBox;双亲结点结构

datafirstchildtypedefstruct{CTBoxnodes[MAX_TREE_SIZE];

intn,r;//结点数和根结点的位置

}CTree;树结构:ABCDEFGABCEDFGrootABCEDFG

三、树的孩子-兄弟(二叉链表）表示法typedefstructCSNode{Elemdata;

structCSNode

*firstchild,*nextsibling;}CSNode,*CSTree;C语言的类型描述:结点结构:

firstchilddatanextsibling由于二叉树可以用二叉链表表示，为了使一般树也能用二叉链表表示，必须找出树与二叉树之间的关系。这样，给定一棵树，可以找到唯一的一棵二叉树与之对应。1、树转换为二叉树

6.4.2树、森林和二叉树的对应关系

A

B

CDE

G

HFI树转换为二叉树根结点无右孩子ABEFCDGHI

2、森林和二叉树的对应关系设森林F=(T1,T2,…,Tn);T1=(root，t11,t12,…,t1m);二叉树B=(LBT,Node(root),RBT);由森林转换成二叉树的转换规则为:若F=Φ，则B=Φ；否则，由ROOT(T1)对应得到Node(root)；由(t11,t12,…,t1m)对应得到LBT；由(T2,T3,…,Tn)对应得到RBT。由二叉树转换为森林的转换规则为：若B=Φ，则F=Φ；否则，由Node(root)对应得到ROOT(T1

)；由LBT对应得到(t11,t12,…，t1m)；由RBT对应得到(T2,T3,…,Tn)。

由此，树的各种操作均可对应二叉树的操作来完成。

应当注意的是，和树对应的二叉树，其左、右子树的概念已改变为：左是孩子，右是兄弟。研究生试题【2009】将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是

I．父子关系

II.兄弟关系

III.

u的父结点与v的父结点是兄弟关系

()

A.只有II

B.I和II

C.I和III

D.I、II和III

B一、树的遍历二、森林的遍历三、树的遍历的应用6.4.3树和森林的遍历树的遍历可有三条搜索路径:按层次遍历:先根(次序)遍历:后根(次序)遍历:若树不空，则先访问根结点，然后依次先根遍历各棵子树。若树不空，则先依次后根遍历各棵子树，然后访问根结点。若树不空，则自上而下自左至右访问树中每个结点。ABCDEFGHIJK先根遍历时顶点的访问次序：ABEFCDGHIJK后根遍历时顶点的访问次序：EFBCIJKHGDA层次遍历时顶点的访问次序：ABCDEFGHIJK

BCDEFGHIJK1．森林中第一棵树的根结点；2．森林中第一棵树的子树森林；3．森林中其它树构成的森林。森林由三部分构成：1.先序遍历森林的遍历若森林不空，则访问森林中第一棵树的根结点；先序遍历森林中第一棵树的子树森林；先序遍历森林中(除第一棵树之外)其余树构成的森林。即：依次从左至右对森林中的每一棵树进行先根遍历。２．中序遍历若森林不空，则中序遍历森林中第一棵树的子树森林；访问森林中第一棵树的根结点；中序遍历森林中(除第一棵树之外)其

余树构成的森林。即：依次从左至右对森林中的每一棵树进行后根遍历。

树的遍历和二叉树遍历的对应关系？先根遍历后根遍历树二叉树森林先序遍历先序遍历中序遍历中序遍历设树的存储结构为孩子兄弟链表typedefstructCSNode{Elemdata;

structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;一、求树的深度二、输出树中所有从根到叶子的路径三、建树的存储结构intTreeDepth(CSTreeT){

if(!T)return0;

else{h1=TreeDepth(T->firstchild);h2=TreeDepth(T->nextsibling);}}//TreeDepthreturn(max(h1+1,h2));一、求树的深度的算法：二、输出树中所有从根到叶子的路径的算法:ABCDEFGHIJK例如：对左图所示的树，其输出结果应为：ABEABFACADGHIADGHJADGHKvoidAllPath(BitreeT,Stack&S){

if(T){Push(S,T->data);if(!T->Lchild&&!T->Rchild)PrintStack(S);else{

AllPath(T->Lchild,S);AllPath(T->Rchild,S);

}Pop(S);

}//

if(T)}//AllPath//输出二叉树上从根到所有叶子结点的路径voidOutPath(BitreeT,Stack&S){

while(!T){Push(S,T->data);

if(!T->firstchild)Printstack(s);

elseOutPath(T->firstchild,s);Pop(S);T=T->nextsibling;

}//while}//OutPath//输出森林中所有从根到叶的路径三、建树的存储结构的算法:

和二叉树类似，不同的定义相应有不同的算法。假设以二元组(F，C)的形式自上而下、自左而右依次输入树的各边，建立树的孩子-兄弟链表。ABCDEFG例如:对下列所示树的输入序列应为:(‘#’,‘A’)(‘A’,‘B’)(‘A’,‘C’)(‘A’,‘D’)(‘C’,‘E’)(‘C’,‘F’)(‘E’,‘G’)ABCD(‘#’,‘A’)(‘A’,‘B’)(‘A’,‘C’)(‘A’,‘D’)(‘C’,‘E’)可见，算法中需要一个队列保存已建好的结点的指针。voidCreatTree(CSTree&T){T=NULL;

for(scan