第七章树与二叉树

第七章树与二叉树第1页，课件共155页，创作于2023年2月全校学生档案管理的组织方式一．树的应用7.1

树的有关概念．第2页，课件共155页，创作于2023年2月文件夹1文件夹n文件1文件2文件夹11文件夹12文件11文件12C不论是DOS文件系统还是window文件系统，所有的文件是用树的形式来组织的。计算机的文件系统现实世界中，能用树的结构表示的例子：学校的行政关系、书的层次结构、人类的家族血缘关系等。第3页，课件共155页，创作于2023年2月二．树的概念

树是n个结点的有限集合，在任一棵非空树中：

（1）有且仅有一个称为根的结点。

（2）其余结点可分为个互不相交的集合，而且这些集合中的每一集合都本身又是一棵树，称为根的子树。树是递归结构，在树的定义中又用到了树的概念JIACBDHGFEKLM第4页，课件共155页，创作于2023年2月例：下面的图是一棵树T={A,B,C,D,E,F,G,H,I,J，K，L，M}A是根，其余结点可以划分为3个互不相交的集合：

T1={B,E,F，K，L},T2={C,G},T3={D,H,I,J，M}这些集合中的每一集合都本身又是一棵树，它们是A的子树。例如：对于T1，B是根，其余结点可以划分为2个互不相交的集合

T11={E，K，L}，T12={F}，T11,T12

是B的子树。JIACBDHGFEKLM第5页，课件共155页，创作于2023年2月从逻辑结构看：

1）树中只有根结点没有前趋；

2）除根外，其余结点都有且仅一个前趋；3）树的结点，可以有零个或多个后继；

4）除根外的其他结点，都存在唯一条从根到该结点的路径；5）树是一种分枝结构（除了一个称为根的结点外）每个元素都有且仅有一个直接前趋，有且仅有零个或多个直接后继。JIACBDHGFEKLM第6页，课件共155页，创作于2023年2月三．树的表示

1、图示表示

2、二元组表示

3、嵌套集合表示

4、凹入表示法（类似书的目录）

AEDHJIKLMDGCABEKLFCGDHMJI5、广义表表示（A（B（E（K,L）,F））,C（G）,D（H（M）,I,J））第7页，课件共155页，创作于2023年2月树的结点：包含一个数据元素及若干指向子树的分支；孩子结点：结点的子树的根称为该结点的孩子；双亲结点：B结点是A结点的孩子，则A结点是B结点的双亲；兄弟结点：同一双亲的孩子结点；堂兄结点：同一层上结点；祖先结点:从根到该结点的所经分支上的所有结点;子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙;结点层：根结点的层定义为1；根的孩子为第二层结点，依此类推。JIACBDHGFEKLM四．树的基本术语第8页，课件共155页，创作于2023年2月树的深度：树中最大的结点层数；结点的度：结点子树的个数；树的度：树中最大的结点度。叶子结点：也叫终端结点，是度为0的结点；分枝结点：度不为0的结点；有序树：子树有序的树，如：家族树；无序树：不考虑子树的顺序；森林：互不相交的树集合；森林和树之间的联系是：一棵树去掉根，其子树构成一个森林；一个森林增加一个根结点成为树。

JIACBDHGFEKLM第9页，课件共155页，创作于2023年2月树的应用很广，应用不同基本操作也不同。下面列举了树的一些基本操作：

1、initiate(T);T树的初始化，包括建树。

2、root(T);求T树的根。 3、parent(T,x):求T树中x结点的双亲结点。 4、Child(T,x,i)：求T树中x结点的第i个孩子结点。

5、right_sibling(T,x):求T树中x结点的右兄弟

6、insert_Child(y,i,x):将根为x的子树置为y结点的第i个孩子

7、del_child(x,i);删除x结点的第i个孩子

8、traverse(T);遍历T树。按某个次序依次访问树中每一个结点，并使每个结点都被访问且只被访问一次。

9、clear(T);置空T树

五.树的基本操作第10页，课件共155页，创作于2023年2月

树是一种分枝结构，在树的概念中，对每一个结点孩子的个数没有限制，因此树的形态多种多样，本章我们主要讨论一种最简单的树——二叉树。因为树的每个结点的度不同，存储困难，使对树的处理算法很复杂。所以引出二叉树的讨论。第11页，课件共155页，创作于2023年2月二叉树7.2二叉树1.二叉树的概念2.二叉树的性质3.二叉树的存储结构第12页，课件共155页，创作于2023年2月一.二叉树的概念1、二叉树的定义说明1）二叉树中每个结点最多有两颗子树；二叉树每个结点度小于等于2;2）左、右子树不能颠倒——有序树;3）二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念;

A

F

G

E

D

C

B6.2二叉树（BinaryTree）二叉树是一种特殊的树型结构，特点是树中每个结点只有两棵子树，且子树有左右之分，次序不能颠倒。第13页，课件共155页，创作于2023年2月

A

F

G

E

D

C

B

(a)、(b)是不同的二叉树，(a)的左子树有四个结点，(b)的左子树有两个结点，(a)

A

G

E

D

B

C

F(b)第14页，课件共155页，创作于2023年2月二叉树的五种基本形态空二叉树仅有根结点右子树为空左子树为空左右子树均非空

2、二叉树的基本形态

第15页，课件共155页，创作于2023年2月3、应用举例例1可以用二叉树表示表达式

a+b*(c-d)-e/f

e

d

c

b

f

a

+

*

/

-

-第16页，课件共155页，创作于2023年2月例2双人比赛的所有可能的结局

甲乙甲乙甲乙甲乙甲乙甲乙甲乙甲乙甲乙甲乙甲乙甲乙甲乙开始开局连赢两局或五局三胜第17页，课件共155页，创作于2023年2月性质1在二叉树的第i层上最多有2i-1个结点（用归纳法可证明）性质2深度为k的二叉树最多有2k-1个结点性质3设二叉树叶子结点数为n0，度为2的结点n2，则n0=

n2+1二、二叉树性质

A

F

G

E

D

C

B第18页，课件共155页，创作于2023年2月两种特殊的二叉树满二叉树：如果深度为k的二叉树，有2k-1个结点则称为满二叉树；

A

G

F

E

D

C

B

B

A

CK=3的满二叉树K=2的满二叉树第19页，课件共155页，创作于2023年2月完全二叉树：如果一颗二叉树只有最下一层结点数可能未达到最大，并且最下层结点都集中在该层的最左端，则称为完全二叉树；

A

E

D

C

B

G

A

E

D

C

B(a)(c)(b)、(b)完全二叉树(c)不是完全二叉树

A

G

F

E

D

C

B第20页，课件共155页，创作于2023年2月下面是两个关于完全二叉树的性质性质4：具有n个结点的完全二叉树的深度为：trunc(log2n)+1.trunc(x)为取整函数。对完全二叉树的结点编号：从上到下，每一层从左到右按顺序编号。

A

F

E

D

C

B123456性质5：在完全二叉树中编号为i的结点1）若有左孩子，则左孩编号为2i2）若有右孩子，则右孩子结点编号为2i+13）若有双亲，则双亲结点编号为trunc(i/2)第21页，课件共155页，创作于2023年2月树与二叉树的区别A．树的结点个数至少为1，而二叉树的结点个数可以为0。B．树中结点的最大度数没有限制，二叉树结点最大度数为2。C．树的结点子树无左、右之分，二叉树的结点子树有明确的左、右之分。

二叉树树第22页，课件共155页，创作于2023年2月三、二叉树的存储结构顺序存储结构实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素特点：结点间关系蕴含在其存储位置中浪费空间，适于存满二叉树和完全二叉树abcdefgabcde0000fg1234567891011用一组连续的存储单元存放二叉树的数据元素。结点在数组中的相对位置蕴含着结点之间的关系。第23页，课件共155页，创作于2023年2月链式存储结构二叉链表typedefstructnode{datatypedata;structnode*lchild,*rchild;}JD;lchilddatarchildABCDEFG在n个结点的二叉链表中，有n+1个空指针域

AB

C

D

E

F

G^^^^^^^^第24页，课件共155页，创作于2023年2月三叉链表typedefstructnode{datatypedata;structnode*lchild,*rchild,*parent;}JD;lchilddataparentrchildABCDEFG

A

B

C

D

E

F

G^^^^^^^^^第25页，课件共155页，创作于2023年2月第一节7.1.实例引入【学习任务】通过实例分析，了解树形结构的特点。【例7.1】连锁店结构示意图。假设北京某食品连锁店，为扩大其经销范围，增强其销售能力和竞争实力，在东北地区的哈尔滨、长春、沈阳等城市建立分店，由于经销得当，销售情况良好，在每个城市分店处又可建立了若干分店，其结构图如图7.1所示。第26页，课件共155页，创作于2023年2月第一阶段北京总店哈尔滨分店长春分店沈阳分店分店1分店1……分店m……分店n分店1……分店p图7.1北京某食品连锁店结构图第27页，课件共155页，创作于2023年2月第二节7.2树【学习任务】掌握树的定义和相关概念，了解树的表示方法，理解树的存储结构。7.2.1树的定义树（Tree）是由n（n≥0）个结点构成的有限集合。结点数为0的树称为空树，结点数大于0的树称为非空树。结点：结点由数据元素和构造数据元素之间关系的指针组成。指针指向结点的子树的分支。图7.2(a)是一棵只有1个结点的树，图7.2(b)是一棵具有12个结点的树.第28页，课件共155页，创作于2023年2月第二阶段AABCDEFIGHJKL(a)只有根结点的树(b)一般的树第29页，课件共155页，创作于2023年2月叶子结点和分支结点：将度为0的结点称为叶子结点，又称为终端结点。将度不为0的结点称为分支结点，又称为非终端结点。图7.2(b)中的E、F、G、H、J、K、L都是叶子结点。A、B、C、D、I结点都是分支结点。孩子结点和双亲结点：某结点子树的根结点称为该结点的孩子结点。该结点称为孩子结点的双亲结点。如图7.2(b)中的B、C、D结点是A结点的孩子结点，K结点是I结点的孩子结点，相对应的A结点是B、C、D结点的双亲结点。第30页，课件共155页，创作于2023年2月兄弟结点：具有同一双亲的结点互为兄弟结点。如图7.2(b)中的H、I、J结点具有相同的双亲结点D，所以称H、I、J结点为兄弟结点。后裔和祖先：一个结点的所有子树上的任何结点都是该结点的后裔。该结点称为这些后裔结点的祖先。如图7.2(b)中的H、I、J、K、L结点都是结点D后裔，A、D、I结点称为K结点的祖先。结点的层次：从根结点到树中某结点所经路径上的边数加1称为该结点的层次。根结点的层次规定为1，其他结点的层次就是其双亲结点的层次数加1。如图7.2(b)中的H结点层次为3。第31页，课件共155页，创作于2023年2月树的深度：树中所有结点的层次的最大值称为该树的深度。如图7.2(b)中的树深度为4。无序树：如果树中任意结点的各孩子结点的排列没有严格次序，可交换位置，则称该树为无序树。有序树：如果树中任意结点的各孩子结点的排列有严格的次序，不可交换位置，则称该树为有序树。在有序树中，最左边的子树的根结点称为第一个孩子，最右边的称为最后一个孩子。森林：n（n≥0）棵树的集合称为森林。森林和树的概念相近，删除一棵树的根，则所有的子树形成森林；而为森林加上一个根，则森林就变成一棵树。第32页，课件共155页，创作于2023年2月7.2.2树的表示方法树的常用表示方法有以下四种：图形表示法、文氏图表示法、广义表表示法和凹入表示法。1．图形表示法图7.2给出了图形表示树的直观表示法，其中用圆圈表示结点，连线表示结点间的关系，并把树根画在上面。图形表示法主要用于直观描述树的逻辑结构。2．文氏图表示法文氏图表示法采用集合的包含关系表示树，如图7.3所示。第33页，课件共155页，创作于2023年2月3．广义表表示法以广义表的形式表示树，利用广义表的嵌套区间表示树的结构。如图7.4所示。4．凹入表示法（章节目录表示法）采用逐层缩进的方法表示树，有横向凹入表示和竖向凹入表示。图7.5所示为横向凹入表示。第34页，课件共155页，创作于2023年2月DABCEFGIH图7.3文氏图表示法(A(B(D)(E)(F))(C(G)(H(I)))))图7.4广义表表示法ABDEFCGHI图7.5凹入表示法第35页，课件共155页，创作于2023年2月7.2.3树的抽象数据类型1．数据集合每个结点由数据元素和构造数据元素之间关系的指针组成。2．操作集合（1）ClearTree(T)：设置树T为空（2）Root(T)：求树T的根结点。（3）InitTree(T)：初始化树T。（4）CreateTree(x,R)：生成以x为根结点，以森林R为子树的树。（5）Parent(T,x)：求树T中x结点的双亲结点。（6）SetParent(x,y)：把结点x置为以结点y为根结点的树的双亲结点。（7）AddChild(y,i,x)：把以结点x为根的树置为结点y的第i棵子树。第36页，课件共155页，创作于2023年2月（8）DeleteChild(x,i)：删除结点x的第i棵子树。（9）LeftChild(x,y)：把结点x置为结点y的最左孩子结点。（10）RightSibling(x,y)：把结点x置为结点y的右兄弟结点。（11）Child(T,x,i)：求树T中x结点的第i棵子树。（12）Traverse(T)：遍历树T，即按某种顺序依次访问树中的每个结点，且只访问一次。第37页，课件共155页，创作于2023年2月7.2.4树的存储结构对于树，关心的是树在计算机中如何表示和存储。存储树时，既要存储结点的数据元素，又要存储结点之间的逻辑关系。结点之间的逻辑关系有：双亲－孩子关系、兄弟关系。因此，采用树的存储结构主要有双亲表示法、孩子表示法、双亲孩子表示法和孩子兄弟表示法。表示结点之间的逻辑关系主要采用指针或仿真指针。1．双亲表示法使用指针表示每个结点的双亲结点，即双亲表示法。每个结点包含两个域：数据域和指针域。第38页，课件共155页，创作于2023年2月图7.6(a)是对图7.2(b)采用常规指针表示的存储结构，图7.6(b)是对图7.2(b)采用仿真指针表示的存储结构。第39页，课件共155页，创作于2023年2月2．孩子表示法使用指针表示出每个结点的孩子结点，即孩子表示法。由于每个结点的孩子结点个数不同，为了简便起见，孩子表示法中的每个结点的指针域个数是树的度。图7.7是对图7.2(b)采用常规指针表示的存储结构。第40页，课件共155页，创作于2023年2月孩子表示法与双亲表示法的特点相反。孩子表示法可方便的找到一个结点的孩子及其后裔，并能方便的实现树的遍历。第41页，课件共155页，创作于2023年2月3．双亲孩子表示法采用双亲表示法和孩子表示法的优势，使用指针既表示出每个结点的双亲结点，又表示出每个结点的孩子结点，就是双亲孩子表示法。指针域既包括指向孩子的指针，也包括指向双亲结点的指针。图7.8是对图7.2(b)采用常规指针表示的存储结构，其中实线表示孩子指针，虚线表示双亲指针。第42页，课件共155页，创作于2023年2月第43页，课件共155页，创作于2023年2月4．孩子兄弟表示法采用指针既指向每个结点的孩子结点，又指向每个结点的兄弟结点，就是孩子兄弟表示法。指针域包含两个指针，指向孩子结点的指针和指向兄弟结点的指针。图7.9是对图7.2(b)采用常规指针表示的存储结构，其中实线表示孩子指针，虚线表示兄弟指针。第44页，课件共155页，创作于2023年2月第45页，课件共155页，创作于2023年2月第三节7.3二叉树二叉树是一种重要的数据结构类型，其特点在于任一结点最多有两个子树分支，二叉树的度为2。在二叉树中，左右子树是严格区分的，子树的顺序不能随意颠倒。【学习任务】掌握二叉树的相关概念和性质，理解二叉树的存储结构，注意把握树和二叉树的异同。返回第46页，课件共155页，创作于2023年2月7.3.1二叉树的定义定义：二叉树是由n（n≥0）个结点组成的有限集合、每个结点最多有两个子树的有序树。它或者是空集，或者是由一个根和称为左、右子树的两个不相交的二叉树组成。特点：（1）二叉树是有序树，即使只有一个子树，也必须区分左、右子树；（2）二叉树的每个结点的度不能大于2，只能取0、1、2三者之一；（3）二叉树中所有结点的形态有5种：空结点、无左右子树的结点、只有左子树的结点、只有右子树的结点和具有左右子树的结点。如图7.10所示。第47页，课件共155页，创作于2023年2月7.3.2二叉树的性质【学习任务】掌握二叉树的性质，注意二叉树、满二叉树、完全二叉树和扩充二叉树之间的联系。第48页，课件共155页，创作于2023年2月性质1二叉树的第i层上最多有个结点。性质2深度为h的二叉树上最多有-1个结点。性质3具有n个结点的二叉树的高度不小于的最大整数。性质4任意一棵二叉树中，如果叶子结点的个数为，度为2的结点的个数为，则必然有＝＋1。满二叉树若深度为h的二叉树，恰好具有-1个结点，则称为满二叉树。如图7.11(a)所示完全二叉树若一棵具有n个结点的二叉树的逻辑结构与满二叉树的前n个结点的逻辑结构完全相同，则称该二叉树为完全二叉树。如图7.11(b)所示。第49页，课件共155页，创作于2023年2月扩充二叉树除叶子结点外，其余结点都必须有两个孩子的二叉树。如图7.11(c)所示。第50页，课件共155页，创作于2023年2月性质5具有个结点的完全二叉树的高度为┍┑性质6假定对一棵有n个结点的完全二叉树中的结点，按从上到下、从左到右的顺序，从1到n编号。设树中某个结点的序号为i，则1≤i≤n，则有以下关系：（1）若i等于1，则该结点为二叉树的根；（2）若i＞1，则该结点的双亲结点的序号为┗i/2┛；（3）若2i≤n，则该结点的左孩子的序号为2i，否则该结点无左孩子结点；（4）若2i+1≤n，则该结点的右孩子结点为2i+1，否则该结点无右孩子结点。事实上，根据编码规则，序号i-1和i的结点的关系如图7.12所示的两种情况，即在同一层或在两层上第51页，课件共155页，创作于2023年2月7.3.3二叉树的抽象数据类型1．数据集合每个结点由数据元素和两个构造数据元素之间关系的指针组成。第52页，课件共155页，创作于2023年2月2．操作集合（1）CreateBinTree(x,LBT,RBT)：创建一棵以x为根结点、以LBT为左子树、以RBT为右子树的二叉树；（2）DestroyBinTree(BT)：撤销二叉树BT；（3）IsEmpty(BT)：判断二叉树BT是否为空，为空则返回true，否则返回false；（4）ClearBinTree(BT)：移除所有结点，使二叉树BT成为空二叉树；（5）Root(BT)：返回二叉树BT的根结点；（6）Parent(BT,x)：返回二叉树BT中结点x（x不能是根结点）的双亲结点。如果结点x是根结点或者二叉树中没有结点x，则返回空；第53页，课件共155页，创作于2023年2月（7）LeftChild(x,BT)：返回二叉树BT中结点x的左孩子结点；（8）RightChild(x,BT)：返回二叉树BT中结点x的右孩子结点；（9）MakeBinTree(x,LBT,RBT)：构造一棵以x为根结点、以LBT为左子树、以RBT为右子树的二叉树。（10）BreakBinTree(BT,x,LBT,RBT)：把二叉树BT拆分为三部分，x为根结点，LBT和RBT分别为原二叉树的左、右子树。（11）AddLChild(BT,y,SBT)：把子二叉树SBT插在二叉树BT中作为结点y的左子树。（12）AddRChild(BT,y,SBT)：把子二叉树SBT插在二叉树BT中作为结点y的右子树。第54页，课件共155页，创作于2023年2月（13）PreOrder(BT)：前序遍历二叉树BT。（14）InOrder(BT)：中序遍历二叉树BT。（15）PostOrder(BT)：后序遍历二叉树BT。7.3.4二叉树的存储结构二叉树的存储结构有顺序存储结构、链式存储结构、仿真指针存储结构。1．顺序存储结构顺序存储结构采用一维数组存储的。根据二叉树的性质6可计算出双亲结点、左右孩子结点的下标。因此满二叉树、完全二叉树的存储可采用一维数组，把结点按从上到下、从左到右的顺序存放在数组中，结点之间的关系可由性质6的公式计算得到。第55页，课件共155页，创作于2023年2月图7.11(a)在数组中的存储形式为1234567图7.11(b)在数组中的存储形式为123456一般二叉树不宜采用顺序表示，这是由于如果采用该方法表示，不能确定一棵普通二叉树的各种关系。一般二叉树可采用链式存储结构。第56页，课件共155页，创作于2023年2月如果需要采用顺序存储结构存储一棵普通二叉树时，可采用在一棵普通二叉树中增添一些并不存在的空结点使之变成完全二叉树的形态，然后再采用顺序存储结构存储。图7.13(a)是一棵普通二叉树，图7.13(b)是图7.13(a)添加空结点后的完全二叉树形态，图7.13(c)是图7.13(b)采用一维数组的顺序存储表示（符号∧表示空结点）。第57页，课件共155页，创作于2023年2月2．链式存储结构链式存储结构采用链表存储二叉树中的数据元素，用链建立二叉树中结点之间的关系。二叉树最常用的链式存储结构是二叉链，每个结点包含三个域，分别是数据元素域data、左孩子链域lChild和右孩子链域rChild，结点结构为：第58页，课件共155页，创作于2023年2月lChilddatarChild与单链表带头结点和不带头结点的两种情况相似，二叉链存储结构的二叉树也有带头结点和不带头结点两种。对于图7.13(a)所示的二叉树，带头结点和不带头结点的二叉链存储结构的二叉树如图7.14(a)和(b)所示。第59页，课件共155页，创作于2023年2月第60页，课件共155页，创作于2023年2月3．仿真指针存储结构二叉树的仿真指针存储结构使用数组存储二叉树中的结点，数组中每个结点除数据域外，增加仿真指针域用于仿真常规指针构造二叉树中结点之间的逻辑关系。二叉树的仿真指针存储结构包含仿真二叉链存储结构和仿真三叉链存储结构。第61页，课件共155页，创作于2023年2月7.4二叉树的结点类及二叉树类【学习任务】掌握二叉树的结点类和二叉树类的定义，注意其使用特点。7.4.1二叉树结点类结点是构造二叉树的根本，只有建立了结点，才能在此基础上进行二叉树的设计。下面是二叉树结点类的定义。

publicclassBinTreeNode{ //二叉树结点类

privateBinTreeNodelChild; //左孩子结点对象引用

privateBinTreeNoderChild; //右孩子结点对象引用

publicObjectdata; //数据元素第62页，课件共155页，创作于2023年2月

BinTreeNode(){ //构造二叉树结点

lChild=null;rChild=null; } BinTreeNode(Objectitem,BinTreeNodeleft,BinTreeNoderight){ //构造二叉树结点

data=item; lChild=left; rChild=right; }第63页，课件共155页，创作于2023年2月

BinTreeNode(Objectitem){ //构造二叉树结点

data=item; lChild=null; rChild=null; } publicBinTreeNodegetLeft(){ //返回左孩子

returnlChild; } publicBinTreeNodegetRight(){ //返回右孩子

returnrChild; }第64页，课件共155页，创作于2023年2月

publicObjectgetData(){ //返回数据元素

returndata; }publicvoidsetLeft(BinTreeNodeleft){ //设置左孩子

lChild=left;}publicvoidsetRight(BinTreeNoderight){ //设置右孩子

rChild=right;}}第65页，课件共155页，创作于2023年2月第四节7.4.2二叉树类二叉树类是在二叉树结点类的基础上设计的，这里设计的二叉树类只实现最基本的创建二叉树、删除二叉树的操作，其他操作将在以后随着探讨的深入不断增加。

publicclassBinTree{ //二叉树类

privateBinTreeNoderoot;BinTree(){ //构造方法

root=null;}第66页，课件共155页，创作于2023年2月BinTree(Objectitem,BinTreeleft,BinTreeright){//构造方法

BinTreeNodel=null,r=null;if(left==null)l=null;elsel=left.root;if(right==null)r=null;elser=right.root;root=newBinTreeNode(item,l,r);}第67页，课件共155页，创作于2023年2月

publicbooleanroot(Objectx){ //返回根结点元素函数

if(root!=null){x=root.getData();returntrue;}elsereturnfalse;}publicvoidMakeTree(Objectx,BinTreeleft,BinTreeright){//创建二叉树

if(root!=null||left==right) return;root=newBinTreeNode(x,left.root,right.root);第68页，课件共155页，创作于2023年2月

left.root=null;right.root=null;}publicvoidBreakTree(Objectx,BinTreeleft,BinTreeright){//删除二叉树

if(root==null||left==right||left.root!=null||right.root!=null)return;x=root.getData();left.root=root.getLeft();right.root=root.getLeft();//deleteroot;root=null;}… //遍历算法第69页，课件共155页，创作于2023年2月第五节7.5二叉树的遍历【学习任务】掌握二叉树前序、中序、后序遍历算法的思想，理解递归遍历算法及实例应用。7.5.1二叉树遍历算法由于二叉树是递归定义的，所以二叉树遍历操作也可设计成递归算法。（1）前序遍历（DLR）递归算法描述如下：若二叉树为空，算法结束；否则：①访问根结点；②前序遍历左子树；③前序遍历右子树。第70页，课件共155页，创作于2023年2月（2）中序遍历（LDR）递归算法描述如下：若二叉树为空，算法结束；否则：①中序遍历左子树；②访问根结点； ③中序遍历右子树。（3）后序遍历（LRD）递归算法描述如下：若二叉树为空，算法结束； 否则：①后序遍历左子树； ②后序遍历右子树； ③访问根结点。第71页，课件共155页，创作于2023年2月图7.15给出了二叉树三种遍历算法的例子。第72页，课件共155页，创作于2023年2月二叉树还可以按层次遍历，即先访问根结点，再依次访问下层结点，每层结点按从左至右的顺序访问，直至全部结点访问完毕。对于图7.15所示的二叉树，按层次遍历的结果为：ABCDEF。二叉树的层次遍历可以借助队列来完成，算法如下：（1）把根结点压入队列；（2）如果队列非空，循环执行以下操作：①从队列中取出队头结点，访问该结点； ②若该结点的左孩子结点非空，则将该结点的左孩子结点压入队列； ③若该结点的右孩子结点非空，则将该结点的右孩子结点压入队列；（3）结束。第73页，课件共155页，创作于2023年2月7.5.2二叉树遍历算法的实现1.访问结点算法访问结点表示遍历到该结点时，对该结点进行的具体操作。操作随着问题的不同而不同，这里设计一个访问类Visit输出结点内容。

publicclassVisit{publicvoidprint(Objectitem){System.out.print(item+””);}}第74页，课件共155页，创作于2023年2月2.遍历算法publicclassBinTree{ //二叉树类

…publicstaticvoidPreOrder(BinTreeNoder,Visitvs){//前序遍历二叉树

if(r!=null){vs.print(r.data);PreOrder(r.getLeft(),vs);PreOrder(r.getRight(),vs);}}publicstaticvoidInOrder(BinTreeNoder,Visitvs){//中序遍历二叉树

if(r!=null){InOrder(r.getLeft(),vs);vs.print(r.data);InOrder(r.getRight(),vs);}}第75页，课件共155页，创作于2023年2月

publicstaticvoidPostOrder(BinTreeNoder,Visitvs){ //后序遍历二叉树

if(r!=null){PostOrder(r.getLeft(),vs);PostOrder(r.getRight(),vs);vs.print(r.data);}}

publicstaticvoidLevelOrder(BinTreeNoder,Visitvs) //层次遍历二叉树

throwsException{java.util.Queueq=newjava.util.LinkedList();if(r==null)return;BinTreeNodecurrent;第76页，课件共155页，创作于2023年2月

q.add(r);while(!q.isEmpty()){ current=(BinTreeNode)q.remove();vs.print(current.data);if(current.getLeft()!=null)q.add(current.getLeft());if(current.getRight()!=null)q.add(current.getRight());}}}第77页，课件共155页，创作于2023年2月7.5.3非递归的二叉树遍历算法非递归的二叉树前序遍历算法为： （1）初始化一个空堆栈； （2）把根结点指针压入栈； （3）当堆栈不为空时，循环执行以下操作： ①弹出栈顶结点指针，访问该结点； ②如果该结点的右孩子结点不为空，则将该结点右孩子结点指针压入栈； ③如果该结点的左孩子结点不为空，则将该结点的左孩子结点压入栈； （4）结束。对于图7.14(a)所示的二叉树，非递归的二叉树前序遍历算法的执行过程如表7.1所示。第78页，课件共155页，创作于2023年2月表7.1非递归二叉树前序遍历算法执行过程步骤操作堆栈内容当前访问结点0入栈(A)1出栈A2入栈(C)3入栈(B),(C)4出栈(C)B5入栈(D),(C)6出栈(C)D7出栈C8入栈(F)9入栈(E),(F)10出栈(F)E11出栈F12栈空第79页，课件共155页，创作于2023年2月即遍历结果为ABDCEF，和递归的前序遍历结果一致。非递归的二叉树前序遍历函数如下：publicstaticvoidpreOrderNonRecu(BinTreeNoderoot,Visitvs)throwsException{ java.util.Stacks=newjava.util.Stack(); //创建链式堆栈类对象

if(root==null) //空树，结束

return; BinTreeNodecurr; s.push(root); //根结点压入堆栈第80页，课件共155页，创作于2023年2月

while(!s.isEmpty()){ //栈不为空，从栈顶弹出结点并访问

curr=(BinTreeNode)s.pop(); //弹出栈顶指针

vs.print(curr.data); //访问结点

if(curr.getRight()!=null) //右孩子不为空，右孩子结点压入堆栈

s.push(curr.getRight()); if(curr.getLeft()!=null) //左孩子不为空，左孩子结点压入堆栈

s.push(curr.getLeft()); }}第81页，课件共155页，创作于2023年2月7.5.4二叉树遍历的应用1.根据输入的前序序列，创建二叉树publicBinTreecreateBinTree(){ //根据输入的前序序列，创建二叉树

BinTreer; charch='';;BufferedReaderin=newBufferedReader(newInputStreamReader(System.in)); try{ CharArrayReadercar=newCharArrayReader(in.readLine().toCharArray()); ch=(char)car.read();//输入字符

}catch(Exceptione){ //TODO:handleexception } 第82页，课件共155页，创作于2023年2月

if(ch=='') //空字符时停止创建

r=null; else{ r=newBinTree(); //创建二叉树对象

r.root=newBinTreeNode(ch); //生成二叉树对象的根结点

r.root.setLeft(createBinTree().root);//创建其左子树

r.root.setRight(createBinTree().root); //创建其右子树

} returnr;}第83页，课件共155页，创作于2023年2月2.查找元素在以R为根结点的二叉树中查找数据元素x，如果查找到则返回该结点，否则返回空。

publicstaticBinTreeNodesearch(BinTreeNoder,Objectx){BinTreeNodetemp;if(r==null) //树，查找失败

returnnull;if(r.data.equals(x)) //比较根结点，相同则成功返回该结点

returnr;if(r.getLeft()!=null){ //在左子树查找第84页，课件共155页，创作于2023年2月

temp=search(r.getLeft(),x); //左子树查找结果

if(temp!=null) //查找结果不空，则成功返回该结点

returntemp;}if(r.getRight()!=null){ //在右子树查找

temp=search(r.getRight(),x); //右子树查找结果

if(temp!=null) //查找结果不空，则成功返回该结点

returntemp;}returnnull; //查找不到，返回空

}第85页，课件共155页，创作于2023年2月3.求二叉树的高度二叉树的高度为二叉树中结点层次的最大值。所以，需要遍历左子树求其高度，再遍历右子树求其高度，而二叉树的高度是左、右子树层次高者再加1。publicstaticintdepthOfBinTree(BinTreeNoder){inthigh,lh,rh;if(r==null) //二叉树空，高度为0return0;第86页，课件共155页，创作于2023年2月

else{lh=depthOfBinTree(r.getLeft()); //左子树高度

rh=depthOfBinTree(r.getRight()); //右子树高度

if(lh>rh) //左子树高度大

high=lh+1; //二叉树的高度为左子树高度加1elsehigh=rh+1; //否则高度为右子树高度加1}returnhigh;}第87页，课件共155页，创作于2023年2月第六节7.6线索二叉树【学习任务】掌握线索二叉树的定义，了解线索二叉树的存储结构、遍历方法、构造方法。7.6.1线索二叉树的定义在二叉树的链式存储结构中，增加指向前驱和后继结点的信息，称为线索。加上线索的二叉树叫做线索二叉树（ThreadedBinaryTree）。对二叉树以某种次序进行遍历使其成为线索二叉树的过程叫做线索化。第88页，课件共155页，创作于2023年2月7.6.2线索二叉树的存储结构1.线索二叉树存储结构的确定在由n个结点构成的二叉树链式存储结构中，存在着n+1个空链域。可利用这些空链域建立起相应结点的前驱结点信息和后继结点信息。思想：在二叉链中，如果某结点有左子树，则其lChind域指向其左孩子，否则其lChild域指向该结点在遍历序列中的前驱结点；如果某结点有右子树，则其rChild域指向其右孩子，否则其rChild域指向该结点在遍历序列中的后继结点。第89页，课件共155页，创作于2023年2月为了区分一个结点中的lChild域和rChild域指向的是左、右孩子还是前驱、后继，需要在结点中再增设两个线索标志域ltag和rtag来区分这两种情况。线索标志域定义如下：

第90页，课件共155页，创作于2023年2月因此，每个结点包含5个域。lChildltagdatartagrChild2.线索的画法在二叉树中，结点的前驱和后继需要根据遍历的不同而不同，因此线索二叉树也分为前序线索二叉树、中序线索二叉树和后序线索二叉树。如图7.16(a)所示为图7.15(a)对应的中序线索二叉树，如图7.16(b)所示为图7.15(a)对应的前序线索二叉树，如图7.16(c)所示为图7.15(a)对应的后序线索二叉树。因此，每个结点包含5个域。第91页，课件共155页，创作于2023年2月第92页，课件共155页，创作于2023年2月和其他结构一样，线索二叉树也可包含有头结点。头结点的data域为空，lChild域指向二叉树的根结点，ltag为0，rChild域指向某种遍历的最后一个结点，rtag为1。如图7.17所示为图7.15(a)的中序线索链表。第93页，课件共155页，创作于2023年2月第94页，课件共155页，创作于2023年2月7.6.3遍历线索二叉树本算法基于图7.16所示的具有头结点的存储结构，采用这样的存储结构，既可以从第一个结点开始起顺着后继线索进行遍历，又可以从最后一个结点顺着前驱线索进行遍历。遍历中序线索二叉树的算法如下：publicclassBinThrTreeNode{ //线索二叉树结点类privateBinThrTreeNodelChild; //左孩子结点对象引用privateBinThrTreeNoderChild; //右孩子结点对象引用第95页，课件共155页，创作于2023年2月

publicObjectdata; //数据元素

privateintltag,rtag; //线索标志域

publicBinThrTreeNodegetLeft(){ returnlChild; } publicvoidsetLeft(BinThrTreeNodechild){ lChild=child; }… } publicclassBinThrTree{ //线索二叉树类

privateBinThrTreeNoderoot //线索二叉树头结

publicBinThrTreecreateInOrderThrd(); //中序线索二叉树

… }第96页，课件共155页，创作于2023年2月publicvoidinOrderTraverseThrTree(BinThrTreeNodeh,Visitvs){//遍历中序线索二叉树,h为头结点

BinThrTreeNodep; p=h.getLeft(); while(p!=h){ while(p.getLtag()==0) p=p.getLeft(); vs.print(p.getData()); while(p.getRtag()==1&&p.getRight()!=h){ p=p.getRight(); vs.print(p.getData()); } p=p.getRight(); }}第97页，课件共155页，创作于2023年2月7.6.4构造中序线索二叉树构造中序线索二叉树就是中序遍历并线索化二叉树，线索化的实质是将二叉链表中的空域改为指向前驱或后继的线索，而前驱或后继线索的信息需要在遍历的过程中得到，因此，线索化的过程就是在遍历二叉树的过程中修改空链域的过程。算法思想：为了构造中序线索二叉树，需要在对二叉树进行遍历的过程中建立线索，即边遍历边线索化。如果访问的某结点的左子树为空，则为其建立前驱线索；如果访问的某结点的右子树为空，则为其建立后继线索。第98页，课件共155页，创作于2023年2月publicvoidinThrd(BinThrTreeNodep){ //在中序遍历二叉树的过程中建立线索的递归算法BinThrTreeNodepre=p;if(p!=null){ inThrd(p.getLeft()); //左子树线索化

if(p.getLeft()==null){ p.setLtag(1); p.setLeft(pre);//建立p结点的前驱线索

} if(p.getRight()==null){ pre.setRtag(1); pre.setRight(p);//建立pre结点的后继线索

} pre=p; //链转接，保持pre指向p的前驱

inThrd(p.getRight());//右子树线索化

}}第99页，课件共155页，创作于2023年2月publicBinThrTreeNodecreateInOrderThrd(BinThrTreeNodehead,BinThrTreeNoder){//head指向头结点，r指向根结点。中序线索二叉树r，并对其进行线索化

BinThrTreeNodepre; head=newBinThrTreeNode(); //建立头结点

head.setLtag(0); //设置头结点标志域

head.setRtag(0); head.setRight(head); //头结点的右链域指向自身

if(r==null) head.setLeft(head); //如果二叉树为空，则左链域指向自身

else{ head.setLeft(r); pre=head; inThrd(r); //进行中序线索化

pre.setRight(head); //最后一个结点线索化

pre.setRtag(1); head.setRight(pre); } returnhead;}第100页，课件共155页，创作于2023年2月第七节7.7树和森林【学习任务】掌握树、森林与二叉树之间相互转换的思想及实现过程。7.7.1树、森林与二叉树的转换下面图示树与二叉树之间的转换，具体转换步骤为：（1）添加兄弟连线：在树中所有具有相同双亲结点的兄弟结点之间增加一条连线；（2）抹除右孩子与双亲连线：对树中不是双亲结点的第一个孩子的结点，只保留新添加的该结点与左兄弟结点之间的连线，删除该结点与双亲结点之间的连线；（3）旋转调整：整理所有保留的和添加的连线，使每个结点的第一个孩子结点连线位于左孩子指针位置，使每个结点的右兄弟结点连线位于右孩子指针位置。树转换为二叉树的过程如图7.18所示。第101页，课件共155页，创作于2023年2月(a)一般的树ABCDEFGH(b)相邻兄弟加连线ABCDEFGH(c)删除双亲与不是第一个右孩子的连线ABCDEFGH(d)整理后的二叉树ABCDEFGH图7.18树转换为二叉树的过程第102页，课件共155页，创作于2023年2月2.森林转换成为二叉树森林转换为二叉树的情况如图7.19所示。(a)森林ABCDE(b)森林的二叉树表示FGHIJKLABCDE图7.19森林转换为二叉树的过程FGHIJKL第103页，课件共155页，创作于2023年2月3.二叉树转换成为树二叉树转换为树的过程如图7.20所示。(d)一般树ABCDEFGH(a)二叉树ABCDEFGH图7.20二叉树转换为树的过程(b)添加连线ABCDEFGH(b)删除连线ABCDEFGH第104页，课件共155页，创作于2023年2月4.二叉树转换成为森林二叉树转换为森林的过程如图7.21所示。(d)森林ABCDEFGHIJKL图7.21二叉树转换为森林的过程(a)二叉树ABCDEFGHIJKL(b)添加连线ABCDEFGHIJKL(c)删除连线ABCDEFGHIJKL第105页，课件共155页，创作于2023年2月7.7.2树和森林的遍历对如图7.22所示的森林，对其进行遍历，结果如下：图7.22森林ABCDEFGHIJKL先根遍历结果为：ABCEDFGHIJLK。中根遍历结果为：BECDAHGFLJKI。后根遍历结果为：EDCBHGLKJIFA。第106页，课件共155页，创作于2023年2月第八节7.8树的应用7.8.1二叉排序树【学习任务】掌握二叉排序树的定义，建立，遍历，插入和删除等操作，注意其与线索二叉树的联系。

1.二叉排序树的定义二叉排序树（Binarysorttree）又称二叉查找树（Binarysearchtree），其中的结点由关键字的值表示。第107页，课件共155页，创作于2023年2月图7.23所示为一个二叉排序树。2.二叉排序树的结点类为了方便实现二叉排序树的各种操作，二叉排序树的结点采用三叉链存储结构。第108页，课件共155页，创作于2023年2月publicclassBinTreeNode3{ //三叉链结点类

privateBinTreeNode3lChild,rChild,parent; //左右孩子、双亲结点引用

privateintdata; publicBinTreeNode3(){ //无参构造函数

lChild=null; rChild=null; } publicBinTreeNode3(intitem){ //带参构造函数

lChild=null; rChild=null; data=item; }第109页，课件共155页，创作于2023年2月publicBinTreeNode3(intitem,BinTreeNode3left,BinTreeNode3right){//构造函数

data=item; lChild=left; rChild=right; } publicvoidsetParent(BinTreeNode3parent){ //设置双亲指针

this.parent=parent; } publicBinTreeNode3getParent(){ //返回双亲指针

returnparent; } publicvoidsetLeft(BinTreeNode3left){ //设置左孩子

lChild=left; } publicBinTreeNode3getLeft(){ //返回左孩子指针

returnlChild; }第110页，课件共155页，创作于2023年2月

publicvoidsetRight(BinTreeNode3right){ //设置右孩子

rChild=right; } publicBinTreeNode3getRight(){ //返回右孩子指针

returnrChild; } publicvoidsetData(intdata){ //设置数据域

this.data=data; } publicintgetData(){ //设置数据域

returndata; }}第111页，课件共155页，创作于2023年2月

3.二叉排序树的建立研究二叉排序树，应