计算机-数据结构和二叉树

树的有关概二叉二叉树的遍遍历的应线索二叉哈尔滨工业大学(威海)计算机科学与技树和森树及其应1重点：(1)二叉树的定义、结构特点和性质树的有关概遍历方式的递归和非递归算法。(3)二叉树的线索二叉过程和算法；(4)最优二叉树的特性及建立最优二二叉树的遍树 编码的方法遍历的应难点：二叉树的线索化算法；设计解决与树或二叉线索二叉相关的应用问题的有效算树和森树及其应23二叉树的设计，二叉树结构的特点，三

树的有关概树的概树的应树的表

A树的有关术

D了树的概念。 了树的概念。

6.1T={A,B,C,D,E,F,G,H,I,T1={B,E,F，K，L},T2={C,G},T3={D,H,I, A 6

A

族谱：设某家庭有13个成员A、B、C、D、E、F(无前驱最后一个数据元

根结点(无前多个叶子结点(无后继

G、H、I、J，K，L，M他们之间的关系可下图所示的树表示A 其它数据元(一个前驱、一个后继

其它数据元(一个前驱、多个后继

单位行政机构的组织关

树形表示

凹入表示A 计算机的文件系统：不论是DOS文件系统还Windows文件系统，所有的文件是用树的形式来C

文件夹 文件夹 文件 文件

AABFCGDHIJ文件夹11文件夹12文件11文件

嵌套集合表示法（文氏图AAA D

广义表表示(A）第一(A(B, 第二(A(B(E,F),C(GD(H,IJ)))第三 MI

(A(B(E(K,L),FC(G 第四 G

6.1结点的度：结点 叶子结点0树的度为树的深度为 树的度为树的深度为

点除叶结点外，其余的都是分支结点有序树： 去掉根，

第2第3

第4

树的抽象数据型 A

ADTTree数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D为空集，则称为空树；否则：在D中存在唯一的称为根的数据元素则R集为空当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm，其中每

称为根root 类、删除类操作} 查找 Root(T)//求树的根结Value(T,cur_e)//求当前结点的元素值Parent(T,cur_e)//求当前结点的双亲结点LeftChild(Tcur_e)//求当前结点的最左孩子RightSibling(Tcur_e)求当前结点的右兄弟TreeEmpty(T)//判定树是否为空树TreeDepth(T)//求树的深度TraverseTreeTVisit())遍

树ADT的基本操作类类InitTree(&T)//初始化置空树CreateTree(&T,definition) //按定义构造树Assign(T,cur_e,value) //给当前结点赋值InsertChild(&T,&p,i,//将以c为根的 为结点p的第i 删除ClearTree(&T)//将树清空DestroyTree(&T)//销毁树的结构DeleteChild(&T&pi)删除结点p的第i棵

树的有关概二叉二叉树的遍遍历的应线索二叉树和森树及其应 二叉树是一种分支结构的对象，在树的概念中，每一个结点孩子的个数没有限制，因此树的形态种多样，本节主要讨论一种最简单的树——二叉树A

二叉二叉树 结 G 二叉树或为空树，或由根及两颗不相交的

构成，并且左、 本身也是二叉树说明二叉树中每个结点最多有两 ；即二叉树每个左、 不能颠倒——有序树二叉树是递归结构，在二叉树的定义中又用到了二

G

G树的概念

二叉树是有左φ

用二叉树表示计算表达式-(a)空 (b)仅有 (c)

根节点是运算符 a+b*(c-d)-(d) (e)左、 均 二叉二叉树 结

性质1在二叉树的第i(i≥1)层上至多有2i-1个结点。证明：最多结点数为各层结点个数相加，1+2+4+…+2k-1=2k- E I 完全二叉树：二叉树中所含的n个结点和满二叉树中

完全二叉树：二叉树中所含的n个结点和满二叉树中 1

E 结论：结论：满二叉树一定是完全二叉树，反之不一

89结论：满二结论：满二叉树一定是完全二叉树，反之不一性质3具有n个结点的完全二叉树的深度为log2n证明：设所求完全二叉树的深度为

性质4对任意二叉树T，如果度数为0的结点数为n0数1结点数的为n1,度数为2的结点数为n2，则n0=n2+1证明：二叉树T的结点总数

2k-1-1＜n≤2k-

k层的最多结

二叉树的分支总数b=n-1（根结点无进入分支）由此可以推出：2k-1取对数得 由于k为整数，故有k-1=logn

则有分支总数b=n1+2*n2

log2n

D

由(1)(2)(3)得求得 E 性质2:深性质2:深度为k的二叉树最多有2k-1个结点 性质5:若对含n个结点的完全二叉树从上到下且从左至右进 i/2的结点为其双亲 为2i的结点 为

i=1是根结 点 双亲为i/2 为 为双亲为双亲为i/2 为 为双亲为i/2

二叉二叉树 结

二叉树的顺 表二叉树的链 表 性质5:若对n结点的完全二叉树从上到下

二叉树的顺 表

至右进行1至n ，则对完全二叉树中任意一

i结点i

采用一维数组，按层序顺序

A

通过通过性质5把二叉树的非线性结构轻易转化成了线性结构

1 4

6

9

ABCDEFABCDEFGHIJ 二叉树的顺 表

二叉树的顺 表 B 说明：顺 方式对于畸形二叉树，浪费说明：顺 方式对于畸形二叉树，浪费较大空间 0JABC0E0G00J1

6 9 6.2.3二叉树 6.2.3二叉树 二叉树的链 表二叉链

二叉树的链 表A

左指针域、右指针域。C语言的类型描述如下typedefstructBiTNode{DataTypedata;structBiTNode*lch,}BiTNode,*

F二叉

C

AA∧CB∧C∧∧∧∧E∧∧∧二叉链表图 性质6：n个结点的二叉树中，共有性质6：n个结点的二叉树中，共有n+1

6.2.3二叉树 二叉树的链 表C∧EC∧E∧AB∧AB∧∧D∧∧F二叉

针域的结点；∧∧数为：2n（n-1）=

含四个域：数据域、左指针域、右指针域、双亲指针结点C语言的类型描述如下typedefstructBiTNode{DataTypedata;structBiTNode}BiTNode,* 6.2.3二叉树 6.2.3二叉树 二叉树的链 表 A

ABB

BiTree*{t=C t‐>data=CDE t‐>lch=DE t‐>rch=F returnt;F} 树的有关概二叉二叉树的遍遍历的应线索二叉树和森树及其应

二叉树的遍历 6.3二叉树的遍遍历：按某种搜索路

二叉树的遍历“遍历”是任何类型均有的操索路径 而且每个结点仅 一次 6.3二叉树的遍对“二叉树”而言，可以有三条搜索路径

二叉树的遍历方二叉树由根、 、 二叉树的遍历可以分解为 和遍历 先右 ）后左

TLR，LTR，LRTRL，RTL，RL

GTLR、LTR、LRT，分 6.3.1二叉树的遍历方法先序遍历（TL F F 例先序遍历右图所示的二叉 根结点先序遍历 ：即按TLR的顺序遍历先序遍历 ：即按TLR的顺序遍历

二叉树的遍历方法中序遍历（LTR法A G 中序遍历右图所示的二叉DBG,E,A,C 二叉树的遍历方法后序遍历（LRT

二叉树的遍历方法 先序遍历、中序遍历、后序遍历下图所示的二叉树例

G

先序：-,+,a,*,b,- 后序遍历 ：即按LRT的顺序遍历 ：即按LRT的顺序遍历根结点后序遍历序列：

中序：a,+,b,*,c,-,d,-：

6.3二叉树的遍历

先序遍历（TLR） 若二叉树为空，结束——基本项（也叫终止项若二叉树非空——

voidPreOrder(BiTreeT){if(T){∧PreOrder(T->lch);PreOrder(T-∧}}先序序列

* /*/a∧-∧a∧-∧d∧∧b∧∧b∧∧c∧+a*(b-+

voidInOrder(BiTreeT) if*{*∧a∧visit(T->data)；∧a∧∧b∧b∧}中序序列

++/-∧d-∧d∧∧e∧∧c∧∧a*(b-∧*abcde称为前缀表达

a*b–c+de称为中缀表达

6.3二叉树的遍历+voidPostOrder(BiTree+if*/{*/∧a∧-∧d∧∧e∧∧a∧-∧d∧∧e∧∧b∧∧b∧∧c∧}a*(b-后序序列abc*de/+称为后缀表达

1序遍历（TLR）的非递归算对每个结点，在完后，沿其左链一直下来，直到左链为空，这时，所有已被过的结点进栈。然后结点出栈，对于每个出栈结点，即表示该结点和其左已被结束，应该该结点的右。

voidvoidPreOrder(BiTreet)PSeqStackBiTreep=t;/**/S=Init_SeqStack();/*栈初始化*/whilep||!Empty_SeqStack{if(p)visit(p->data)/*预留p指针在栈中*/Push_SeqStackSp);p=p->lch;}Pop_SeqStack(S,&pp=p-}/* }//end}//end 先序遍历的非递归算 voidPreOrder(NODE*root)

+ + NODE*p,*node[MAX];inttop=0;p=root;dowhile(p!=NULL){

toptoptoptop

node[

p p- p pp }if(top>0)top--; p=p->rch;}while(top>0||}

,op]ta); ;;p=p->lch;

BiTNode*GoFarLeft(BiTreeT,Stack*S)if(!T)returnwhile(T->lch) Push(S,

StacktGoFarLeft(TS);找到最左下的结while(t){T=T-}

if(t-t=GoFarLeft(t->rch,elseifStackEmpty(S 栈不空时退return }

}//}//

t=tNULL栈空表明

typedefstruct{BiTNode*node;intflag;typedefstruct{BiTNode*node;intflag;voidPostOrder(BiTreet){PSeqStackS;DataTypeinttag;BiTreep=S=Init_SeqStack();/*栈初始化*/whilep||!Empty_SeqStack(Sif(p)Sq.flag=0;Push_SeqStack(S,p=p-}Pop_SeqStack(S,&Sq);p=Sq.node;if(Sq.flag==0)/*二次压栈*/Push_SeqStackS,Sq);p=p->rch;}elsevisit(p-p=null;///*把p赋空从 }}//end}end A

voidLevelOrder(BiTreeT){BiTreeP=T;if(P) ueue(Q);//初始化队

visit(P); ueue(Q,P); 根结点，并将根结点入while ueue(Q)){//当队非空时重复执行下 //if(P->lch){visit(P- //处理左孩if(P->rch){visit(P- //处理右孩}} 树的树的有关概二叉二叉树的遍遍历的应线索二叉树和森树及其应 例例求二叉树的叶子数。算法思想：采用任何遍历方法，

intcountleaf(bitreet,intnum){if(t!=NULL){if((t->lch==NULL)&&(t-num=countleaf(t->lch,num);num=countleaf(t->rch,}return} 例求二叉树的深度例求二叉树的深度算法都可求得。下面给出后序遍历求二叉树深度的递归算inttreedepth(bitree*t){inth,lh,rh; else returnh;}

二叉树的遍历

6.4.2二叉树的遍历

给定某两种遍历序列能否唯一确定一棵二叉 DC

给定中序和先

唯一确定一棵二叉答案不唯

给定先序和后序不能唯一确定一棵二叉 6.4.2二叉树的遍历 先序：12463578中序：2641375

6.4.2二叉树的遍历 先中

左 右 6.4.2二叉树的遍历 6.4.2二叉树的遍历

结论可以在遍历过程中对结点进结论可以在遍历过程中对结点进 先序:-,+,a,*,b,-

6.4.3相似且相应结点包含相同信息的二叉树称为等价二叉树

两株二叉树具有相同结构(1)

“形状”相

(2)它们都是非空的，且左 分别具有相同结构 6.4.3

6.4.3intEQUAL(BiTreet1,BiTreet2){intx=0;if(ISEMPTY(t1)&&ISEMPTY(t2))x=1;elseif(!ISEMPTY(t1)&&!ISEMPTY(t2))if(DATA(t1)==DATA(t2))if(EQUAL(LCHILD(t1),LCHILD(t2)))x=EQUAL(RCHILD(t1),RCHILD(t2))return}/*EQUAL

BiTreeCOPY(BiTreeoldtree){BiTreetemp;if(oldtree!=NULL){temp=newNodetemp->lch=COPY(oldtree->lch);temp->rch=COPY(oldtree->rch);temp->data=oldtree->data;return(temp}return(NULL)}

线索二叉树的树的有关概二叉二叉树的遍遍历的应线索二叉树和森树及其应

6.5

个线性序列，即对一个非线性结构进行线性化

利用空链利用空链

链 6.5

6.5typedefstructtypedefstructnodedatatypestructnode*lch,*rch;intltag,rtag;}threadbithptr,

6.5线索：线索二叉树： 先序线索化二叉树、中序线索化二叉树和

6.5线索二叉 二叉树的根结点，其rchild域指向中序遍历时的最后

0*1d1a0-1b1c01010-00-0 A

00000101

11010C010

类似线性链表，为每个线索树增加一个头结点二叉 0000A

1111101G1111101

Thrt->lchT二叉树的根Thrt->lchThrtThrt->rchThrtThrt->lchThrtThrt->rchThrtThrt->ltag=0;Thrt->rtag=1;T0B001D011G

0C11E 1F1先序线索二叉

A0B 0C1D 1E 1F

A

G

线索化的实质是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或后继信息只有在遍历时才能得到，因此线索化的过程即为在遍历过程中修改算法中附设一个指针pre始终指向刚刚过的结点，若指针p指向当前的结点，则pre指向它的前

p指针→当前结点之指针；pre指针→前驱技巧：当结点p的左/右域为空时，只改写它的左域（装入前pre），而其右域（后继）或者说，当前结点的指针p应当送到前驱结点的空右域若p->lch＝NULL,则{p->ltag=1;p//p的前驱结点指针pre存入左空,//p存入其前驱结点pre的右空

pre

前驱结

中序遍历线索已建已建立二叉 ∧ p指 当前结

∧

0∧ ∧

0∧ ∧ ∧ ∧ 增加头结增加头结0

1

StatusInOrderThreading(BiThrTreeif(!(Thrt=(threadbithptr ∧

(sizeof(threadbithptr))))exitThrt->ltag=0;Thrt->rtagThrt->rch 添加 ∧

0∧ ∧

0∧ ∧

return}// ∧G∧ if(!T)Thrt->lch=elseThrt->lch=T; pre=Thrt;

P0

pre->rch=Thrt;pre->rtag=1;Thrt->rch=pre;}

0 ∧

∧0

00∧ ∧

0∧ ∧ ∧ 查找查找 P

if(p //对以p为根的非空二叉树进行线索 //

{p->ltag=

建前p->lch=pre;建后

{pre->rtag= pre->rch=p;pre 1∧

∧ ∧1

1∧ ∧中中序遍历线索化完成

}//}//

// 线索 6.5线索二叉

所有右链为线索的结点，直接指示了结点的后 threadbithptr*InOrderNext(threadbithptr*p)

若其左标志为“1threadbithptrif(p->rtag==1)//*P的 为returnp-else{//*P //从*P的 //找 returnq;(2)当p->rtag(2)当p->rtag=0时，p的 (1)当p->rtag=1时，p->rch即为所求（线索）

p

qq

} threadbithptr*InOrderPre(threadbithptr*pthreadbithptr*q;if(p->ltag==1)//*P的 returnp-else{//*P 非//从*P的 //找 的“最右下”结

if(p!=Null)()//do{ p=InOrderNext(p);找*p}while-return(2)当p->ltag(2)当p->ltag=0时，p的 (1)当p->ltag=1时，p->lch即为所求（线索）}

} 前序线索二叉树上找

中序线索二叉树上找 中序的前驱和后继都往上指向祖结点C的前 后序线索二叉树上找找前驱：若结点有右孩子，则右孩子是其前驱；否则找后继 ，需要知道双010100A000010BC结点C的后继0010BC111E101 111E101

在二叉树中一般不讨论结点 线索树的缺点 11G11 例将结点 作为结点S的右孩子结点若S的 为空，直 并修改线索若S的 非空，则 后原来S的 作为R的。

例将结点 作为结点S的右孩子结点若S的 为空，直 并修改线索若S的 非空，则 后原来S的 作为R的。 前（S的 为空

前（ 非空 后 例将结点(2)若S的VoidVoidRINSERT(threadbithptrS,R){if(S->rtag==1){ //右 R->rch=S->rch;R->rtag=S->rtag;R->ltag=1;R->lch=SS->rtag=0S->rch=R;else{// 非w=InOrderNext(S)Rw->lch //R的中序后继是}}

作为结点S的右孩子结点： 非空，则 后原来S的 作为R的

树的有关概二叉二叉树的遍遍历的应线索二叉树和森树及其应 6.6

双亲双亲//typedefstructPTNodeElemintparent;}

A

data9A09A0B1C1D2E2F3G5H5I5123456采用一组采用一组连续

789

data C CC

child 3 5∧9876∧987

孩子结点结构:

双亲结点结构:

H

typedefstruct //ChildPtr}typedefstructCTNode{ structCTNode}typedefstruct //ChildPtr}typedefstructCTNode{ structCTNode}

∧∧9∧9∧A0B1C1D2∧E2F3∧G5∧H5∧I5∧∧ ∧65 65 7 7

结点结构: ∧98typedefstructCSNode{∧98typedefstructCSNode{ structCSNode*firstchild,}CSNode,7带双亲的孩子链表9

parent

结点结点链

该结点的该结点的第一个孩子结点和右边下一个兄弟结点∧D∧DB∧E∧F∧E∧F∧ ∧

A∧C∧A∧C∧

6.6 ∧∧I树的孩子兄弟表示法图

将树转换为二叉 树转换为二叉树的方在所有兄弟结点

每棵树对应的二叉

将森林转换为二叉将森林中的每一树转换二叉将各二叉树的根结点

A

包含3

AE

KL森林对应的二叉森林对应的二叉 每棵树对应的每棵树对应的二 树或森林与二叉树之间有一个自然的一一对应的关系任何一个森林或树可以唯一地对应到一棵二叉任何一棵二叉树可以唯一地对应到一个森林或一棵

如果结点如果结点是其双亲的左孩子，则把去掉所有双亲到右 6.6

树中各个结点一次且仅进行一次。由于一个结点可以有两棵以上的，因此一般不讨论中序左右指的是在结构中自然形成的之间的次序），另树的按层次 6.6.3树的遍后后根顺序遍历T1后根顺序遍历T2…后根顺序遍历根结点 根结点 先根顺序遍历T1先根顺序遍历T2 …先根顺序遍历Tk

练 树的遍历先根遍

A E

D K

用二叉链表作树和森林 HuffmanA,B,E,H,I,J,C,D,C’,Huffman后根遍H,I,J,E,B,C,C’,K,G,D, 6.7树的应树树的有关概二叉二叉树的遍遍历的应线索二叉树和森树及其应

二叉排序树二叉排序树的定一种特殊的二叉树，又称二叉查找树。它的每结点数据中都有一个关键值，并有如下性质 如果其 非空，则 左

typedeftypedefstructnode{keytypekey;infotypestructnode*lch,*}BSTNode,*8 8—12—45—54—60—67— 二叉排序树的优点：用二叉排序树作为树，把一个记录的关键码和记录的地址作为二叉排序树的结点，按关键码值建成二叉排序树可以实现：8

bstnode*CreatBST(){bstnode*t,*s;keytypekey,while(key!=endflag){s-t=insertbts(t,s);

return}

例设查找的关键字序列90}

中序遍历二叉排序树可得到一个关键字有序的序列

在二叉排序树上一个记录或结点，不需要移动

其它记录或结点

在二叉排序树中进行查找，将要查找的值从树根若与根的关键值相等，则查找成功若比根值小，则到 找若比根值大，则到 找直到查找成功或查 为空（失败）

if((T==NULL)||(T->key==return(T);return(searchbst(key,T-}

二叉排序树 的递归算BSTNode*insertbts(BSTNode*p,BSTNode*root)

if(root==NULL)returnif(p->key<root-root->lch=insertbts(p,root-root->rch=insertbts(p,root->rch);return(root);} 首先查找到要删除的结点,删除结点后，仍保持二排序树的结构特点不变

二叉排序树的中序序列仍然是按关

(1)若*p结点是叶子，则直接删除。为空。（f->rch=NULL)

删除树叶结点说明：结点必作为树 说明：结点必作为树 (2)若*p为单分支结点，则只需用它唯一(2)若*p为单分支结点，则只需用它唯一的根去继承它的位置。(f->lch=p->rch) p

f ( 的最右结点）替换*p

删除单分支结点

删除两分支结点 recordsdeletemin(F){recordstmp;BSTp;if(F->lch==NULL)p=Ftmp=F->data;F=F->rch;deletep;returntmp;}return(deletemin(F->lch)

DeleteBST(BiTreeT,KeyTypekey){if(!T)returnFALSE;elseif(key==T->data.key)returnDelete(T);elseif(key<T->data.key)returnDeleteBST(T->lch,key);elsereturnDeleteBST(T->rch,key);returnTRUE;}}}

思考题思考题小元不可能有左孩子，对于最大元也是这个道理最大元和最小元不一定是叶子，它也可以是根结点(分支小元不可能有左孩子，对于最大元也是这个道理最大元和最小元不一定是叶子，它也可以是根结点(分支结点)等，这需根 结点时的次序而定 6.7

树的路径长度：树中所有叶子结点的路径长度之和；一般记为 8

Huffman

非完全二叉 完全二叉

路径长

增长

内结内结点路径长度I内结点路径长度I：外结点路径长度E：从根结点到每个外结点的路长的n，Sn

为什么Sn+1

结论：如内结点路径长度为I，则外结点路径长EI2×n，nI=结论：如内结点路径长度为I，则外结点路径长EI2×n，n 结点的权：根据应用的需要可以给树的结点赋权值，记为wi结点的带权路径长度：从根到该结点的路径长度Li与该结点

A7Bwi的乘树的带权路径长度：树中所有叶子结点的带权路径之和；记作WPL=w

2 4 C4 7 5

752 D树可以构造出多棵，其中必存在一WPL最小的二叉树，称该二叉树为最优二叉树树

例构造以W=（5，14，40，26，10）为权 树

步骤

树时,

根据给定的n个权值，构造n棵只有一个根结点的二叉树n个权值分别是这些二叉树根结点的设F是由这n棵二叉树构成的集合，在F中选取两棵根结点树值最小的树作为左、右，构造一颗新的二叉树，置新二叉树根的权值=左、右根结点权值之和；从F中删除这两颗树，并将新树加入重复2、3，直到F中只含一颗树为止；这棵树便是树 对5个权值{5,6,2,9,7}构造最优二叉树的过程如动画所示。

typedefstructfloatintlch,rch,hufmtreetree[m];CreatHuffmanTree(hufmtreetree[])inti,j,p1,floatsmall1,small2,Huffman树的构造Huffman树的构造

//初始化}}

voidInputWeight(hufmtreeT输入权floatw;inti;for(i=0;i<n;i++)}for(i=n;i<m;i++把合并后的结点放入向量p1=0; //两个根结点在向量tree//small1=maxval;

for(j=0;j<i-1;jif(tree[j].weight<small1){small2=small1;//改变最小权，次小权及其位置small1=tree[j].weight;//找出最小的权值}elseif(tree[j].weight<small2){small2=tree[j].weight;//改变次小权及位置}}// //新生成的结点放在向量tree[i+1].lch=p1;tree[i+1].rch=tree[i+1].weight=tree[p1].weight+tree[p1].

通常有两通常有两类二进制编码不等长编码（变长编码）：即各个字符的编码长度不}// 不等长不等长编码的好处：都不能是另一个字符的编码的前缀，这种编码称为前缀编码

例例要传输的原文为等长编码 发送方：ABACCDA转换成接收方：00010010101