数据结构（Java语言实现） 课件 陈锐 第5、6章 树和二叉树、图

第5章树和二叉树结构Java实据现数目录CONTENTS5.1

树的定义和抽象数据类型5.2二叉树的定义、性质5.3二叉树的遍历5.6并查集5.4二叉树的线索化5.5树、森林与二叉树5.7哈夫曼树5.1树的定义和抽象数据类型5.1.1树的定义唐·欧·克努特（DonaldErvinKnuth）教授开创了数据结构的最初体系，他所著的《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。树（Tree）是n(n≥0)个结点的有限集合。其中，当n=0时，称为空树。当n>0时，称为非空树，该集合满足以下条件：（1）有且只有一个称为根（root）的结点。（2）当n>1时，其余n-1个结点可以划分为m个有限集合T1、T2、…、Tm，且这m个有限集合不相交，其中Ti（1≤i≤m）又是一棵树，称为根的子树。5.1树的定义和抽象数据类型5.1.1树的定义唐·欧·克努特（DonaldErvinKnuth）教授开创了数据结构的最初体系，他所著的《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。图5.1给出了一棵树的逻辑结构，它如同一棵倒立的树。5.1树的定义和抽象数据类型5.1.1树的定义唐·欧·克努特（DonaldErvinKnuth）教授开创了数据结构的最初体系，他所著的《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。树的结点：包含一个数据元素及若干指向子树分支的信息。结点的度：一个结点拥有子树的个数称为结点的度。例如，结点C有3个子树，度为3。叶子结点：也称为终端结点，没有子树的结点也就是度为零的结点称为叶子结点。分支结点：也称为非终端结点，度不为零的结点称为非终端结点。孩子结点：一个结点的子树的根结点称为孩子结点。5.1树的定义和抽象数据类型5.1.1树的定义唐·欧·克努特（DonaldErvinKnuth）教授开创了数据结构的最初体系，他所著的《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。双亲结点：也称父结点，如果一个结点存在孩子结点，则该结点就称为孩子结点的双亲结点。子孙结点：在一个根结点的子树中的任何一个结点都称为该根结点的子孙结点。例如，{G,H,I,M,N}是C的子树，子树中的结点G、H、I、M和N都是C的子孙结点。祖先结点：从根结点开始到达一个结点，所经过的所有分支结点，都称为该结点的祖先结点。例如，N的祖先结点为A、C和I。5.1树的定义和抽象数据类型5.1.1树的定义唐·欧·克努特（DonaldErvinKnuth）教授开创了数据结构的最初体系，他所著的《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。兄弟结点：一个双亲结点的所有孩子结点之间互相称为兄弟结点。例如，E和F是B的孩子结点，因此，E和F互为兄弟结点。树的度：树中所有结点的度的最大值。例如，图5.1中右边的树的度为3，因为结点C的度为3，该结点的度是树中拥有最大的度的结点。结点的层次：从根结点开始，根结点为第一层，根结点的孩子结点为第二层，依此类推，如果某一个结点是第L层，则其孩子结点位于第L+1层。5.1树的定义和抽象数据类型5.1.1树的定义唐·欧·克努特（DonaldErvinKnuth）教授开创了数据结构的最初体系，他所著的《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。树的深度：也称为树的高度，树中所有结点的层次最大值称为树的深度。例如，图5.1中右边的树的深度为4。有序树：如果树中各个子树的次序是有先后次序的，则称该树为有序树。无序树：如果树中各个子树的次序是没有先后次序，则称该树为无序树。森林：m棵互不相交的树构成一个森林。如果把一棵非空的树的根结点删除，则该树就变成了一个森林，森林中的树由原来的根结点各个子树构成。5.1树的定义和抽象数据类型5.1.2树的逻辑表示唐·欧·克努特（DonaldErvinKnuth）教授开创了数据结构的最初体系，他所著的《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。（1）树形表示法。（2）文氏图表示法。（3）广义表表示法。(A(B(E(K,L),F),C(G(M),H,I(N)),D(J)))（4）凹入表示法。5.1树的定义和抽象数据类型5.1.3树的抽象数据类型唐·欧·克努特（DonaldErvinKnuth）教授开创了数据结构的最初体系，他所著的《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。ADTTree{

数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D为空集，则称为空树。若D仅含一个数据元素，则R为空集，否则R={H}，H是如下二元关系：（1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；（2）若D-{root}≠¢，则存在D-{root}的一个划分D1，D2，…，Dm(m>0)，对任意的j≠k(1≤j,k≤m)有Dj∩Dk=¢，且对任意的i(1≤i≤m)，唯一存在数据元素xi∈Di，有<root,xi>∈H；（3）对应于D-{root}的划分，H-{<root,x1>},…,<root,xn>}有唯一的一个划分H1，H2，…，Hm(m>0)，对任意的j≠k(1≤j,k≤m)有Dj∩Dk=¢，且对任意的i(1≤i≤m)，Hi是Di上的二元关系，(Di,{Hi})是一棵符合本定义的树，称为root的子树。5.1树的定义和抽象数据类型5.1.3树的抽象数据类型唐·欧·克努特（DonaldErvinKnuth）教授开创了数据结构的最初体系，他所著的《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。基本操作：（1）InitTree(&T)

初始条件：树T不存在。操作结果：构造空树T。（2）DestroyTree(&T)

初始条件：树T存在。操作结果：销毁树T。（3）CreateTree(&T)

初始条件：树T存在。操作结果：根据给定条件构造树T。5.1树的定义和抽象数据类型5.1.3树的抽象数据类型唐·欧·克努特（DonaldErvinKnuth）教授开创了数据结构的最初体系，他所著的《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。（10）DeleteChild(&T,p,i)

初始条件：树T存在，p指向T中某个结点，1≤i≤d，d为p所指向结点的度。操作结果：将p所指向的结点的第i棵子树删除。如果删除成功，返回1，否则返回0。（11）TraverseTree(T)

初始条件：树T存在。操作结果：按照某种次序对T的每个结点访问且仅访问一次。（12）TreeDepth(T)

初始条件：树T存在。操作结果：若树T非空，返回树的深度，如果是空树，返回0。}ADTTree5.2二叉树的定义、性质和抽象数据类型5.2.1二叉树的定义二叉树（BinaryTree）是另一种树结构，它的特点是每个结点最多只有两棵子树。树可以转化为唯一一棵二叉树，二叉树可以简化树的处理。下面给出二叉树的五种基本形态，如图5.4所示。5.2二叉树的定义、性质和抽象数据类型5.2.1二叉树的定义一个由12个结点构成的二叉树如图5.5所示。F是C的左孩子结点，G是C的右孩子结点，L是G的右孩子结点，G的左孩子结点不存在。5.2二叉树的定义、性质和抽象数据类型满二叉树和完全二叉树每层结点都是满的二叉树称为满二叉树，即在满二叉树中，每一层的结点都具有最大的结点个数。图5.6所示就是一棵满二叉树。在满二叉树中，每个结点的度或者为2，或者为0（即叶子结点），不存在度为1的结点。5.2二叉树的定义、性质和抽象数据类型满二叉树和完全二叉树如果一棵二叉树有n个结点，并且二叉树的n个结点的结构与满二叉树的前n个结点的结构完全相同，则称这样的二叉树为完全二叉树。完全二叉树及对应编号如图5.8所示。而图5.9所示就不是一棵完全二叉树。5.2二叉树的定义、性质和抽象数据类型5.2.2二叉树的性质（1）性质1：在二叉树中，第m(m≥1)层上至多有2m-1个结点（规定根结点为第一层）。证明：利用数学归纳法证明。当m=1时，即根结点所在的层次，有2m-1=21-1=20=1，命题成立。假设当m=k时，命题成立，即第k层至多有2k-1个结点。因为在二叉树中，每个结点的度最大为2，则在第k+1层，结点的个数最多是第k层的2倍，即2×2k-1=2k-1+1=2k。即当m=k+1时，命题成立。思考：第i层上至少有

1

个结点？5.2二叉树的定义、性质和抽象数据类型5.2.2二叉树的性质（2）性质2：深度为k(k≥1)的二叉树至多有2k-1个结点。证明：第i层结点的最多个数2i-1，将深度为k的二叉树中的每一层的结点的最大值相加，就得到二叉树中结点的最大值，因此深度为k的二叉树的结点总数至多有：

思考：深度为k时至少有

个结点？k5.2二叉树的定义、性质和抽象数据类型5.2.2二叉树的性质（3）性质3：对任何一棵二叉树T，如果叶子结点总数为n0，度为2的结点总数为n2，则有n0=n2+1。证明：假设二叉树中结点总数为n，度为1的结点总数为n1。则：n=n0+n1+n2。假设二叉树的分支数为Y，有n=Y+1。二叉树的所有分支都是由度为1和度为2的结点发出，所以分支数Y=n1+2×n2。故n=Y+1=n1+2×n2+1。联合两式，得到n0+n1+n2=n1+2×n2+1，即n0=n2+1。

5.2二叉树的定义、性质和抽象数据类型5.2.2二叉树的性质（4）性质4：如果完全二叉树有n个结点，则深度为

log2n

+1。符号表示不大于x的最大整数。证明：假设具有n个结点的完全二叉树的深度为k。k层完全二叉树的结点个数介于k-1层满二叉树与k层满二叉树结点个数之间。根据性质2，k-1层满二叉树的结点总数为n1=2k-1-1，k层满二叉树的结点总数为n2=2k-1。因此有n1<n≤n2，即n1+1≤n<n2+1，又n1=2k-1-1和n2=2k-1，故得到2k-1-1≤n<2k-1，同时对不等式两边取对数，有k-1≤log2n<k。因为k是整数，k-1也是整数，所以k-1=

log2n

，即k=

log2n

+1。命题成立。

5.2二叉树的定义、性质和抽象数据类型5.2.2二叉树的性质（5）性质5：如果完全二叉树有n个结点，按照从上到下、从左到右的顺序，对二叉树中的每个结点从1到n进行编号，则对于任意结点i有以下性质： 如果i=1，则序号i对应的结点就是根结点，该结点没有双亲结点。如果i>1，则序号为i的结点的双亲结点的序号为。 如果2×i>n，则序号为i的结点没有左孩子结点。如果2×i≤n，则序号为i的结点的左孩子结点的序号为2×i。 如果2×i+1>n，则序号为i的结点没有右孩子结点。如果2×i+1≤n，则序号为i的结点的右孩子结点序号为2×i+1。

一棵完全二叉树有2000个结点，则其叶结点的个数是（）。10005.2二叉树的定义、性质和抽象数据类型5.2二叉树的定义、性质和抽象数据类型5.2.3二叉树的抽象数据类型ADTBinaryTree{

数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D=¢，则称BinaryTree为空二叉树。若D≠¢，则R={H}，H是如下二元关系：（1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；（2）若D-{root}≠¢，则存在D-{root}={Dl，Dr}，且Dl∩Dr=¢。（3）若Dl≠¢，则Dl中存在唯一的元素xl，<root,xl>∈H，且存在Dl上的关系HlH；若Dr≠¢，则Dr中存在唯一的元素xr，<root,xr>∈H，且存在Dr上的关系HrH；H={<root,xl>,<root,xr>,Hl,Hr}；（4）(Dl，{Hl})是一棵符合本定义的二叉树，称为根的左子树，(Dr,{Hr})是一棵符合本定义的二叉树，称为根的右子树。

5.2二叉树的定义、性质和抽象数据类型5.2.3二叉树的抽象数据类型基本操作P：（1）InitBiTree(&T)

初始条件：二叉树T不存在。操作结果：构造空二叉树T。（2）CreateBiTree(&T)

初始条件：给出了二叉树T的定义。操作结果：创建一棵非空的二叉树T。

5.2二叉树的定义、性质和抽象数据类型5.2.3二叉树的抽象数据类型（10）PreOrderTraverse(T)

初始条件：二叉树T存在。操作结果：先序遍历二叉树T，即先访问根结点、再访问左子树、最后访问右子树，对二叉树中的每个结点访问且仅访问一次。（11）InOrderTraverse(T)

初始条件：二叉树T存在。操作结果：中序遍历二叉树T，即先访问左子树、再访问根结点、最后访问右子树，对二叉树中的每个结点访问，且仅访问一次。（12）PostOrderTraverse(T)

初始条件：二叉树T存在。操作结果：后序遍历二叉树T，即先访问左子树、再访问右子树、最后访问根结点，对二叉树中的每个结点访问，且仅访问一次。（13）LevelTraverse(T)

初始条件：二叉树T存在。操作结果：对二叉树进行层次遍历。即按照从上到下、从左到右，依次对二叉树中的每个结点进行访问。

5.2二叉树的定义、性质和抽象数据类型5.2.4二叉树的存储表示1.二叉树的顺序存储我们已经知道，完全二叉树中每个结点的编号可以通过公式计算得到，因此，完全二叉树的存储可以按照从上到下、从左到右的顺序依次存储在一维数组中。

5.2二叉树的定义、性质和抽象数据类型5.2.4二叉树的存储表示对于非完全二叉树来说，这种存储方式会浪费内存空间的浪费。在最坏的情况下，如果每个结点只有右孩子结点，而没有左孩子结点，则需要占用2k-1个存储单元，而实际上，该二叉树只有k个结点。5.2二叉树的定义、性质和抽象数据类型5.2.4二叉树的存储表示2.二叉树的链式存储在二叉树中，每个结点有一个双亲结点和两个孩子结点。从一棵二叉树的根结点开始，通过结点的左右孩子地址就可以找到二叉树的每一个结点。因此二叉树的链式存储结构包括三个域：数据域、左孩子指针域和右孩子指针域。5.2二叉树的定义、性质和抽象数据类型5.2.4二叉树的存储表示为了方便找到结点的双亲结点，在二叉链表的存储结构中增加一个指向双亲结点的指针域parent。这种存储结构称为三叉链表结点存储结构。classBiTreeNode//二叉树的结点类型{chardata;BiTreeNodelchild,rchild;BiTreeNode(chardata)

{this.data=data;lchild=null;rchild=null;}}5.2二叉树的定义、性质和抽象数据类型创建二叉树算法实现如下：BiTreeNodeCreateBiTree(charstr[])

{

if(str[pi]=='#')//本层是构建root、root.lchild、root.rchild三个结点{

++pi;

returnnull;

}

BiTreeNoderoot=newBiTreeNode();

root.data=str[pi];

++pi;

root.lchild=CreateBiTree(str);//构造左子树

root.rchild=CreateBiTree(str);//构造右子树

returnroot;//递归结束返回构造好的树的根结点

}5.3二叉树的遍历学习基础学习认知能力二叉树的遍历，即按照某种规律对二叉树的每个结点进行访问，使得每个结点仅被访问一次的操作。这里的访问，可以是对结点的输出、统计结点的个数等。如果限定先左后右的次序，则在以上6种遍历方案中，只剩下3种方案：DLR、LDR和LRD。其中，DLR称为先序遍历，LDR称为中序遍历，LRD称为后序遍历。5.3.1二叉树遍历的定义5.3二叉树的遍历学习基础学习认知能力5.3.2二叉树的先序遍历二叉树的先序遍历的递归定义如下：如果二叉树为空，则执行空操作。如果二叉树非空，则执行以下操作：（1）访问根结点。（2）先序遍历左子树。（3）先序遍历右子树。根据二叉树的先序递归定义，得到图5.16所示的二叉树的先序序列为：A、B、D、G、E、H、I、C、F、J。5.3二叉树的遍历学习基础学习认知能力二叉树的先序递归算法。publicvoidPreOrderTraverse(BiTreeNodeT)

//先序遍历二叉树的递归实现

{

if(T!=null){

System.out.print(T.data+"");//访问根结点

PreOrderTraverse(T.lchild);//先序遍历左子树

PreOrderTraverse(T.rchild);//先序遍历右子树

}

}5.3二叉树的遍历二叉树的先序非递归遍历从二叉树的根结点开始，访问根结点，然后将根结点的指针入栈，重复执行以下两个步骤：（1）如果该结点的左孩子结点存在，访问左孩子结点，并将左孩子结点的指针入栈。重复执行此操作，直到结点的左孩子不存在；（2）将栈顶的元素（指针）出栈，如果该指针指向的右孩子结点存在，则将当前指针指向右孩子结点。重复执行以上两个步骤，直到栈空为止。5.3二叉树的遍历publicvoidPreOrderTraverse2(BiTreeNodeT)

//先序遍历二叉树的非递归实现

{

BiTreeNodestack[]=newBiTreeNode[MAXSIZE];//定义一个栈，用于存放结点的指针

inttop=0;BiTreeNodep=T;

while(p!=null||top>0){

while(p!=null)//如果p不空，访问根结点，遍历左子树

{

System.out.print(p.data+"");//访问根结点

stack[top++]=p;

p=p.lchild;//遍历左子树

}

if(top>0)//如果栈不空

{

p=stack[--top];//栈顶元素出栈

p=p.rchild;//遍历右子树

}

}

}5.3二叉树的遍历5.3.3二叉树的中序遍历二叉树的中序遍历的递归定义如下：如果二叉树为空，则执行空操作。如果二叉树非空，则执行以下操作：（1）中序遍历左子树。（2）访问根结点。（3）中序遍历右子树。根据二叉树的中序递归定义，图5.16的二叉树的中序序列为：D、G、B、H、E、I、A、F、J、C。。5.3二叉树的遍历（1）如果该结点的左孩子结点存在，将左孩子结点的指针入栈。重复执行此操作，直到结点的左孩子不存在；（2）将栈顶的元素（指针）出栈，并访问该指针指向的结点，如果该指针指向的右孩子结点存在，则将当前指针指向右孩子结点。重复执行以上（1）和（2），直到栈空为止。publicvoidInOrderTraverse2(BiTreeNodeT)//中序遍历二叉树的非递归实现{BiTreeNodestack[]=newBiTreeNode[MAXSIZE];//定义一个栈，用于存放结点的指针

inttop=0;//定义栈顶指针,初始化栈

BiTreeNodep=T;while(p!=null||top>0){while(p!=null)//如果p不空，则遍历左子树

{stack[top++]=p;//将p入栈

p=p.lchild;//遍历左子树

}if(top>0)//如果栈不空

{p=stack[--top];//栈顶元素出栈

System.out.print(p.data+"");//访问根结点

p=p.rchild;//遍历右子树

}}}5.3二叉树的遍历5.3.4二叉树的后序遍历二叉树的后序遍历的递归定义如下：如果二叉树为空，则执行空操作。如果二叉树非空，则执行以下操作：（1）后序遍历左子树。（2）后序遍历右子树。（3）访问根结点。根据二叉树的后序递归定义，图6.16所示的二叉树的后序序列为：G、D、H、I、E、B、J、F、C、A。publicvoidPostOrderTraverse(BiTreeNodeT)//后序遍历二叉树的递归实现{if(T!=null)//如果二叉树不为空

{PostOrderTraverse(T.lchild);

PostOrderTraverse(T.rchild);

System.out.print(T.data+"");

}}5.3二叉树的遍历（1）如果该结点的左孩子结点存在，将左孩子结点的指针入栈。重复执行此操作，直到结点的左孩子不存在；（2）取栈顶元素（指针）并赋给p，如果p没有右孩子或右孩子结点已经访问过，则访问根结点。否则，则执行p=p.rchild。重复执行以上（1）和（2），直到栈空为止。publicvoidPostOrderTraverse2(BiTreeNodeT)//后序遍历二叉树的非递归实现{BiTreeNodestack[]=newBiTreeNode[MAXSIZE];

inttop=0;BiTreeNodep=T;BiTreeNodeq=null;

//初始化结点的指针

while(p!=null||top>0){while(p!=null)//如果p不空，则遍历左子树

{stack[top++]=p;//将p入栈

p=p.lchild;//遍历左子树

}if(top>0)//如果栈不空

{p=stack[top-1];//取栈顶元素

if(p.rchild==null||p.rchild==q)//如果p没有右孩子结点，或右孩子结点已经访问过

{System.out.print(p.data+"");//访问根结点

q=p;//记录刚刚访问过的结点

p=null;//为遍历右子树做准备

top--;//出栈

}

elsep=p.rchild;

}}}分析：n个结点，则共有2n个链域。除根结点外，每个结点都有一个链域指向自身，因此，有n－1个结点的链域存放有指针。空指针个数＝2n－(n-1)=n+1在n个结点的二叉链表中，有

个空指针域。AB

D

E

F

CG^^^^^^^^n+15.4二叉树的线索化5.4二叉树的线索化为了区分指针域指向的是左孩子结点还是直接前驱结点、右孩子结点还是直接后继结点，增加两个标志域ltag和rtag。结点的存储结构如图5.20所示。其中，当ltag=0时，lchild指示结点的左孩子；当ltag=1时，lchild指示结点的直接前驱结点。当rtag=0时，rchild指示结点的右孩子；当rtag=1时，rchild指示结点的直接后继结点。：5.4二叉树的线索化二叉树按照某种遍历方式使二叉树变为线索二叉树的过程称为二叉树的线索化。图5.21所示就是将二叉树进行先序、中序和后序遍历得到的线索二叉树。5.4二叉树的线索化线索二叉树的存储结构类型描述如下：classBiThrNode//线索二叉树结点{Stringdata;BiThrNodelchild,rchild;intltag,rtag;BiThrNode()

{this.data="NULL";//二叉树的结点值

this.lchild=null;//左孩子

this.rchild=null;//右孩子

this.ltag=0;//线索标志域

this.rtag=0;//线索标志域

}5.4二叉树的线索化为了方便，在二叉树的线索化时，可增加一个头结点。使头结点的指针域lchild指向二叉树的根结点，指针域rchild指向二叉树中序遍历时的最后一个结点，二叉树中的第一个结点的线索指针指向头结点。初始化时，使二叉树的头结点指针域lchild和rchild均指向头结点，并将头结点的标志域ltag置为Link，标志域rtag置为Thread。5.4二叉树的线索化publicBiThrNodeInOrderThreading(BiThrNodeT)

//通过中序遍历二叉树T，使T中序线索化。thrt是指向头结点的指针

{

BiThrNodethrt=newBiThrNode();

//将头结点线索化

thrt.ltag=0;//修改前驱线索标志

thrt.rtag=1;//修改后继线索标志

thrt.rchild=thrt;//将头结点的rchild指针指向自己

if(T==null)//如果二叉树为空，则将lchild指针指向自己

thrt.lchild=thrt;

else{

thrt.lchild=T;//将头结点的左指针指向根结点

pre=thrt;//将pre指向已经线索化的结点

T=InThreading(T);//中序遍历进行中序线索化

//将最后一个结点线索化

pre.rchild=thrt;//将最后一个结点的右指针指向头结点

pre.rtag=1;//修改最后一个结点的rtag标志域

thrt.rchild=pre;//将头结点的rchild指针指向最后一个结点

thrt.lchild=T;//将头结点的左指针指向根结点

}

returnthrt;

}5.4二叉树的线索化publicBiThrNodeInThreading(BiThrNodep){

//二叉树中序线索化

if(p!=null){

InThreading(p.lchild);//左子树线索化

if(p.lchild==null)//前驱线索化

{

p.ltag=1;

p.lchild=pre;

}

if(pre.rchild==null)//后继线索化

{

pre.rtag=1;

pre.rchild=p;

}

pre=p;//pre指向的结点线索化完毕，使p指向的结点成为前驱

InThreading(p.rchild);//右子树线索化

}

returnp;

}5.4二叉树的线索化查找指定结点的中序直接前驱的算法实现如下。publicBiThrNodeInOrderPre(BiThrNodep)

//在中序线索树中找结点p的中序直接前趋

{

if(p.ltag==1)//如果p的标志域ltag为线索，则p的左子树结点即为前驱

returnp.lchild;

else{

pre=p.lchild;//查找p的左孩子的最右下端结点

while(pre.rtag==0)//右子树非空时，沿右链往下查找

pre=pre.rchild;

returnpre;//pre就是最右下端结点

}

}5.4.3线索二叉树的遍历5.4二叉树的线索化中序遍历线索二叉树的算法实现如下。publicvoidInOrderTraverse(BiThrNodeT)

//中序遍历线索二叉树

{

BiThrNodep=T.lchild;//将根结点赋给p

while(p!=T){

while(p!=T&&p.ltag==0)//顺着左孩子线索进行搜索

p=p.lchild;

Print(p);

while(p.rtag==1&&p.rchild!=T){//如果存在右孩子线索，搜索后继结点

p=p.rchild;

Print(p);

}

p=p.rchild;

}

}5.4二叉树的线索化【例5.1】编写程序，建立如图5-21所示的二叉树，并将其中序线索化。任输入一个结点，输出该结点的中序前驱和中序后继。例如，结点’D’的中序直接前驱是’G’，其中序直接后继是’A’。线索二叉树的输出序列：0 Thread B Link 1 Thread G Thread 2 Link D Thread 3 Link A Link 4 Thread E Link 5 Thread H Thread 6 Link C Link 7 Thread F Thread 元素D的中序直接前驱元素是:G元素D的中序直接后继元素是:A元素E的中序直接前驱元素是:A元素E的中序直接后继元素是:H5.5树、森林与二叉树1.双亲表示法双亲表示法是利用一组连续的存储单元存储树的每个结点，并利用一个指示器表示结点的双亲结点在树中的相对位置。通常在Java语言中，利用数组实现连续的单元的存储。树的双亲表示法如图5-23所示。5.5.1树的存储结构5.5树、森林与二叉树classPNode//双亲表示法的结点定义

{

Stringdata;

intparent;//指示结点的双亲

}

classPTree//双亲表示法的类型定义

{

PNodenode[];

intnum;//结点的个数

PTree()

{

node=newPNode[num];

}

}5.5.1树的存储结构5.5树、森林与二叉树2.孩子表示法把每个结点的孩子结点排列起来，看成是一个线性表，且以单链表作为存储结构，则n个结点有n个孩子链表（叶子结点的孩子链表为空表），这样的链表称为孩子链表。5.5树、森林与二叉树classChildNode//孩子结点的类型定义{intchild;ChildNodenext;//指向下一个结点}classDataNode//n个结点数据与孩子链表的指针构成一个结构{intdata;ChildNodefirstchild;//孩子链表的指针}孩子表示法classCTree//孩子表示法类型定义{DataNodenode[];intnum;//结点的个数

introot;//根结点在顺序表中的位置

CTree(){node=newDataNode[num];num=0;root=-1;}}5.5树、森林与二叉树3.孩子兄弟表示法孩子兄弟表示法，也称为树的二叉链表表示法。即以二叉链表作为树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点，分别命名为firstchild域和nextsibling域。5.5树、森林与二叉树3.孩子兄弟表示法树的孩子兄弟表示法的类型描述如下。classCSNode//孩子兄弟表示法的类型定义{Stringdata;CSNodefirstchild,nextsibling;//指向第一个孩子和下一个兄弟}5.5树、森林与二叉树5.5.2树转换为二叉树从树的孩子兄弟表示和二叉树的二叉链表表示来看，它们在物理上的存储方式是相同的，也就是说，从它们的相同的物理结构可以得到一棵树，也可以得到一棵二叉树。5.5树、森林与二叉树5.5.2树转换为二叉树按照以下步骤，可以将一棵树转换为对应的二叉树。（1）在树中的兄弟结点之间加一条连线。（2）在树中，只保留双亲结点与第一个孩子结点之间的连线，将双亲结点与其他孩子结点的连线删除。（3）将树中的各个分支，以某个结点为中心进行旋转，子树以根结点成对称形状。5.5树、森林与二叉树5.5.3森林转换为二叉树按照以下步骤，可以将一棵树转换为对应的二叉树。（1）把森林中的所有树都转换为对应的二叉树。（2）从第二棵树开始，将转换后的二叉树作为前一棵树根结点的右孩子，插入到前一棵树中。然后将转换后的二叉树进行相应的旋转。5.5树、森林与二叉树5.5.4二叉树转换为树和森林（1）在二叉树中，将某结点的所有右孩子结点、右孩子的右孩子结点等等，都与该结点的双亲结点用线条连接。（2）删除掉二叉树中双亲结点与右孩子结点的原来的连线。（3）调整转换后的树或森林，使结点的所有孩子结点处于同一层次。5.6并查集对于并查集，在一些有N个元素的集合应用问题中，初始时通常将每个元素看成是一个单元素的集合，然后按一定次序将属于同一组的元素所在的集合两两合并，其间要反复查找一个元素在哪个集合中。5.6并查集1.初始化每个元素代表一棵树。假设有n个编号分别为1、2、...、n的元素，使用列表parent存储每个元素的父结点，初始化时，先将父结点设为自身。publicclassDisjointSet{finalintMAXSIZE=100;intparent[];intrank[];DisjointSet(intn)

{parent=newint[n+1];rank=newint[n+1];for(inti=0;i<n+1;i++)parent[i]=i;}}5.6并查集将a和f所在的集合（即把a和f两棵树）合并后，使a成为两个结点构成树的父结点。如图5-32(b)所示。如图5-32(c)所示。继续将其他结点进行合并操作，直到所有结点构成一棵树。5.6并查集查找publicintFind(intx){

if(parent[x]==x)

returnx;

else

returnFind(parent[x]);

}5.6并查集查找publicintFind2(intx){

if(parent[x]==x)

returnx;

parent[x]=Find2(x);

returnparent[x];

}带路径压缩的查找算法实现如下：publicintFind_NonRec(intx)

{introot=x;

while(parent[root]!=root)//查找根结点root

root=parent[root];

inty=x;

while(y!=root)//路径压缩

{parent[y]=root;

y=parent[y];

}

returnroot;

}5.6并查集3.合并合并算法主要思想：找到x和y所属子树的根结点root_x和root_y，若root_x==root_y，则表明它们属于同一棵子树，不需合并；否则，需要比较两棵子树的高度，即秩，使合并后的子树高度尽可能小：给你一个由'1'（陆地）和'0'（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。grid=[

["1","1","0","0","0"],

["1","1","0","0","0"],

["0","0","1","0","0"],

["0","0","0","1","1"]

]5.6并查集算法思想：该题要找到岛屿的数量，就是一个利用并查集的合并操作，将所有的元素都合并完，再去还剩下多少个独立集合的问题。每一个岛屿就是一个独立的集合。这里有一个注意点就是需要区分不同的样本，显然要进行合并的样本的值都是字符’1’。5.6并查集发送电文过程中，要将待传字符转换成二进制的字符串，怎样编码才能使转换后的报文尽快发送？BAAACCCADB010000001010100011010000011100100原则：频率高的字符编码尽可能地短5.7哈夫曼树哈夫曼（Huffman）树，也称最优二叉树。它是一种带权路径长度最短的树。A：00B：01C：10D：11A：0B：00C：1D：01编码短注意：在编码时，必须保证任何一个字符的编码不能是其他字符编码的前缀字符串。AAAAAAAABBAAABBA歧义BAAACCCADB00000111001005.7哈夫曼树A：0B：00C：1D：01DCAB000111A：110B：111C：10D：0

1111101101101010101100111BAAACCCADBACDB000111A：0B：110C：10D：111

10100011111101111105.7哈夫曼树使用二叉树对结点进行编码是无歧义的，这种编码就是前缀编码译码时，从根结点出发，扫描字符串，遇到0访问左孩子结点，遇到1访问右孩子结点，直到叶子结点，叶子结点的字符即为该编码对应的字符。BAAACCCADB特点：每一个字符的编码都不是其他字符编码的前缀，绝不会错译!称为前缀码5.7哈夫曼树1010001111110111110ACDB0001115.7哈夫曼树1.路径和路径长度路径是指在树中，从一个结点到另一个结点所走过的路程。路径长度是一个结点到另一个结点的分支数目。2.树的带权路径长度在一些实际应用中，根据结点的重要程度，将树中的某一个结点赋予一个有意义的值，则这个值就是结点的权。（1）WPL=8×2+4×2+2×2+3×2=38（2）WPL=8×2+4×3+2×3+3×1=37（3）WPL=8×1+4×2+2×3+3×3=315.7哈夫曼树（1）由给定的n个权值{w1,w2,…,wn}，构成n棵只有根结点的二叉树集合F={T1,T2,…,Tn}，每个结点的左右子树均为空。（2）在二叉树集合F中，找两个根结点的权值最小和次小的树，作为左、右子树构造一棵新的二叉树，新二叉树的根结点的权重为左、右子树根结点的权重之和。（3）在二叉树集合F中，删除作为左、右子树的两个二叉树，并将新二叉树加入到集合F中。（4）重复执行步骤（2）和（3），直到集合F中只剩下一棵二叉树为止。这颗二叉树就是要构造的哈夫曼树。5.7哈夫曼树例如，假设给定一组权值{1,3,6,9}，按照哈夫曼构造的算法对集合的权重构造哈夫曼树的过程如图5.38所示。classHTNode//哈夫曼树类型定义

{

intweight;

intparent,lchild,rchild;

HTNode()

{

this.weight=weight;

this.parent=parent;

this.lchild=lchild;

this.rchild=rchild;

}

}5.7哈夫曼树若一棵哈夫曼树的叶子结点为n个，则该哈夫曼树结点总数为2n-1算法实现：定义一个类型为HuffmanCode的变量HT，用来存放每一个叶子结点的哈夫曼编码。初始时，将每一个叶子结点的双亲结点域、左孩子域和右孩子域初始化为0。如果有n个叶子结点，则非叶子结点有n-1个，所以总共结点数目是2*n-1个。5.7哈夫曼树若n=4,w={1,3,6,9}，请构造哈夫曼树和哈夫曼编码结点总个数：m=2*4-1=7weightparentlchrch11000230003600049000567weightparentlchrch1150023500366004970054612610753719046a9c6a1b35.7哈夫曼树初始状态最终状态000publicvoidHuffmanCoding(HTNodeHT[],StringHC[],intw[],intn)//构造哈夫曼树HT，哈夫曼树的编码存放在HC中，w为n个字符的权值{if(n<=1)return;intm=2*n-1;for(inti=1;i<=n;i++)//初始化n个叶子结点

{HT[i]=newHTNode();HT[i].weight=w[i-1];HT[i].parent=0；

HT[i].lchild=HT[i].rchild=0;}for(inti=n+1;i<=m;i++)//将n-1个非叶子结点的双亲结点初始化化为0

{HT[i]=newHTNode();HT[i].parent=0;}for(inti=n+1;i<=m;i++)//构造哈夫曼树

{List<Integer>s=Select(HT,i-1);//查找树中权值最小的两个结点

ints1=s.get(0),s2=s.get(1);HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}5.7哈夫曼树

//从叶子结点到根结点求每个字符的哈夫曼编码

//求n个叶子结点的哈夫曼编码

for(inti=1;i<=n;i++)

{charcd[]=newchar[n+1];intstart=n-1;for(intc=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//从叶子结点到根结点求编码

{if(HT[f].lchild==c)cd[--start]='0';

elsecd[--start]='1';}HC[i]=newString()；

Stringstr=newString(cd);HC[i]=str;//将当前求出结点的哈夫曼编码复制到HC}}5.7哈夫曼树请输入叶子结点的个数:4请输入第1个结点的权值:1请输入第2个结点的权值:3请输入第3个结点的权值:6请输入第4个结点的权值:9哈夫曼编码:100哈夫曼编码:101哈夫曼编码:11哈夫曼编码:0"100101011"的译码结果：ABDC【例5.6】通过键盘输入一个表达式，如6+(7-1)*3+9/2，将其转换为二叉树，即表达式树，然后通过二叉树的遍历操作求解表达式的值。1）初始化栈，并将’#’入栈；2）若当前读入的字符ө2是操作数，则将该操作数压入ExpTreeStack栈，并读入下一个字符；3）若当前字符ө2是运算符，则将ө2与栈顶的运算符ө1比较。（1）若ө1优先级低于ө2，则将ө2压入OptrStack栈，继续读入下一个字符；（2）若ө1优先级高于ө2，则从OptrStack栈中弹出ө1，将其作为子树的根结点，并使ExpTreeStack栈执行两次出栈操作，弹出的两个表达式rcd和lcd分别作为ө1的右子树和左子树，从而创建二叉树，并将该二叉树的根结点压入ExpTreeStack栈中。（3）若ө1的优先级与ө2相等，且ө1为’(‘，ө2为’)’，则将ө1出栈，继续读入下一个字符；4）如果ө2的优先级与ө1相等，且ө1和ө2都为’#‘，从OptrStack栈中将ө1弹出，则OptrStack栈为空。则完成中缀表达式转换为表达式树，ExpTreeStack的栈顶元素就是表达式树的根结点，算法结束。重复执行2）~4），直到所有字符读取完毕且OptrStack为空。请输入算术表达式串：6+(7-1)*3+9/2#先序遍历：++6*-713/92中序遍历：6+7-1*3+9/2表达式的值：28.55.8小结树中结点与结点之间是一种一对多的关系。树的定义是递归的。一棵树或者为空，或者是由m棵子树T1、T2、…、Tm组成，这m棵子树又是由其他子树构成的。树中的孩子结点没有次序之分，是一种无序树。二叉树的两棵子树有次序之分。二叉树也是递归定义的，二叉树的两棵子树又是由左子树和右子树构成。在二叉树中，有两种特殊的树：满二叉树和完全二叉树。满二叉树中每个非叶子结点都存在左子树和右子树，所有的叶子结点都处在同一层次上。完全二叉树是指与满二叉树的前n个结点结构相同，满二叉树是一种特殊的完全二叉树。5.8小结二叉树的遍历分为先序遍历、中序遍历和后序遍历。二叉树遍历的过程就是将二叉树这种非线性结构转换成线性结构。通过将二叉树线索化，不仅可充分利用二叉链表中的空指针域，还能很方便地找到指定结点的前驱结点。在哈夫曼树中，只有叶子结点和度为2的结点。哈夫曼树是带权路径最小的二叉树，通常用于解决最优化问题。感谢聆听主讲：结构Java实据现数第6章图结构Java实据现数目录CONTENTS6.1

图的定义及相关概念6.2图的存储结构6.3图的遍历6.6最短路径6.4图的连通性问题6.5有向无环图6.7小结6.1图的定义及相关概念6.1.1图的定义图由数据元素集合与边的集合构成。数据元素常称为顶点（Vertex），顶点集合（V）不能为空，边（E）表示顶点之间的关系，用连线表示。图（G）的形式化定义为：G=(V,E)，其中，V={x|x∈数据元素集合}，E={<x,y>|Path(x,y)/\(x∈V,y∈V)}。Path(x,y)表示从x与y的关系属性。如果<x,y>∈E，则<x,y>表示从顶点x到顶点y的一条弧（Arc），x称为弧尾（Tail）或起始点（Initialnode），y称为弧头（Head）或终端点（Terminalnode）。6.1图的定义及相关概念6.1.1图的定义如果<x,y>∈E且有<y,x>∈E，则用无序对(x,y)代替有序对<x,y>和<y,x>，表示x与y之间存在一条边（Edge），将这样的图称为无向图。6.1图的定义及相关概念6.1.1图的定义对于无向图，边数e的取值范围为0~n(n-1)/2。将具有n(n-1)/2条边的无向图称为完全图。对于有向图，弧度e的取值范围是0~n(n-1)。将具有n(n-1)条弧的有向图称为有向完全图。具有e<nlogn条弧或边的图，称为稀疏图（Sparsegraph）。具有e>nlogn条弧或边的图，称为稠密图（Densegraph）。6.1图的定义及相关概念6.1.2图的相关概念1.邻接点在无向图G=(V,E)中，如果存在边(vi,vj)∈E，则称vi和vj互为邻接点（Adjacent），即vi和vj相互邻接。边(vi,vj)依附于顶点vi和vj，或者称边(vi,vj)与顶点vi和vj相互关联。2.顶点的度在无向图中，顶点v的度是指与v相关联的边的数目，记作TD(v)。在有向图中，以顶点v为弧头的数目称为顶点v的入度（InDegree），记作ID(v)。以顶点v为弧尾的数目称为v的出度（OutDegree），记作OD(v)。顶点v的度为以v为顶点的入度和出度之和，即TD(v)=ID(v)+OD(v)。6.1图的定义及相关概念6.1.2图的相关概念3.路径在图中，从顶点vi出发经过一系列的顶点序列到达顶点vj称为从顶点vi到vj的路径（Path）。路径的长度是路径上弧或边的数目。4.子图假设存在两个图G={V,E}和G’={V’,E’}，如果G’的顶点和关系都是V的子集，即有V’V，E’E，则G’为G的子图。6.1图的定义及相关概念6.1.2图的相关概念5.连通图和强连通图在无向图中，如果从顶点vi到顶点vj存在路径，则称顶点vi到vj是连通的。推广到图的所有顶点，如果图中的任何两个顶点之间都是连通的，则称图是连通图（ConnectedGraph）。无向图中的极大连通子图称为连通分量（ConnectedComponent）。6.1图的定义及相关概念6.1.2图的相关概念6.生成树一个连通图（假设有n个顶点）的生成树是一个极小连通子图，它含有图中的全部顶点，但只有足以构成一棵树的n-1条边。6.1图的定义及相关概念6.1.2图的相关概念7.网在实际应用中，图的边或弧往往与具有一定意义的数有关，即每一条边都有与它相关的数，称为权，这些权可以表示从一个顶点到另一个顶点的距离或花费等信息。这种带权的图称为带权图或网。一个网如图6.6所示。6.1图的定义及相关概念6.1.3图的抽象数据类型7.网在实际应用中，图的边或弧往往与具有一定意义的数有关，即每一条边都有与它相关的数，称为权，这些权可以表示从一个顶点到另一个顶点的距离或花费等信息。这种带权的图称为带权图或网。一个网如图6.6所示。ADTGraph{

数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R={VR}VR={<x,y>|x,y∈V且P(x,y>，<x,y>表示从x到y的弧，谓词P(x,y>定义了弧<x,y>的意义或信息}6.1图的定义及相关概念6.1.3图的抽象数据类型基本操作：

（1）CreateGraph(&G)

初始条件：图G不存在。

操作结果：创建一个图G。

（2）DestroyGraph(&T)

初始条件：图G存在。

操作结果：销毁图G。

（3）LocateVertex(G,v)

初始条件：图G存在，顶点v合法。

操作结果：若图G存在顶点v，则返回顶点v在图G中的位置。若图G中没有顶点v，则函数返回值为空。

（4）GetVertex(G,i)

初始条件：图G存在。

操作结果：返回图G中序号i对应的值。i是图G某个顶点的序号，返回图G中序号i对应的值。6.1图的定义及相关概念6.1.3图的抽象数据类型（5）FirstAdjVertex(G,v)

初始条件：图G存在，顶点v的值合法。操作结果：返回图G中v的第一个邻接顶点。若v无邻接顶点或图G中无顶点v，则函数返回-1。（6）NextAdjVertex(G,v,w)

初始条件：图G存在，w是图G中顶点v的某个邻接顶点。操作结果：返回顶点v的下一个邻接顶点。若w是v的最后一个邻接顶点，则函数返回-1。（11）DFSTraverseGraph(G)

初始条件：图G存在。操作结果：从图中的某个顶点出发，对图进行深度遍历。（12）BFSTraverseGraph(G)

初始条件：图G存在。操作结果：从图中的某个顶点出发，对图进行广度遍历。}ADTGraph6.2图的存储结构6.2.1邻接矩阵表示法图的邻接矩阵表示（AdjacencyMatrix）也称为数组表示。它采用两个数组来表示图：一个是用于存储顶点信息的一维数组，另一个是用于存储图中顶点之间的关联关系的二维数组，这个关联关系数组称为邻接矩阵。6.2图的存储结构学习基础学习认知能力两个图弧和边的集合分别为A={<A,B>,<A,C>,<A,D>,<C,A>,<C,B>,<D,A>}和E={(A,B),(A,D),(B,C),(B,D),(C,D)}。它们的邻接矩阵表示如图6.7所示。6.2图的存储结构学习基础学习认知能力enumKind{DG,DN,UG,UN}//图的类型publicclassMGraph{Stringve