数据结构-第四章树微软2010版2013ldy

第1页4.1树的基本概念4.2二叉树(BinaryTree)4.3线索二叉树(ThreadedBinaryTree)4.4树与森林(Tree&Forest)4.5压缩与哈夫曼树(HuffmanTree)4.6应用第四章树第2页在现实世界中，树（或曰树结构）大量存在，例如用树可形象地表示家谱、行政组织机构、著作目录等。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程。绪论第3页例1.大学层次结构吉林大学人文学部哲学社会学院文学院外国语学院艺术学院体育学院社会科学部文学院外国语学院艺术学院体育学院理学部数学学院物理学院化学学院生命科学学院第4页下图给出了Joe(乔)的后代的层次结构,其中Joe在顶层,Joe的孩子Ann(安),Mary(玛丽)和John(约翰)列在下一层,在父母和孩子间有一条边.在层次表示中,很容易找到Ann的兄弟姐妹,Joe的后代,Chris(克里斯)的祖先等.例2.Joe的后代JoeAnnMaryJohnMarkSueChris第5页总裁销售副总裁市场副总裁财务副总裁开发副总裁例3.

某公司组织管理机构某公司中地位最高的人为总裁，在最高处；副总裁的地位次之，位于总裁之下.副总裁为总裁的下属，总裁是其上级。每个副总裁都有自己的下属，而其下属又可能有自己的下属。图中,每个员工若有直接下属或直接上级，则两者间有一条边互连。第6页联邦政府国防部教育部税务部陆军海军空军海军陆战队下图是联邦政府层次结构图.顶层元素(亦称机构)是联邦政府，下一级是其主要的隶属单位，如不同的部.每个部可进一步划分，其分支在下一层示出.例如国防部包括陆军,海军,空军和海军陆战队.每个机构，若有分支机构，则两者间有一条边。下图展现了诸元素间的整体-部分关系.例4.政府机构第7页文字处理器文件字体导入光标OpenNewSavePrintQuit例5.某文字处理软件结构下图给出了某文字处理器的一种模块分解图.文字处理器是最顶层模块,在其下层被划分成4个模块.文件模块完成与文本文件有关的操作,如Open,New,Save,Print和Quit等.字体模块包括与字体处理有关的所有功能模块,且它们在字体模块的下一层.导入模块用于处理图形、表格及其他格式的文本文件.光标模块处理屏幕上光标的移动.在接口设计好之后,程序员可以相对独立的方式分析、设计和开发每个模块.

第8页软件的模块化技术.一方面，模块化的目标是将大而复杂的软件系统，分解成许多功能独立，较简单、较小的模块，使多人同时并行开发不同的模块，可大大缩短整个软件的开发时间.另一方面，分开测试一些小而独立的模块比测试一个大而复杂的模块要容易得多，有利于保障开发的正确性。第9页4.1树的基本概念4.2二叉树4.3线索二叉树4.4树和森林4.5压缩与哈夫曼树4.6

应用第10页树的递归定义定义4.1.1：一个树(或曰树形)就是一个有限非空的结点集合T，其中：有一个特别标出的被称为该树之根root(T)的结点；除根之外的其余结点被分成m0个不相交的集合T1,T2,…,Tm，且T1,T2,…,Tm又都是树.树T1,T2,…,Tm被称作root(T)的子树(或曰子树形).4.1.1

树的定义第11页定义4.1.2

树是包含n1个结点且满足如下条件的有限集合:存在唯一的结点v0,它无前驱结点,称为树的根(或曰根结点)；任何非根结点都有且仅有一个前驱结点，称为该结点的父结点；若某结点无后继结点,则称之为叶结点;任何非叶结点P都有1个后继结点,称其为P的子结点;任一非根结点vk都有且仅有一条从v0到vk的结点序列(或曰路径)v0

v1

…

vk,其中vi是vi1(1

i

k)

的子结点。树的非递归定义线性结构树结构首结点(无前驱)根结点(无前驱)最后1个元素(无后继)叶子结点可能多个(无后继)其它数据元素(一个前驱,一个后继)树中其它结点(一个前驱,多个后继)树与线性结构的比较第12页1、结点的度与树的度一个结点的子结点的数目,被称为该结点的度或曰次数.一棵树的度为maxi

1nD(i),其中n为树中结点总数,i指树中的第i个结点,D(i)表结点i的度.2、叶结点与分支结点度为零的结点被称为叶结点；度大于零的结点被称为分支结点.4.1.2树的相关术语第13页3．结点的层数树形T中结点的层数递归定义如下：⑴root(T)层数为零；⑵其余结点的层数为其前驱结点的层数加1.第14页在图4.1所示的树T中：B有一个子结点E，度为1；A有三个子结点B,C和D(换言之,A是B,C和D的父结点)度为3；因为在T中,结点A的子结点数最多,故这棵树的度为3.T

中F,G,H,I

为叶结点,其余结点为分支结点.T中,结点A

为树T

之根,其层数为零;结点F的层数为3.第15页图4.1树TACB层数0层数1DEGHIF层数2层数3T中,结点A的子结点数最多,故T的度为3第16页4．边，路径，路径长度树形中结点间的连线被称为边。若树T中存在结点序列vm

vm1…

vmk，1

k

T的最大层数，满足vi1是vi（m

i

mk1）的子结点，则称此结点序列为vm到vmk的路径，该路径所经历的边数k被称为路径长度.5.子孙结点、祖先结点一棵树中若存在结点vm到vn的路径，则称vn为vm的子孙结点，vm为vn的祖先结点.第17页一个结点到它的某个子孙结点有且仅有一条路径.树中结点间的父子关系具有如下特征：树中任一结点都可有零个或多个直接后继(即子结点),但至多只能有一个直接前驱(即父结点).树中只有根结点无前驱,它是始结点;叶结点无后继,它们是终结点.树中某些结点之间具有父子关系或者祖先、子孙关系，祖先、子孙关系是父子关系的扩展,一些结点间,如兄弟结点(同一父亲的诸子结点被称为兄弟结点)之间就没有这种关系。第18页6．树的高度树的高度为maxi

1nNL(i),其中n为树中结点总数,i指树中第i个结点,NL(i)之值为结点i的层数.换言之,树的高度指树中结点的最大层数.第19页A(B,C(D,E))3树的表示:

1.集合嵌套表示法2.凹入表示法3.广义表表示法4.树形表示法BDE1ACABDE2CABCDE4第20页树的基本操作1、判树空：TREEEMPTY(T)2、求根：ROOT(T)3、求树的深度：TREEDEPTH(T)4、求结点的brothers:同一双亲的孩子互称5、求结点的双亲：PARENT(T,e)6、求结点的孩子：CHILD(T,e,i)7、建树:CREATE_TREE(T,T1,T2,…,Tm)8、遍历树：TRAVERSAL(T)第21页4.2二叉树(BinaryTree)4.2.1二叉树的定义和主要性质定义4.2.1二叉树(形)是结点的有限集合，它或者是空集，或者由一个根及两个不相交的称为这个根的左、右子树形的二叉树组成。第22页二叉树的五种不同形态LRRL(a)(b)(c)(d)(e)第23页树与二叉树的主要区别：⑴二叉树每个结点最多有2个子结点，树则无此限制；⑵二叉树中结点的子树分成左子树和右子树，即使某结点只有一棵子树，也要指明该子树是左子树，还是右子树，就是说二叉树是有序的；⑶树决不能为空(即树不能为空集),它至少有一个结点,而一棵二叉树可以是空的(即可以为空集).第24页A(a)(b)(c)(d)(e)ACBACBCBACBACB图4.2.2含3个结点的所有二叉树第25页引理4.1二叉树中层数为

i的结点至多有

2i个,i0.证明：用数学归纳法。当i0时,至多有一个根结点,其层数为0,因此当

i0时引理成立.假定当ik(k0)时引理成立，即第k层上至多有2k

个结点。对二叉树的任意结点，其子结点个数最多为2,故第k1层上至多有22k2k+1

个结点，因此当ik1时，引理成立。证毕▐二叉树的性质第26页高度为k(k1)的二叉树中至少有k1个结点.有k1个结点的二叉树高度至多为k1.图4.2.3

是高度为3,结点最少(4个)的二叉树之一.ABCD图4.2.3有4个结点的二叉树高度为3第27页引理4.2

高度为k0的二叉树至多有2k+11个结点.根据引理4.2.1第0层上至多有20个结点，第1层上至多有21个结点,……,第k层上至多有2k个结点,因此，高度为k的二叉树中至多有20＋21＋……+2k

2k+1－1个结点。证毕▐第28页证明：设T中,度为1的结点为n1个,总边数为e,则nn0+n1+n2

⑴非根结点有1条边与父结点相连,有en–1⑵显然又有，e2n2+n1⑶由上诸式有2n2+n1=n0+n1+n21

n2=n01n0=n2+1证毕▐引理4.3任一有n个结点的二叉树,其中叶结点数为n0,度为2的结点数为n2,则有n0n21第29页满二叉树定义4.4一棵非空高为k（k

0）,具有2k+11个结点的二叉树，被称为满二叉树。第30页712345689101112131415非空高为k二叉树至多有2k+11个结点.满二叉树的特点是：叶结点都在第k层上；每个分支结点都有两个子结点；叶结点的个数等于非叶结点个数加1(对满二叉树而言，除叶结点外，其它结点的度均为2.见引理4.3).第31页层次顺序:按从上至下,即从第0至第k层，每层由左到右的次序.定义4.5

一棵有n个结点、高为k的二叉树T,一棵高为k的满二叉树T*,用正整数按层次顺序分别编号T和T*的所有结点,如果T之所有结点恰好对应于T*的前n个结点，则称T为完全二叉树.完全二叉树显然,满二叉树一定是完全二叉树.第32页第33页71234568910111213141512345678910完全二叉树满二叉树包含n个结点、高为k的完全二叉树的特点：树中只有最下面两层结点的度可小于2；树中最下面一层的结点都集中在该层最左边

的若干位置上；树中叶结点只能出现在层数最大、次大的两层上，即存在一个整数m0使得树中每个叶结点在第m或第m1层上；对树中所有结点,按层次顺序,用正整数从1开始编号,仅仅编号最大的非叶结点可无右孩子,其余非叶结点都有两个孩子结点；在层次顺序意义下,树中所有结点对应于高为k的满二叉树中编号由1至n的那些结点。第34页引理4.4将一棵有n

个结点的完全二叉树,按层次顺序用自然数从1开始编号，则有：若1i

n,则编号为i之结点的父结点编号

为

i/

2

.若2i

n,且编号为i

的结点有左孩子,则其

左孩子的编号为2i．若2i1

n,且编号为

i

的结点有右孩子,则其右孩子的编号为2i+1．仅编号最大的非叶结点可无右孩子,但必须有

左孩子,其余非叶结点都有两个孩子结点.第35页用归纳法证明引理4.4:若i

1，n2，则其左孩子的编号显然为2.假定对所有

j(1

ji,2i

n),其左孩子编号为2j.如果

2(i1)n

,那么对结点

ji1,往证其左孩子的编号为2(i1).由层次顺序知,i1的左孩子之前的两个结点就是i的左孩子和右孩子,由归纳假设知i

的左孩子编号为2i,故i

的右孩子编号为2i1,从而i1的左孩子编号为2i22(i1).其它条款可仿证.证毕▐第36页引理4.5具有n

个结点的完全二叉树的高度是log2n.证明：设二叉树高度为k

,

由定义4.5知,

完全二叉树的结点个数介于高度为k1和k

的满二叉树的结点数之间，即有：

2k

1

n

2k+1

1从而有2k

n

2k+1，即k

log2n

k+1，因为

k

为整数，故有k

log2n

.证毕▐第37页二叉树的存储结构要存储一棵二叉树，需存储其所有结点的数据信息，以及其左、右孩子的地址。通常有两种存储方式：顺序存储链接存储第38页4.2.2二叉树的顺序存储二叉树的顺序存储(或曰顺序存储方式，顺序存储方法)：

系指将二叉树的所有结点按层次顺序存放在一块地址连续的存储空间中，同时要反映出二叉树中结点间的逻辑关系。第39页对于任一完全二叉树T,结点的层次顺序反映了

其结构,可按层次顺序给出其结点编号:这就是

T的顺序存储方式,结点编号恰好反映了

T

结

点间的逻辑关系。若对完全二叉树T之结点按层次顺序编号,则

可用一维数组A对其进行存储,A[i]存储T中

编号为i的结点，其中A[1]存储T的根结点；

若结点A[i]有左孩子，则其存放在A[2i]处；若结点A[i]有右孩子,则其存放在A[2i1]处.第40页图4.2.5完全二叉树的顺序存储结构(b)图(a)的顺序存储结构顺序存储结构ABECDA[1]A[2]A[3]A[4]A[5]1(a)5个结点的完全二叉树EBACD2345第41页结点值3123126694175706249结点编号12345678910106649311294175706212345672389哪个是编号最大的非叶结点？第42页若将上述方法用于非完全二叉树,却有很多缺点.如果采用上述顺序存储方式，按层次顺序，对非完全二叉树之结点进行编号，则编号不能表达结点间的逻辑关系.为此先通过添加虚结点将其转换成一棵“完全二叉树”,然后再对原来的结点和虚结点统一编号,最后完成顺序存储。但这无疑增加了用于存储虚结点的空间。第43页(a)

非完全二叉树ABCDA[1]A[3]A[7]A[15](c)非完全二叉树的顺序存储结构转换(b)完全二叉树ABCDABCD第44页二叉树链接存储系指二叉树的诸结点被随机存放在内存空间中,用指针指明结点间的逻辑关系.二叉树的结点结构

在二叉树的链接存储中，结点包含三个域，数据域data、左指针域left和右指针域right，其中左、右指针分别指向该结点的左、右子树的根结点；结点结构图示如下：4.2.3二叉树链接存储第45页leftdataright常用data字段值表示结点的名字.如在右图第2层最左边的结点C中,left域中的表示C的左子树为空,right域的表示C的右子树为空.ABCDEFG第46页CABDEFG二叉树链接存储结构Leftdataparentright另一种结点结构：结点包括三个指针域,parent域中指针指向其父结点第47页算法Father(t,p.q)/*指针t指向二叉树T之根;Father使用递归在T

中搜索给定结点p之父结点;q指向p之父结点*/Father1.[t

?]IF

t

THEN(

q

.RETURN.

).Father2.[t为所求?]IF

Left

(t)p

OR

Right(t)p

THEN

(q

t.

RETURN.).Father3.[递归]Father(Left

(

t

)

,p

.qL).IFqL

THEN(q

qL

.RETURN.).Father(Right

(

t

),p

.qR).q

qR

.▐①在二叉树中搜索给定结点的父结点第48页问题：为什么需要浅绿色语句?②搜索二叉树中符合数据域条件的结点算法Find(t,item

.q

)/*指针t指向二叉树T之根,Find在T中搜索Data

域之值为item的结点,指针q指向该结点*/Find1.[t

?]IFt

THEN(q

.RETURN.

).IFData(

t

)

itemTHEN(q

t

.RETURN.

).Find2.[递归]Find

(

Left(t),item

.p

).IFp

THEN

(q

p

.RETURN.

).Find

(Right(t),item

.q

).▐第49页③从二叉树中删除给定结点及其左右子树算法DST(t)/*root指向二叉树T之根，DST从T中

删除给定结点t及其左右子树*/DST1.[t

?]IFt

THENRETURN.DST2.[t

root?]IFt

rootTHEN(Del(t).root

.RETURN.)DST3.[找t的父亲q]p

t.Father(root,p.q).DST4.[修改q的指针域]IFLeft(q)

pTHENLeft(q)

.IFRight(q)

pTHENRight(q)

.DST5.[删除p及其子树]Del(p).▐第50页算法Del(p)//删除结点p及其左右子树Del1.[p

?]IFp

THENRETURN.Del2.[递归删除]Del(Left(p)).Del(Right(p)).AVAIL

p.▐假定，当前p指向结点C第51页AGBCDEF二叉树的遍历：按照一定次序访问树中所有结点，且使每个结点恰好被访问一次。以先根(中根、后根)次序遍历二叉树T,得到T之

结点的一个序列,称为T的先根(中根、后根)序列.遍历方式先根遍历：

DLR中根遍历：

LDR后根遍历：

LRD4.2.4二叉树的遍历D二叉树RL第52页当二叉树为空则什么都不做,否则遍历分三步进行：二叉树之先根,中根和后根遍历定义先根序中根序后根序步骤一访问根以中根序遍历左子树以后根序遍历左子树步骤二以先根序遍历左子树访问根以后根序遍历右子树步骤三以先根遍历右子树以中根序遍历右子树访问根第53页+ABEFDC图4.11

表达式(A+B)((CD)E+F)对应的二叉树第54页例：先根序遍历得到的结点序列：ABCDEF中根序遍历得到的结点序列：A+BCDE+F后根序遍历得到的结点序列：AB+CDEF+中根遍历二叉树算法框架:若二叉树为空,则空操作;否则：中根遍历左子树;访问根结点;中根遍历右子树.表达式语法树的中根遍历

结果：abcde/f中根遍历(InorderTraversal,中序遍历)表达式语法树afbcde第55页二叉树结点在水平线上的投影即中序遍历结果GKHAFEDCBCBDFE

AH

G

K第56页这三种结点序列都非常重要，它们分别与表达式的前缀、中缀和后缀表示相对应(其中,中缀表示还需要括号和优先级,稍有差别).

第57页二叉树递归的中根遍历算法算法Inorder（t）/*;步骤中简记Inorder为INO

*/INO1.[递归出口]

//若二叉树为空,则终止算法IFtNULLTHENRETURN.INO2.[递归遍历]Inorder(left(t)).PRINT(data(t)).Inorder(right(t)).▐第58页二叉树递归的先根遍历算法算法Preorder（t）/*;步骤中简记Preorder

为PRO*/PRO1.[递归出口]//若二叉树为空,终止算法IFtNULLTHENRETURN.PRO2.[递归遍历]PRINT(data(t)).Preorder(left(t)).Preorder(right(t)).)▐

第59页二叉树递归的后根遍历算法算法Postorder（t）/*;步骤中简记Postorder

为POO*/POO1.[树为空?]IFtNULLTHENRETURN.POO2.[后根遍历子树]Postorder(left(t)). Postorder(right(t)).POO4.[访问根]PRINT(data(t)).▐

第60页算法NIO(t)/*设t是指向一棵链接表示的二叉树T

之根的指针,NIO利用一个辅助堆栈S以中根序访问

T

的所有结点*/NIO1.[初始化]CREATE

(

S

).p

t

.

//创建空栈S

NIO2.[入栈]

WHILE

p

DO(S

p.p

Left(p).

)//*一直往左下方NIO3.[栈为空?]

IF

S为空THEN

RETURN

ELSE

p

S.NIO4.

[访问p,更新p]PRINT(Data(

p

)).p

Right(

p

).NIO5.[返回]GOTONIO2.▐非递归中根遍历算法第61页图4.12非递归中根遍历二叉树(b)中根遍历(a)中二叉树,堆栈内容变化过程图(b)中略去了进栈过程的描述NIO2.[入栈]WHILEp

DO

(S

p.p

Left

(p).)NIO3.[栈为空?]若S为空,则RETURN.否则

p

S.NIO4.[访问,更新p]打印

Data(p).

pRight(p).

返回NIO2.第62页

(a)二叉树ABCEFD

AB

A

AD

C

CE

A

F访问D访问A访问C访问F

A

ABA进栈B进栈访问B

ADD进栈

CC进栈E进栈

CE访问EF进栈

F

定理4.1设算法NIO从步骤NIO2开始，p指向一棵有n个结点之二叉树T*的根，此时栈S中有S[1],S[2],┅,S[m],m0.则步骤NIO2至NIO5将以中根序遍历T*，并最后达到步骤NIO3，同时栈S也恢复到原来值S[1],S[2],┅,S[m].算法NIO正确性证明作业：读书上之证明第63页②非递归后根遍历算法非递归后根遍历算法需要一个辅助堆栈来记忆访问路径，算法中栈元素结构如下：树中任一结点p都要进栈三次，出栈三次.

第一次出栈是为遍历p的左子树；第二次出栈是为遍历p的右子树；第三次出栈是为访问p.其中i在集合{0,1,2}中取值,用来标识p

的

出栈次数.具体说明如下：

结点

退栈次数

i第64页初始化时,将(根结点,0)进栈.

出栈,判断出栈元素(p,i)中的标号i：若i0,则(p,1)

进栈;若p的左指针非空,则

(Left(p),

0)

进栈,准备遍历

p

的左子树./*

若p有左子树,则其左子树所有结点的二元组皆在p的二元组之上

*/

若i1,则(p,2)进栈;若

p

的右指针非空,则(Right(p),0)

进栈,准备遍历

p

的右子树./*

此时

p

的左子树已被遍历;若p有右子树,则其右子树所有结点的二元组皆在p的二元组之上*/

若i

2,访问结点p.

//此时p

的左、右子树都已被遍历,自然应访问根结点第65页算法NPO(t)/*设二叉树T以链接方式存储,指针t

指向T之根,算法NOP利用堆栈S以后根序遍历T*/NPO1.[初始化]IFt

THENRETURN.CREATS(S).S

(t,0).NPO2.[后根遍历]WHILE栈S非空DO((p,i)S.IFi0THEN(

S

(p

,

1).若left(p)则

S(left(p),0).).IFi1THEN//此时p

的左子树已被遍历(

S

(

p

,

2).若

right(

p)

则

S

(

right(

p),

0).).IFi2THEN//此时p

的右子树已被遍历PRINT(data(p)).).▐WHILE的每次迭代中3个IF语句仅执行一个第66页

C,1A,2E,1

C,1A,2E,2访E访F访C访A

C,1A,2

C,2A,2F,0

C,2A,2F,1

C,2A,2F,2

C,2A,2

A,2

对左图之二叉树进行后序遍历,栈S之变化

A,0

B,0A,1

B,1A,1

B,2A,1D,0

B,2A,1D,1

B,2A,1D,2

B,2A,1

A,1

C,0A,2

C,1A,2E,0访D访BWHILE栈S非空DO//分别简记left、right为Lt和Rt(

(p,i)S.IFi0THEN

[S(p,1).

若

Lt

(p),则

S

(Lt(p),0).].IFi1THEN

[S(p,2).

若

Rt

(p),则

S

(Rt(p),0).].IFi2THEN

PRINT(data(p)).)▐ABCDEF第67页先根序列和中根序列可唯一确定一棵二叉树ABDCEFKH[例]上图二叉树T的先序、中序遍历结果:①先根序列A00BALCBRKCLDAREDLHELFDR②中根序列BALKCLCBRA00HELEDLDARFDR由①、②两个序列可确定二叉树的结构。

由①知T之根为A,由②知A之左子树包括B,K,C三个结点

其右子树包含H,E,D,F四个结点,再由①知A之左子树的根为B，知A之右子树的根为D，照此可确定出整个T之结构.譬如，FDR系指F是D的右孩子。A00系指T之根。第68页后根序列和中根序列可唯一确定一棵二叉树[例]

后根序列CEFDBHGA

中根序列CBEDFAGH第69页后根序列CBLEDLFDRDBRBALHGRGARA00

中根序列CBLBALEDLDBRFDR

A00GARHGRAC

B

E

DFGHDEFABCGHABCGDEHF第70页第71页练习：已知某二叉树的先序遍历序列是ABDGCEFH，中序遍历序列是DGBAECHF，它的后序遍历序列是什么？给定一棵二叉树T的先根序列和后根序列，那么能否由此确定出T之结构？第72页层次遍历:按层数由小到大,即从第0层开始逐层向下,同层中由左到右的次序访问二叉树的所有结点.遍历结果:

ABECFDABECFD第73页在第

i

层上若结点x

在结点y

的左边，则x

一定在y

之前被访问.同理,在第i1层上，x的孩子结点一定在y

的孩子结点之前被访问.若访问i

层上的所有结点，必须知道i

层上所有结点的地址，地址保存在其父结点的left或right指针中。由①，算法可用先进先出的队列来实现；由②，除待遍历二叉树T的根结点之外，其余结点的地址均是其父结点的left或right.层次遍历问题的分析第74页使用一个先进先出结构的队列Q，具体如下：将根结点插入Q.重复执行本步骤直至Q为空:若Q非空,取Q的头结点n

并访问;若n的左指针不空,将其左孩子插入Q;若n的右指针不空,将其右孩子插入Q.二叉树层次遍历算法的主要思想第75页/*

算法LevelOrder按层次顺序对链接存储的二叉树T进行遍历，t

指向T

之根，Q

为队列

*/LO1.[建空队]CREATE(Q).LO2.[入队]p

t.IF

p

THEN

Q

p.//T

之根入队LO3.[层次遍历]

WHILE

Q

非空DO(p

Q.PRINT(Data(p)).//取对头并访问

IF

Left(p)

THEN

Q

Left(p).

IF

Right(p)

THEN

Q

Right(p).)▐算法LevelOrder(t)第76页由二叉树的遍历算法，很容易想到用遍历方法去创建二叉树。如，从先根遍历思想出发构造二叉树。但先根序列不能唯一确定二叉树的结构，两棵不同的二叉树却可能有相同的先根序列。

原因是：二叉树中，可能有其左指针和/或右指针为空的结点，先根序列不包含这方面的信息。

由此：需在先根序列中加入特殊符号以示空指针位置，这里不妨用“#”号表示空指针位置。4.2.5创建二叉树第77页递归算法CreateBinTree（简记为CBT）以根指针t为输入参数，以包含空指针信息的先根序列为输入序列.当读入"#"字符时，将其初始化为一个空指针；否则生成一个新结点并初始化其父结点之左、右指针.由于序列中用"#"表示空指针，故在算法中设置tostop"#"，以便判断序列中的"#"号.当输入序列为ABD#E###C##时,可创建下页所示的二叉树.第78页算法CBT(tostop.t)//构造以结点t为根的二叉树；tostop

‘#’CBT1.[读数据]READ(ch).//顺序读入序列中的一个符号CBT2.[ch

tostop?]IFch

tostopTHEN(t

.RETURN.)ELSE(t

AVAIL.Data(t)

ch.)CBT3.[构造左子树]CBT(tostop.Left(t)).CBT4.[构造右子树]CBT(tostop.Right(t)).▐

ABD#E###C##CBT(.t)

Data(t)A

CBT(.L(t))

Data(L(t))B

CBT(.L(L(t)))

Data(L(L(t)))D

CBT(.L(L(L(t)))).L(L(L(t))).

CBT(.R(L(L(t))))

Data(R(L(L(t))))E

CBT(L(R(L(L(t))))).L(R(L(L(t)))).

CBT(R(R(L(L(t))))).R(R(L(L(t)))).

CBT(.R(L(t))).

R(L(t)).

CBT(.R(t))

Data(R(t))C

CBT(.L(R(t))).

L(R(t)).

CBT(.R(R(t))).R(R(t)).▐第79页DBE####CA##ABD#E###C##简记Left,Right为L和R;省略参数tostop,以及t

AVAIL等操作t第80页设指针t指向一棵链接表示的二叉树T，欲得到T的一个“备份”，则容易想到用先根、中根或后根遍历二叉树的解决方案。考虑到在创建二叉树的算法中使用了先根遍历的思想，这里最好尝试其它遍历方式，譬如说“后根遍历”。若采用后根遍历方式，则复制过程如下：

①复制左子树；

②复制右子树；

③生成父结点，连接父结点和左右子树之根结点.4.2.6二叉树遍历的应用：复制二叉树第81页

算法

CT(t.p)

/*t指向链接表示的二叉树T之根，二叉树T为T的复制品，

p指向T之根;在CT中，复制采用后根遍历方式*/

CT1.[递归出口]IFt

THENRETURN.CT2.[复制左子树]IFLeft(t)

THENCT(Left(t).lptr)ELSElptr

.CT3.[复制右子树]IFRight(t)

THENCT(Right(t).rptr)ELSErptr

.CT4.[生成根结点]p

AVAIL.Data(p)

Data(t).Left(p)lptr.Right(p)rptr.RETURNp.▐CT(t.p)//t

指向结点A

CT(L(t).lptr)

//步CTP2.L(t)B

具体见85页

CT(R(t).rptr)

//步CTP3.R(t)D具体见86页

pAVAIL.Data(p)

Data(t).

L(p)lptr.//此时L(p)指向结点B，见85页R(p)rptr.

//此时R(p)指向结点D，见86页

RETURNp.▐//此时p指向结点ABACDE简记Left、Right为:L(t)和R(t)第82页CT(L(t).lptr)

//L(t)B

lptr

//步CT2，L(L(t))

CT(R(L(t)).rptr)

lptr

//L(R(L(t)))

rptr

//R(R(L(t)))

pAVAIL.Data(p)Data(R(L(t))).//Data(p)C

L(p)lptr.R(p)rptr.

RETURNp.

//rptr

p

pAVAIL.Data(p)

Data(L(t)).//Data(p)B

L(L(t))

lptr.//L(L(t))

R(L(t))

rptr.

//R(L(t))指向结点C

RETURNp.//lptr

p，即

lptr

指向结点B第83页简记Left、Right为:L(t)和R(t)BADECCT(R(t).rptr)

CT(L(R(t)).lptr)//L(R(t))E

lptr

.

//CT2.L(L(R(t))))

rptr

.

//CT3.R(L(R(t))))

pAVAIL.Data(p)Data(L(R(t))).//Data(p)E

L(p)

lptr.//lptr

R(p)

rptr.//rptr

RETURNp.

//lptrp，此时lptr指向结点ECT(R(R(t)).rptr)RETURN.//rptr

pAVAIL.Data(p)

Data(R(t)).//Data(p)D

L(p)

lptr.//此时L(p)

指向结点E

R(p)

rptr.

//R(p)RETURNp.//rptr

p，此时rptr指向结点D

BADCE第84页第85页用后序遍历计算二叉树结点个数算法Count(t.n)/**/IFtNULLTHEN(n0.RETURN.)Count(left(t).nl).Count(right(t).nr).n

nlnr1.▌编写计算二叉树高度的算法[解题思路]二叉树之深度可由如下公式求得：由此可见，该题可用递归算法求解。第86页算法depth(t.d)/**/IFtTHEN(d1.RETURN.)ELSE(depth(left(t).d1).depth(right(t).d2).IF(d1>d2)THEN(dd11.RETURN.) ELSE(dd2+1.RETURN.)

)▐

第87页以Left/Right链接表示的二叉树结构，可看作是由许多从根结点到叶结点的单链表组成的，一个结点的前驱结点是它的父结点，一个结点的后继结点是它的孩子结点。这种结构的不足有二：

其一是，从一个结点出发只能访问它的孩子结点，而不能访问它的父结点；

其二是，这种结构通常包含很多未被有效利用的指针字段，譬如包含i个结点的二叉树，在其2i个指针字段中仅有i1个被使用.4.3线索二叉树第88页为使二叉树之访问更方便,其空间利用率更高.1960年,珀利斯(A.J.Perlis)和桑顿(C.Thornton)提出了巧妙的线索二叉树表示，并给出了以各种顺序遍历线索二叉树的重要思想.但是珀利斯和桑顿提出的只是单向的线索二叉树.1963年，霍特(A.W.Holt)又提出了双向线索二叉树。第89页第90页象双向链表一样,二叉树也可采用双向链接.如下图所示,针对某种遍历顺序,可为二叉树的每个结点增加两个指针域，分别存放指向其前驱和后继结点的指针Pred和Succ，并称Pred和Succ为"线索".在这样的二叉树中,搜索一结点在某遍历顺序下的前驱或后继将变得更加容易，但将增加一些存储空间的开销.LeftRight

DataPredSucc线索二叉树定义4.6设T*是一棵二叉树，其结点增加了针对某种遍历顺序的线索域，在T*中可直接查找任一结点在该遍历顺序下的前驱和后继结点，称T*为线索二叉树

(Threaded

BinaryTree).第91页在一棵线索二叉树中，若指针Pred和Succ分别指向结点的先根（中根、后根）前驱和先根（中根、后根）后继，则称其为先序（中序、后序）线索二叉树.书上：图4.21(a)所示二叉树T之中根遍历序列为BCAED，它的中序线索二叉树的链接表示如图4.21(b)所示；T的后根序列为CBEDA，它的后序线索二叉树的链接表示如图4.21(c)所示.

第92页(a)

二叉树ABDCEPredSuccPredrootSuccPred(b)中序线索二叉树的链接表示中序序列：BCAEDDEACBSuccPredSucc图4.21线索二叉树的链接表示图中虚线箭头表示线索第93页后序线索二叉树的链接表示后序序列：

CBEDASuccPredSuccSuccPredSuccrootADBCEPredPred第94页线索二叉树的问题与分析问题：由图4.21可见，线索二叉树的结点中仍有很多空指针，就是说存储空间的浪费问题还未得到有效解决。分析：指针域需占用较多的存储空间，如一个空间容量为4GB的内存储器需要32个二进制位来表示地址，若将指针域中的Pred和Succ换成1个二进制位则会节省许多空间。

第95页10月22日讲到这里线索二叉树的改进方案：将原指针域Pred和Succ分别改成存储一个二进制位的域LThread和RThread.若结点t有左孩子，则Left指向t的左孩子，且LThread值为0;若t没有左孩子,

则Left指向t的前驱结点,且LThread值为1，此时称Left为线索.若结点t有右孩子，则Right指向t的右孩子，且RThread值为0；若t没有右孩子，则Right指向t的后继结点，且RThread值为1，此时称Right为线索.第96页图4.22改进后的线索二叉树(b)改进的中序线索二叉树A00B10C11D01E11ABDCE(a)

二叉树结点中为何出现?SuccPredPredSucc第97页PredSuccroot

(c)改进后的后序线索二叉树0A0D10B10E11C11SuccSuccPredABDCE(a)二叉树为何Left域中放?第98页在中序线索二叉树中,不需要对二叉树进行遍历就可方便地找到给定结点的中序前趋和中序后继结点，且不需要太多的额外空间。在改进的线索二叉树中，一个结点是叶结点的充要条件是，其左、右标志（LThread、RThread）均为1.第99页[1]-1在以t

为根的中序线索二叉树中，搜索中根顺序的第一个结点算法思想：若t

有左子树，则中根遍历顺序的第一个结点就是左子树中最左边的结点；若t

无左子树，中根遍历顺序的第一个结点就是t.

4.3.3线索二叉树基本算法第100页算法FIO(t.q)/*t指向改进的中序线索二叉树T*之根，本算法返回T*的中根序列的首结点，并用q指向它*/FIO1.[初始化]q

t.FIO2.

[找中根序首结点]WHILELThread(q)0DOq

Left(q).RETURNq.▐

第101页WhileLThread(q)=0DOq

Left(q);A00B10C11D01E11t第102页[1]-2搜索线索二叉树T*之中根顺序的最后一个结点,设t

指向T*之根.算法思想：若t

有右子树，则中根序末结点就是右子树中最右边的结点；若t无右子树，中根序的末结点就是t.

第103页算法LIO(t.q)/*给定改进的中序线索二叉树T*，t指向T*之根，LIO返回T*之中根序之末结点，并用q指向它*/LIO1.[初始化]q

t.LIO2.[找中根序末结点]WHILERThread(q)0DOq

Right(q).RETURNq.▐第104页解决该问题的主要思路：若p是中根序首结点，则p无中序前驱结点；

//情况1若p非中根序首结点：若LThread(p)1，则Left(p)为左线索，直接指向p的中序前驱结点；//情况2若LThread(p)0，p的中序前驱结点是p之左子树的中根序末结点.//情况3[2]-1T是一棵改进的中序线索二叉树，如何找出

T中结点p的中序前驱结点？第105页算法PIO(t,p.q)/*给定改进的中序线索二叉树（这里亦简称二叉树）T*，t指向T*之根，算法PIO搜索T*中结点p的中序前驱结点，PIO运行结束时q指向它*/PIO1.[求中序首结点]FIO(t.first).IFp

firstTHEN(q

.RETURNq.)//p无前驱PIO2.[取p之左指针]lp

Left(p).IFLThread(p)1THEN(qlp.RETURNq.)

//情况2，lp指向p的中序前驱结点PIO3.[求中序末结点]LIO(lp.q).//求以lp

为根之二叉树的中序末结点RETURNq.▐第106页主要思想：若p是中序末结点，则其无后继结点；

//情况1若p非中序末结点：

//由中序定义知：p之后继在p

的右子树中若RThread(p)1，则Right(p)指向p之中序后继//情况2，Right(p)为右线索若RThread(p)0，则p的中序后继为p之右子树的中序首结点。//情况3[2]-2T是一棵改进的中序线索二叉树，如何找出T中

结点p之中序后继结点？第107页算法NIO*(t,p.q)/*给定改进的中序线索二叉树（这里亦简称二叉树）T*，t指向T*之根，NIO*搜索T*中结点p的中序后继，当NIO*运行结束q指向它*/NIO*1.[求中序末结点]

LIO(t.last).IFp

lastTHEN(q

.RETURNq.)//情况1NIO*2.[取p之右指针]rp

Right(p).IFRThread(p)1THEN(qrp.RETURNq.)

//情况2，Right(p)为指向p之中序后继的右线索NIO*3.[RThread(p)0]

FIO(rp.q).RETURNq.▐

/*情况3，

rp为p之右子树的根，q指向以rp为根之

二叉树的中序首结点*/第108页主要思想：若结点p是改进的后序线索二叉树T*之后序首结点，则p无后序前驱；//情况1若结点p非T*之后序首结点：若LThread(p)1，则Left(p)指向p的后序前驱；

//情况2，Left(p)为左线索若LThread(p)0，则：

//情况3，此时p有左子树若p无右子树，则p之左孩子是其后序前驱；若p有右子树，则p之右孩子是其后序前驱.[3]-1改进的后序线索二叉树中结点p之后序前驱第109页算法PPO(t,p.q)/*给定后序线索二叉树T*，t指向T*之根，PPO搜索T*之结点p的后序前驱，并令q指向它*/PPO1.[求T*之后序首结点]FPO(t.first).//FPO求T*之后序首结点IFpfirst