哈工大数据结构6

第6章树和二叉树1树是一种重要的非线性结构。树是以分支关系定义的层次结构，其中以二叉树最为常用。树型结构在计算机中有广泛应用：在微机操作系统中，文件和文件夹以树形结构存储。在编译系统中，可以用树来表示源程序的语法结构。在数据库系统中，树型结构是信息的重要组织形式。26.1树的定义和基本术语6.2二叉树6.3遍历二叉树6.4恢复二叉树6.7树和森林6.8哈夫曼树及其应用6.5线索二叉树6.6二叉树的基本运算及其应用36.1树的定义和基本术语4数据对象D：D是具有相同特性的数据元素的集合。

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

R：1.树的定义5

基本操作：查找类

插入类删除类6

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())//遍历7InitTree(&T)

//初始化置空树

插入类：CreateTree(&T,definition)

//按定义构造树Assign(T,cur_e,value)

//给当前结点赋值InsertChild(&T,&p,i,c)

//将以c为根的树插入为结点p的第i棵子树8

ClearTree(&T)

//将树清空

删除类：DestroyTree(&T)

//销毁树的结构DeleteChild(&T,&p,i)

//删除结点p的第i棵子树9ABCDEFGHIJMKLA(

B(E,F(K,L)),

C(G),D(H,I,J(M)))T1T3T2树根例:10

树的特点：

在非空树中：树中至少有一个结点——根。树中各子树是互不相交的集合。

树的定义是递归的，即在树的定义中又用到树的概念，正好反映了树的固有特性。

11A只有根结点的树ABCDEFGHIJKLM有子树的树根子树12(１)有确定的根；(２)树根和子树根之间为有向关系。有向树：有序树：子树之间存在确定的次序关系。无序树：子树之间不存在确定的次序关系。13对比树型结构和线性结构的结构特点14~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~线性结构树型结构第一个数据元素(无前驱)

根结点(无前驱)最后一个数据元素(无后继)多个叶子结点(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)15结点(node)——表示树中的元素，包括数据项及若干指向其子树的分支。结点的度(degree)——结点拥有的子树个数。叶子(leaf)——度为0的结点。孩子(child)——结点子树的根称为该结点的孩子。双亲(parents)——孩子结点的上层结点叫该结点的双亲或父结点。兄弟(sibling)——同一双亲的孩子。树的度——一棵树中各结点的度的最大值称为该树的度。2.树的基本术语16结点的层次(level)——根结点的层数为1，其余结点的层数等于它双亲结点的层数加1。树的深度(depth)——树中结点的最大层次数。森林(forest)——m(m0)棵互不相交的树的集合。(从根到结点的)路径——由从根到该结点所经分支和结点构成。ABCDEFGHIJMKL17任何一棵非空树是一个二元组：

Tree=（root，F）其中：root被称为根结点。

F被称为子树森林。森林：是m（m≥0）棵互不相交的树的集合。ArootBCDEFGHIJMKLF18任何一棵树，只要删去根结点就成了森林。如图：(a)

树

(b)

移去根结点后成为森林19ABCDEFGHIJKLM结点A的度：3结点B的度：2结点M的度：0叶子：K，L，F，G，M，I，J结点A的孩子：B，C，D结点B的孩子：E，F结点I的双亲：D结点L的双亲：E结点B，C，D为兄弟结点K，L为兄弟树的度：3结点A的层次：1结点M的层次：4树的深度：4结点F，G为堂兄弟结点A是结点F，G的祖先20bacghdefij树型表示树的表示：21凹入表表示abdeijfcgh22嵌套集合表示嵌套括号表示ijdfghabcea(b(d,e(i,j),c(g,h)

)

)236.2二叉树241.二叉树的定义

二叉树是有n（n>=0）个结点的有限集合。（1）该集合或者为空（n=0）；（2）该集合或者只有一个根结点；（3）该集合或者由一个根结点及两个不相交的分别称为左子树和右子树组成的非空树；（4）左子树和右子树同样又都是二叉树。二叉树的定义是递归的：在一棵非空的二叉树中，每个结点至多只有两棵子树，分别称为左子树和右子树，左子树和右子树同样又都是二叉树。二叉树是有序树：二叉树的左右子树的次序不能交换。25ABCDEFGHK根结点左子树右子树26二叉树的五种基本形态：N空树只含根结点NNNLRR右子树为空树L左子树为空树左右子树均不为空树27

二叉树的基本操作：查找类插入类删除类28

Root(T);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);BiTreeDepth(T);PreOrderTraverse(T,Visit());InOrderTraverse(T,Visit());PostOrderTraverse(T,Visit());LevelOrderTraverse(T,Visit());29

InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c);30ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);31二叉树的主要基本操作：

（1）CreateBT（）：

创建一棵二叉树。

（2）ShowTree(BT*T)：按凹入法显示二叉树。（3）Preorder(BT*T)：按先序（根、左、右）遍历二叉树上所有结点。（4）Inorder(BT*T)：按中序（左、根、右）遍历二叉树上所有结点。（5）Postorder(BT*T)：按后序（左、右、根）遍历二叉树上所有结点。32（6）Levelorder(BT*T)：按层次遍历二叉树上所有结点。（7）Leafnum(BT*T)：

求二叉树叶子结点总数。（8）TreeDepth(BT*T)：求二叉树的深度。332.二叉树的性质性质1：一棵非空二叉树的第i层上最多有2i–1个结点（i≥1）。证明：用归纳法证明之

i=1时，只有一个根结点，

成立假设对所有j(1j<i)命题成立，即第j层上至多有个

结点。那么，第i-1层至多有个结点。

须证明

j=i时命题也成立。因为二叉树每个结点的度至多为2

第i层上最大结点数是第i-1层的2倍，即

故命题得证。34性质2：

深度为k的二叉树中，最多具有2k-1个结点。证明：根据性质1，当深度为k的二叉树每一层都达到最多结点时，它的和最大，即：35两类特殊的二叉树：满二叉树：定义：一棵深度为k且有2k–1个结点的二叉树称为满二叉树。特点：满二叉树每一层上的结点都具有最大的结点数。123114589121367101415深度为k=4的满二叉树36完全二叉树：定义：深度为k，有

n个结点的二叉树，当且仅当其每一个结点

都与深度为

k的满二叉树中编号从

1

至

n的结点一一对

应时，称为完全二叉树。特点：叶子结点只可能在层次最大的两层上出现。对任一结点，若其右分支下子孙的最大层次为L，则其左分

支下子孙的最大层次必为

L或

L+1完全二叉树123114589126710371234567123456特点：完全二叉树除最后一层外，其余各层都是满的；并且最后一层或者为满，或者仅在右边缺少连续若干个结点。38性质3：不大于x的最大整数证明：设完全二叉树的深度为k，结点数为n，

由性质2和完全二叉树的定义可知：2k-1-1<n2k-1

即2k-1

n

<2k两边取对数有：

k-1log2n

<k

对k取整数：

k=log2n+139性质4：如果对一棵有n个结点的完全二叉树的结点按层序编号，

则对任一结点

i(1in)，有：(1)若i=1，则序号为

i的结点是根结点。

若i>1,则序号为i的结点的父结点的序号为i/2。(2)若2i<=n，则序号为i的结点的左孩子结点的序号为2i。

若2i>n，则序号为i的结点无左孩子。(3)若2i+1<=n，则序号为i的结点的右孩子结点的序号为

2i+1

若2i+1>n，则序号为i的结点无右孩子。40性质5：对任何一棵二叉树T，如果其终端结点数为

n0，度为

2

的

结点数为

n2，则

n0=n2+1。证明：n1为二叉树

T中度为

1

的结点数因为：二叉树中所有结点的度均小于或等于2所以：其结点总数n=n0+n1+n2

又二叉树中，除根结点外，其余结点都只有一个分支进入设B为分支总数，则

n=B+1

又：分支由度为1和度为2的结点射出，

B=n1+2n2

于是，n=B+1=n1+2n2+1=n0+n1+n2n0=n2+1413.二叉树的存储结构(1)

顺序存储结构一维数组存储法：实现：按完全二叉树的结点层次编号，依次存放二叉树中的数据元素。特点：结点间关系蕴含在其存储位置中（i的左子2i，右子2i+1）。abcdefgabcde0000fg

123456789101142特点：浪费空间，适于存满二叉树和完全二叉树。aceda0c000d0000

123456789101112131400e43无须按完全二叉树的结点层次编号，依次按编号存放二叉树中的数据元素即可。结点数据，左子编号，右子编号均要存储。故可采用长度为n的结构数组存放。n为结点个数。结构数组相当于一个二维构造,第一维是结构数组元素,每个元素是一个结构变量,第二维是结构成员。

abcdefg0123456Data[0]Lno[1]Rno[2][0]a12[1]b34[2]c-1-1[3]d-1-1[4]e56[5]f-1-1[6]g-1-1二维数组存储法：44顺序存储结构小结：满二叉树或完全二叉树可采用一维数组；结点少，层数高可采用二维数组；查找方便，找孩子结点及父结点均方便；缺点：空间扩充不便；插入和删除须大量移动数据。45二叉链表：结点组成：lchilddatarchildABCDEFG

AB

C

D

E

F

G^^^^^^^^其中：data为数据域；

lchild为左指针域，放左子树的地址；

rchild为右指针域，放右子树的地址；BT：名字，根，入口(2)

链式存储结构46

二叉链表的定义：typedefstructnode{datatypedata;structnode*lchild,*rchild;}BT;47三叉链表：三叉链表的定义：typedefstructnode{datatypedata;structnode*lchild,*rchild,*parent;}TT;lchilddata

parent

rchildABCDEFG

A

B

C

D

E

F

G^^^^^^^^^结点组成：48三叉链表的静态结构：ABCDFErootdata

parent

leftChildrightChild012345A

-11-1B023C1

-1-1D145E3-1-1F3-1-1496.3遍历二叉树501.问题的提出

顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。访问的含义可以很广，如：输出结点的信息等。

遍历是任何类型均有的操作。对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构，每个结点有两个后继，则存在如何遍历即按什么样的搜索路径遍历的问题。51对二叉树而言，可以有三条搜索路径：1．先上后下的按层次遍历；2．先左（子树）后右（子树）的遍历；3．先右（子树）后左（子树）的遍历。52先序（根）的遍历算法中序（根）的遍历算法后序（根）的遍历算法2.先左后右遍历二叉树的算法53(1)先序（根）遍历（DLR）先序遍历也称为先根遍历。其递归过程为：若二叉树为空，则遍历结束，返回。否则：（1）访问根结点；（2）先序遍历根结点的左子树；（3）先序遍历根结点的右子树。3.遍历二叉树的递归算法54voidPreorder(BT*T) //先序遍历T所指向的二叉树{if(T==NULL)return; //本函数调用结束

{printf(T->data); //输出结点的数据域

Preorder(T->lchild); //先序递归遍历左子树

Preorder(T->rchild); //先序递归遍历右子树

}//本函数调用结束}typedefstructnode{datatypedata;structnode*lchild,*rchild;}BT;算法描述：55ADBCDLRADLRDLR>B>>D>>CDLR先序遍历序列：ABDC

先序遍历:56voidpreorder(BT*T){if(T==NULL)return;{printf("%d\t",T->data);preorder(T->lchild);preorder(T->rchild);}}主程序Pre(T)返回返回pre(TR);返回返回pre(TR);ACBDTBprintf(B);pre(TL);BTAprintf(A);pre(TL);ATDprintf(D);pre(TL);DTCprintf(C);pre(TL);C返回T>左是空返回pre(TR);T>左是空返回T>右是空返回T>左是空返回T>右是空返回pre(TR);先序序列：ABDC57(2)中序（根）遍历（LDR）中序遍历也称为中根遍历。其递归过程为：若二叉树为空，则遍历结束，返回。否则：（1）中序遍历根结点的左子树；（2）访问根结点；（3）中序遍历根结点的右子树。58算法描述：typedefstructnode{datatypedata;structnode*lchild,*rchild;}BT;voidInorder(BT*T) //中序遍历T所指向的二叉树{if(T

==NULL)return;

//本函数调用结束

{Inorder(T->lchild);

//中序递归遍历左子树

printf(T->data);

//输出结点的数据域

Inorder(T->rchild);//中序递归遍历右子树

}//本函数调用结束}59ADBCLDRBLDRLDR>A>>D>>CLDR中序遍历序列：BDAC

中序遍历:60(3)后序（根）遍历（LRD）后序遍历也称为后根遍历。其递归过程为：若二叉树为空，则遍历结束，返回。否则：（1）后序遍历根结点的左子树；（2）后序遍历根结点的右子树。（3）访问根结点；61算法描述：typedefstructnode{datatypedata;structnode*lchild,*rchild;}BT;voidPostorder(BT*T)//后序遍历T所指向的二叉树{if(T

==NULL)return; //本函数调用结束

{Postorder(T->lchild); //后序递归遍历左子树

Postorder(T->rchild); //后序递归遍历右子树

printf(T->data);//输出结点的数据域

}//本函数调用结束}62ADBC

LRDLRDLRD>A>>D>>CLRD后序遍历序列：DBCA

后序遍历:B63（1）先序遍历的非递归算法*提高运算效率基于栈先序遍历的非递归算法：引入栈保存每个结点的右指针算法：1）访问结点。2）结点的右指针入栈。3）若结点的左指针不空，遍历左子树。4）右指针出栈。5）若结点的右指针不空，遍历右子树。4.遍历二叉树的非递归算法64（2）中序遍历的非递归算法基于栈中序遍历的非递归算法：引入栈保存每个结点及右指针，由于知道结点的指针便可知结点和其右指针，故只须结点的指针入栈。算法：1）结点右指针入栈。2）若结点的左指针不空，遍历左子树。3）指针出栈。4）访问结点，若结点的右指针不空，遍历右子树。65算法实现：voidinorderse(BT*bt){inti=0;

//栈的初始化BT*p,*s[M];//保存每个结点的指针的栈

p=bt;do{while(p!=NULL){s[i++]=p;//结点的指针入栈

p=p->lchild;//进入左子树}//左子树为空，退出

if(i>0)//如果栈不空{p=s[--i];//结点的指针出栈printf(“%d\t”,p->data);//访问出栈的结点p=p->rchild;}}while(i>0||p!=NULL);//右子树为空同时栈空，结束循环}66非递归算法栈操作图ABCDEFGpiP->A(1)ABCDEFGpiP->AP->B(2)ABCDEFGpiP->AP->BP->C(3)P=nullABCDEFGiP->AP->B访问：C(4)67pABCDEFGiP->A访问：CB(5)ABCDEFGiP->AP->D访问：CBp(6)ABCDEFGiP->AP->DP->E访问：CBp(7)ABCDEFGiP->AP->D访问：CBEp(8)68ABCDEFGiP->AP->DP->G访问：CBEP=NULL(9)ABCDEFGiP->A访问：CBEGDp(11)ABCDEFGiP->AP->F访问：CBEGDp(12)ABCDEFGiP->AP->D访问：CBEGp(10)69ABCDEFGiP->A访问：CBEGDFp=NULL(13)ABCDEFGi访问：CBEGDFAp(14)i访问：CBEGDFAp=NULLABCDEFG(15)705.层次遍历二叉树的算法

按照自上而下（从根结点开始），从左到右的顺序逐层访问二叉树上的所有结点，称为按层次遍历。按层次遍历时，当一层结点访问完后，接着访问下一层的结点，先遇到的结点先访问，这与队列的操作原则是一致的。在层次遍历时，可设置一个数组来模拟队列，用于保存被访问结点的子结点的地址。遍历从二叉树的根结点开始，首先将根结点指针入队列，然后从队头取出一个元素，每取一个元素，执行下面两个操作：（1）访问该元素所指结点；（2）若该元素所指结点的左、右孩子结点非空，则将该元素所指结点的左孩子指针和右孩子指针依次入队。此过程不断进行，直到队空为止。71在层次遍历算法中，以二叉链表方式存储，lchild和rchild分别是被访问结点的左、右指针。一维数组q[MAXLEN]用以实现队列。72算法描述：

voidLevelorder(BT*T)//按层次遍历二叉树BT,T为指向根结点的指针{inti,j;BT*q[MAXLEN],*p;//q为指针数组用以模拟队列,每个元素均为指向BT类型的指针,用来存放结点地址

p=T;if(p!=NULL) //若二叉树非空，则根结点地址入队

{i=1;q[i]=p;j=2;}//i指向对头，j指向对尾while(i!=j)//当队列不为空时执行循环{p=q[i];printf(p->data);//访问队首结点的数据域

if(p->lchild!=NULL){q[j]=p->lchild;j++;}//将出队结点的左孩子的地址入队if(p->rchild!=NULL){q[j]=p->rchild;j++;}//将出队结点的右孩子的地址入队i++;

}}73层次遍历:ABCDEHIFGK层次遍历的序列:ABCDEFGHIK74例：

有二叉树如图所示，求它的先根遍历、中根遍历、后根遍历和层次遍历的输出序列。ABCIKFEDHG先根遍历的序列：

ABDGEHCFIK中根遍历的序列：

DGBHEAFKIC后根遍历的序列：

GDHEBKIFCA层次遍历的序列：

ABCDEFGHIK75例：设表达式A–B*（C+D）+E/（F+G）的二叉树表示如图所示。试写出它的先根遍历、中根遍历和后根遍历输出序列。A*/EF++BDC-+G先根遍历结果（即前缀表达式）：

+–A*B+CD/E+FG中根遍历结果：

A–B*C+D+E/F+G后根遍历结果（即后缀表达式）：

ABCD+*–EFG+/+766.4恢复二叉树77根据已知的先根序列、中根序列、后根序列得到一棵二叉树称为恢复二叉树。问题的由来：在数据量很大的结构中，如在绘图软件中，如何存储一个用树表示的图形结构？处理方法：

对于链表结构的图形结构：

（1）把每个结点去掉指针项，将结点的数据按中序存储于数组中得到中序结点表。

（2）把每个结点去掉指针项，将结点的数据按先序或后序存储于数组中得到序表。图形结构调入内存时要恢复二叉树。有二种方法：

（1）根据中序数组、先序数组恢复二叉树。

（2）根据中序数组、后序数组恢复二叉树。781.由先根、中根恢复二叉树步骤：（1）根据先根序列的第一个元素确定根结点；在中根序列中找到该根结点，

确定该根结点的左、右子树的中根序列；再在先根序列中确定此左、右子树的先根序列；（2）根据左、右子树的先根序列分别找出左子树和右子树的根结点，并把左、右子树的根结点连到父结点上去；（3）再对左、右子树按此方法找出根结点和左、右子树；

如此递归下去，当取尽先根序列中的结点时，便恢复了一棵二叉树。79例：由下列先根序列和中根序列恢复二叉树。先根序列：ACBRSEDFMLK中根序列：RBSCEAFDLKM80例：前序：ACBRSEDFMLK中序：RBSCEAFDLKM前序：

A

CBRSEDFMLK中序：

RBSCE

A

FDLKMA左子树右子树左子树右子树81例：前序：ACBRSEDFMLK中序：RBSCEAFDLKM前序：

A

C

BRSEDFMLK中序：

RBS

CEAFDLKMA左子树右子树左子树右子树CD82例：前序：ACBRSEDFMLK中序：RBSCEAFDLKM前序：

ACBRSEDFMLK中序：

RBSCEAFDLKMA左子树左子树右子树右子树CD左子树右子树左子树右子树83例：前序：ACBRSEDFMLK中序：RBSCEAFDLKMA左子树左子树右子树右子树CD左子树右子树左子树右子树BEFM前序：ACBRSEDFMLK中序：RBSCEAFDLKM84例：前序：ACBRSEDFMLK中序：RBSCEAFDLKMA左子树左子树右子树CDBEFM左子树右子树左子树前序：ACBRSEDFMLK中序：RBSCEAFDLKM85例：前序：ACBRSEDFMLK中序：RBSCEAFDLKMA左子树左子树右子树CDBEFMRS左子树右子树左子树LK前序：ACBRSEDFML

K中序：RBSCEAFDLKM862.由后根、中根恢复二叉树步骤：（1）根据后根序列的最后一个元素确定根结点；在中根序列中找到该根结点，

确定该根结点的左、右子树的中根序列；再在后根序列中确定此左、右子树的后根序列；（2）根据左、右子树的后根序列分别找出左子树和右子树的根结点，并把左、右子树的根结点连到父结点上去；（3）再对左、右子树按此方法找出根结点和左、右子树；

如此递归下去，当取尽后根序列中的结点时，便恢复了一棵二叉树。87例：由下列中根序列和后根序列恢复二叉树。后根序列：CEDBHGJIFA中根序列：CBEDAGHFJI88例：后序：CEDBHGJIFA中序：CBEDAGHFJIA左子树右子树左子树右子树后序：CEDBHGJIFA中序：CBEDAGHFJI89例：后序：CEDBHGJIFA中序：CBEDAGHFJIA左子树右子树左子树右子树BF后序：CEDBHGJIFA中序：CBEDAGHFJI90例：后序：CEDBHGJIFA中序：CBEDAGHFJIABF左子树左子树右子树右子树左子树右子树左子树右子树后序：CEDBHGJIFA中序：CBEDAGHFJI91例：后序：CEDBHGJIFA中序：CBEDAGHFJIABF左子树左子树右子树右子树左子树右子树左子树右子树CDGI后序：CEDBHGJIFA中序：CBEDAGHFJI92例：后序：CEDBHGJIFA中序：CBEDAGHFJIABF左子树左子树右子树CDGIEHJ后序：CEDBHGJIFA中序：CBEDAGHFJI936.5线索二叉树94对二叉树的遍历可得到三种序列：先序、中序、后序序列。均为线性序列。结点至多有一个直接前驱和直接后继。在二叉链表中找孩子结点容易，但找这样的直接前驱和直接后继不行。利用二叉链表中的空指针域，存储直接前驱和直接后继的指针（为区别起见此时指针称为线索）。带有线索的二叉树称为线索二叉树。对二叉树以某种次序遍历改变空指针域为线索，使其变为线索二叉树的过程称为线索化。1.线索二叉树95∧

A∧

∧

B∧

A∧

两个结点的二叉链表

单结点的二叉链表图

在二叉链表存储的二叉树中：单个结点的二叉树有2个空指针域，如图所示。两个结点的二叉树有3个空指针域，如图所示。96可以证明：一个具有n个结点的二叉树，若采用二叉链表存储结构，在总共2n个指针域中，只有n­1个指针域用来存储结点子树的地址，另外n+1个都是空指针域。证明：度为0的结点数为n0每个结点有2个空链域。度为1的结点数为n1每个结点有1个空链域。度为2的结点数为n2每个结点没有空链域。

所以空链域数=2n0+n1

把性质5（对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1）代入上式得：

空链域数=2n0+n1=n0+n0+n1=n0+n2+1+n1=n0+n1+n2+1=n+1性质：含有n个结点的二叉链表中有n+1个空指针域。972.线索化二叉树的方法同理，对二叉树的不同遍历可得到三种序列的线索二叉树：先序线索二叉树、中序线索二叉树（用得多）、后序线索二叉树。typedefstructnode{intdata;intlt,rt;structnode*lc,*rc;}BT;

在线索二叉树的结点中增加两个标志域：lt:若lt=0,lc域为指针指向左孩子

若lt=1,lc域为线索指向其前驱rt:若rt=0,rc域为指针指向右孩子

若rt=1,rc域为线索

指向其后继（1）结点定义

lcltdatartrc98ABCDE

A

B

D

C

ET先序序列：ABCDE先序线索二叉树00001111^11（2）先序线索二叉树99ABCDE

A

B

D

C

ET中序序列：BCAED中序线索二叉树00001111^11^（3）中序线索二叉树100ABCDE

A

B

D

C

ET后序序列：CBEDA后序线索二叉树0000111111^(4)

后序线索二叉树101ABCDE头结点：lt=0,lc指向根结点rt=1,rc指向头结点自己遍历序列中第一个结点的

lc最后一个结点的

rc

均指向头结点

A

B

D

C

ET中序序列：BCAED中序线索二叉树00001111^11^(5)

中序线索二叉树

0A0

1B0

0D1

1C1

1E1T中序序列：BCAED带头结点的中序线索二叉树

01102(6)

按中序线索化二叉树算法实现ABCDEt

0

1prpiP->A

A

B

D

C

Ebt^^^^^^0000000000BT*zxxsh(BT*bt){BT*p,*pr,*s[M],*t;inti=0;

t=(BT*)malloc(sizeof(BT));t->lt=0;t->rt=1;t->rc=t;if(bt==NULL)t->lc=t;else{t->lc=bt;pr=t;p=bt;do{while(p!=NULL) {s[i++]=p;p=p->lc;} if(i>0) {p=s[--i]; printf("%c",p->data);

if(p->lc==NULL) {p->lt=1;p->lc=pr;}

if(pr->rc==NULL) {pr->rt=1;pr->rc=p;}

pr=p;p=p->rc; }}while(i>0||p!=NULL);

pr->rc=t;pr->rt=1;t->rc=pr;}return(t);}p103BT*zxxsh(BT*bt){JD*p,*pr,*s[M],*t;inti=0;

t=(BT*)malloc(sizeof(BT));t->lt=0;t->rt=1;t->rc=t;if(bt==NULL)t->lc=t;else{t->lc=bt;pr=t;p=bt;do{while(p!=NULL) {s[i++]=p;p=p->lc;} if(i>0) {p=s[--i]; printf("%c",p->data);

if(p->lc==NULL) {p->lt=1;p->lc=pr;}

if(pr->rc==NULL) {pr->rt=1;pr->rc=p;}

pr=p;p=p->rc; }}while(i>0||p!=NULL);

pr->rc=t;pr->rt=1;t->rc=pr;}return(t);}ABCDE

A

B

D

C

Ebt^^^^^^t

0

1prpiP->AP->B0000000000104Ch5_20.cABCDE

A

B

D

C

Ebt^^^^^^t

0

1prP=NULLiP->AP->BBT*zxxsh(BT*bt){JD*p,*pr,*s[M],*t;inti=0;

t=(BT*)malloc(sizeof(BT));t->lt=0;t->rt=1;t->rc=t;if(bt==NULL)t->lc=t;else{t->lc=bt;pr=t;p=bt;do{while(p!=NULL) {s[i++]=p;p=p->lc;} if(i>0) {p=s[--i]; printf("%c",p->data);

if(p->lc==NULL) {p->lt=1;p->lc=pr;}

if(pr->rc==NULL) {pr->rt=1;pr->rc=p;}

pr=p;p=p->rc; }}while(i>0||p!=NULL);

pr->rc=t;pr->rt=1;t->rc=pr;}return(t);}0000000000p105Ch5_20.cABCDE

A

B

D

C

Ebt^^^^^^t

0

1prPiP->A输出:BBT*zxxsh(BT*bt){JD*p,*pr,*s[M],*t;inti=0;

t=(BT*)malloc(sizeof(BT));t->lt=0;t->rt=1;t->rc=t;if(bt==NULL)t->lc=t;else{t->lc=bt;pr=t;p=bt;do{while(p!=NULL) {s[i++]=p;p=p->lc;}if(i>0) {p=s[--i]; printf("%c",p->data);

if(p->lc==NULL) {p->lt=1;p->lc=pr;}

if(pr->rc==NULL) {pr->rt=1;pr->rc=p;}

pr=p;p=p->rc; }}while(i>0||p!=NULL);

pr->rc=t;pr->rt=1;t->rc=pr;}return(t);}00000000001106Ch5_20.cABCDE

A

B

D

C

Ebt^^^^^t

0

1prP输出:BiP->ABT*zxxsh(BT*bt){JD*p,*pr,*s[M],*t;inti=0;

t=(BT*)malloc(sizeof(BT));t->lt=0;t->rt=1;t->rc=t;if(bt==NULL)t->lc=t;else{t->lc=bt;pr=t;p=bt;do{while(p!=NULL) {s[i++]=p;p=p->lc;}if(i>0) {p=s[--i]; printf("%c",p->data);

if(p->lc==NULL) {p->lt=1;p->lc=pr;}

if(pr->rc==NULL) {pr->rt=1;pr->rc=p;}

pr=p;p=p->rc; }}while(i>0||p!=NULL);

pr->rc=t;pr->rt=1;t->rc=pr;}return(t);}0000100000107Ch5_20.cABCDE

A

B

D

C

Ebt^^^^^t

0

1prP输出:BiP->AP->CBT*zxxsh(BT*bt){JD*p,*pr,*s[M],*t;inti=0;

t=(BT*)malloc(sizeof(BT));t->lt=0;t->rt=1;t->rc=t;if(bt==NULL)t->lc=t;else{t->lc=bt;pr=t;p=bt;do{while(p!=NULL) {s[i++]=p;p=p->lc;}if(i>0) {p=s[--i]; printf("%c",p->data);

if(p->lc==NULL) {p->lt=1;p->lc=pr;}

if(pr->rc==NULL) {pr->rt=1;pr->rc=p;}

pr=p;p=p->rc; }}while(i>0||p!=NULL);

pr->rc=t;pr->rt=1;t->rc=pr;}return(t);}0000100000108Ch5_20.cABCDE

A

B

D

C

Ebt^^^^^t

0

1prP=NULLiP->AP->C输出:BBT*zxxsh(BT*bt){BT*p,*pr,*s[M],*t;inti=0;

t=(BT*)malloc(sizeof(BT));t->lt=0;t->rt=1;t->rc=t;if(bt==NULL)t->lc=t;else{t->lc=bt;pr=t;p=bt;do{while(p!=NULL) {s[i++]=p;p=p->lc;} if(i>0) {p=s[--i]; printf("%c",p->data);

if(p->lc==NULL) {p->lt=1;p->lc=pr;}

if(pr->rc==NULL) {pr->rt=1;pr->rc=p;}

pr=p;p=p->rc; }}while(i>0||p!=NULL);

pr->rc=t;pr->rt=1;t->rc=pr;}return(t);}0000100000P109Ch5_20.cABCDE

A

B

D

C

Ebt^^^^^t

0

1prPiP->A输出:BCBT*zxxsh(JD*bt){JD*p,*pr,*s[M],*t;inti=0;

t=(BT*)malloc(sizeof(BT));t->lt=0;t->rt=1;t->rc=t;if(bt==NULL)t->lc=t;else{t->lc=bt;pr=t;p=bt;do{while(p!=NULL) {s[i++]=p;p=p->lc;} if(i>0) {p=s[--i]; printf("%c",p->data);

if(p->lc==NULL) {p->lt=1;p->lc=pr;}

if(pr->rc==NULL) {pr->rt=1;pr->rc=p;}

pr=p;p=p->rc; }}while(i>0||p!=NULL);

pr->rc=t;pr->rt=1;t->rc=pr;}return(t);}00001000001P->C110Ch5_20.cABCDE

A

B

D

C

Ebt^^^^t

0

1prP=NULLiP->A输出:BC

BT*zxxsh(BT*bt){JD*p,*pr,*s[M],*t;inti=0;

t=(BT*)malloc(sizeof(BT));t->lt=0;t->rt=1;t->rc=t;if(bt==NULL)t->lc=t;else{t->lc=bt;pr=t;p=bt;do{while(p!=NULL) {s[i++]=p;p=p->lc;} if(i>0) {p=s[--i]; printf("%c",p->data);

if(p->lc==NULL) {p->lt=1;p->lc=pr;}

if(pr->rc==NULL) {pr->rt=1;pr->rc=p;}

pr=p;p=p->rc; }}while(i>0||p!=NULL);

pr->rc=t;pr->rt=1;t->rc=pr;}return(t);}0000100010111Ch5_20.cABCDE

A

B

D

C

Ebt^^^^t

0

1prPi输出:BCABT*zxxsh(BT*bt){JD*p,*pr,*s[M],*t;inti=0;

t=(BT*)malloc(sizeof(BT));t->lt=0;t->rt=1;t->rc=t;if(bt==NULL)t->lc=t;else{t->lc=bt;pr=t;p=bt;do{while(p!=NULL) {s[i++]=p;p=p->lc;} if(i>0) {p=s[--i]; printf("%c",p->data);

if(p->lc==NULL) {p->lt=1;p->lc=pr;}

if(pr->rc==NULL) {pr->rt=1;pr->rc=p;}

pr=p;p=p->rc; }}while(i>0||p!=NULL);

pr->rc=t;pr->rt=1;t->rc=pr;}return(t);}00001000101P->A112Ch5_20.cABCDE

A

B

D

C

Ebt^^^t

0

1P输出:BCA

priP->DBT*zxxsh(BT*bt){JD*p,*pr,*s[M],*t;inti=0;

t=(BT*)malloc(sizeof(BT));t->lt=0;t->rt=1;t->rc=t;if(bt==NULL)t->lc=t;else{t->lc=bt;pr=t;p=bt;do{while(p!=NULL) {s[i++]=p;p=p->lc;} if(i>0) {p=s[--i]; printf("%c",p->data);

if(p->lc==NULL) {p->lt=1;p->lc=pr;}

if(pr->rc==NULL) {pr->rt=1;pr->rc=p;}

pr=p;p=p->rc; }}while(i>0||p!=NULL);

pr->rc=t;pr->rt=1;t->rc=pr;}return(t);}0000101010113Ch5_20.cABCDE

A

B

D

C

Ebt^^^t

0

1Pi输出:BCA

prP->DBT*zxxsh(BT*bt){JD*p,*pr,*s[M],*t;inti=0;

t=(BT*)malloc(sizeof(BT));t->lt=0;t->rt=1;t->rc=t;if(bt==NULL)t->lc=t;else{t->lc=bt;pr=t;p=bt;do{while(p!=NULL) {s[i++]=p;p=p->lc;} if(i>0) {p=s[--i]; printf("%c",p->data);

if(p->lc==NULL) {p->lt=1;p->lc=pr;}

if(pr->rc==NULL