理学第6章 树.docx
《理学第6章 树.docx》由会员分享，可在线阅读，更多相关《理学第6章 树.docx（78页珍藏版）》请在冰点文库上搜索。
理学第6章树
第六章树
树形结构是一种日常生活中应用非常广泛的非线性结构。
从单位的组织结构、家谱到计算机领域中的操作系统、数据库系统都是树状结构的应用实例，甚至某些数据库管理系统就是利用树状结构的原理设计的。
6.1树简介
什么是树结构？
先看一下它的定义：
树（Tree）是一种特殊的数据结构，它可以用来描述有分支的结构，是由一个或一个以上的结点所组成的有限集合，具有下列性质：
●存在一个特殊的结点，称为根（Root）。
●其余结点为n≥0个互斥的集合，即T1，T2，T3，…，Tn，且每个集合称为子树。
如下图所示，A为根结点，B、C、D、E均为A的子结点。
比较下面的两个图形
图（a）是一种合法的树，符合树的定义：
树由一个或一个以上的结点组成，结点间有连接且不形成回路。
图（b）中结点有连接但却形成了回路，故不是一棵合法的树。
接下来了解一下树的专有名词，以下图为例进行说明。
●树根或根结点（Root）：
没有父结点的结点称为根结点，如A。
●父结点（Parend）：
每一个结点的上层结点称为其父结点，如B的父结点为A，G的父结点为C。
●子结点（Children）：
每一个结点的下层结点称为其子结点，如B的子结点为E及F，A的子结点为B、C、D。
●兄弟结点（Siblings）：
有共同父结点的结点称为兄弟结点，如B、C、D的父结点都是A，所以彼此为兄弟结点。
●结点的度（Degree）：
子结点的个数为该结点的度，如A的度为3，B的度为2。
●叶子结点（TerminalNode）：
没有子结点的结点，即度为零的结点，例如E、F、G、H、D都是叶子结点。
●非叶子结点（Non-TerminalNode）：
叶子结点以外的所有结点为非叶子结点，即度不为零的点，如A、B、C都是非叶子结点。
●边（Edge）：
连接两个结点的线段，称之为边。
上图中的边共有7条，一般地，具有n个结点的树，其边数为n-1。
●层（Level）：
树的层，即树根A为层1，B、C、D为层2，E、F、G、H为层3。
●高度（Height）：
树的最大层数。
●森林（Forest）：
森林是由n棵互斥的树组成的集合（n≥0）。
【范例1】下列哪一种结构不是树（Tree）。
A.一个结点B.环形序列
C.一个没有回路的连通图D.一个边数比结点数少1的连通图
解答：
选择B，因为环形序列会形成循环回路现象，不符合树的定义。
【范例2】下图中的树（Tree）中有几个叶子结点？
A.4B.5C.9D.11
解答：
由上图可以看出答案为A，共有E、C、H、I共4个叶子结点。
6.2二叉树简介
一般的树状结构在内存中的存储方式以链表为主，对于n叉树来说，每个结点的度不一定相同，但为了方便起见，必须取n+1为链表结点的最长固定长度，其数据结构如下：
data
link1
link2
…
linkn
假设n叉树有m个结点，那么此树共需要（n+1）×m个存储单元。
而每个结点不一定都会指向下一层的n个结点，会有大量的空值，如此一来，会造成大量的内存空间浪费，为了克服这一缺点，常使用二叉树结构来取代树状结构。
6.2.1二叉树的定义
二叉树是由有限个结点组成的集合，此集合可以为空集合，也可由一个树根或者一个树根与左右两棵子树所组成。
简单的说，二叉树最多只能有两个子结点，即结点的度小于等于2，其数据结构如下：
left
data
right
二叉树和一般树的不同点如下：
●树不可为空集合，但是二叉树可以。
●树的度d≥0，但二叉树的结点度0≤d≤2。
●树的子树间没有次序关系，但二叉树有次序关系。
6.2.2特殊二叉树的介绍
1.满二叉树
如果二叉树高度为n，树的结点为2n-1，则称此树为满二叉树，如下图所示。
2.完全二叉树
如果二叉树的高度为n，则1～n-1层都是满的，第n层的叶子结点严格按从左至右依次排列，则称此二叉树为完全二叉树，如下图所示。
【性质1】假设一棵完全二叉树具有
个节点，则它的高度（层）
。
证明：
设完全二叉树的高度为
，则有
，
，
故
。
3.严格二叉树
如果二叉树的每个非叶子结点都有非空的左、右子树，则称此二叉树为严格二叉树，如下图所示。
4.歪斜树
当一个二叉树完全没有右结点或左结点时，称为左歪斜树或右歪斜树，如下图所示。
5.排序二叉树
设结点由关键字值来表示，用所有结点的关键字值互异，排序二叉树或者是一棵空树，或者是满足以下条件的树：
（1）若左子树不空，则左子树上所有结点的关键字值均小于根结点的关键字值；
（2）若右子树不空，则右子树上所有结点的关键字值均大于根结点的关键字值；
（3）左、右子树也分别是二叉排序树。
创建这种二叉树是最为方便的，它的中序遍历是关键字值的升序排序，故而称之为二叉排序树。
【性质2】高度为h的二叉树的结点总数n≤2h-1。
证明：
其结点总数为各层中度最大的结点数之和，即
【性质3】对于非空二叉树T，如果n0为叶子（即度为0的结点）结点数，且度为2的结点数是n2，试证明：
n0=n2+1。
证明：
假设结点总数为n，n1是度为1的结点数，边数为e，于是，我们有以下关系式
n=n0+n1+n2，e=n-1，e=2n2+n1
由上述三个式子，有n0=n2+1。
6.3二叉树的存储方式
树状结构在程序中的建立大多使用链表来处理，因为链表的指针用来处理树是相当方便的，只需改变指针即可。
当然也可以使用数组这样的连续结构来表示二叉树，使用数组或者链表各有利弊，下面将给予说明。
6.3.1二叉树的数组表示法
如果用一维数组来存储二叉树，首先应将二叉树想象成一棵完全二叉树，凡空值结点均用特殊字符或者数字替代，并且依序将结点值存放到一维数组中。
【范例3】将下图所示的二叉树，用一维字符数组进行表示。
首先将二叉树想象成一棵完全二叉树，其空值结点用*代替，结束符用！
表示。
其一维字符数组的表示形式为：
索引值
1
2
3
4
5
6
7
内容值
A
B
C
*
*
D
！
【范例程序】用一维字符数组表示结点值为字符的二叉树。
/*
名称：
ch06_01.cpp
示范：
用一维字符数组表示结点值为字符的二叉树
*/
#include
#include
usingnamespacestd;
#defineMaxSize100//数组的最大维数
#defineMaxLevel6//设定可输出的二叉树最大层数
intNodeNum=0;//结点计数变量
charNode[MaxSize];//字符型的结点数组
//创建二叉树的结点数组
voidCreateTreeArray（）
{cout<<"按完全二叉树方式输入，若某层有元素为空，用*替代，结束用!
替代"<Node[0]=0;//使Node[0]闲置
while
（1）
{NodeNum++;
cin>>Node[NodeNum];//输入结点值
if（Node[NodeNum]=='!
'）
break;
if（NodeNum==MaxSize）
{cout<<"输入字符个数超限,无法存储，请增大MaxSize的值"<exit（0）;
}
}
}
//输出树
voidDisplayTree（）
{inti,j,k;//循环控制变量
inthight,level,SerialNum;//hight树高，level树层,SerialNum序号
//确定树的高度
for（i=0;i{if（pow（2,i）>NodeNum）
break;
}
hight=i;
//从第1层至第hight层进行二叉树的输出
level=1;SerialNum=1;
while（level<=hight）
{//每层前端空格输出控制
for（i=0;icout<<"";
//每层输出的结点个数控制
for（j=0;j{
if（Node[SerialNum]!
='*'&&Node[SerialNum]!
='!
'）
cout<elseif（Node[SerialNum]=='*'）
cout<<"";//输出空格
else
break;//遇到结束符!
跳出输出
for（k=0;kcout<<"";//每层后端空格输出控制
}
cout<level++;//层数增1
}
cout<}
//输出数组
voidDisplayArray（）
{inti=1;
do
{cout<i++;
}while（Node[i]!
='!
'）;
cout<}
//主函数
voidmain（）
{CreateTreeArray（）;//创建二叉树结点的一维数组
cout<<"二叉树为"<DisplayTree（）;//输出树
cout<<"结点数组为"<DisplayArray（）;//输出数组
system（"pause"）;
}
如果二叉树的结点值是由整数给出的，对它的处理也是类似的。
【范例4】将下图所示的二叉树，用一维整型数组进行表示。
首先将二叉树想象成一棵完全二叉树，其空值结点用0代替，结束符用-1表示。
其一维整型数组的表示形式为：
索引值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
内容值
6
3
9
2
5
7
0
0
0
4
0
0
8
-1
仅需要对上述示范程序作几处简单的修改，就可以用于解决上述问题的编程。
【范例程序】用一维整型数组表示结点值为整数的二叉树。
/*
名称：
ch06_02.cpp
示范：
用一维整型数组表示结点值为整数的二叉树
*/
#include
#include
usingnamespacestd;
#defineMaxSize100//数组的最大维数
#defineMaxLevel6//设定可输出的二叉树最大层数
intNodeNum=0;//结点计数变量
intNode[MaxSize];//整型结点数组
//创建二叉树的结点数组
voidCreateTreeArray（）
{
cout<<"按完全二叉树方式输入，若某层有元素为空，用0替代，结束用-1替代"<Node[0]=0;//使Node[0]闲置
while
（1）
{NodeNum++;
cout<<"请输入第"<";
cin>>Node[NodeNum];//输入结点值
if（Node[NodeNum]==-1）
break;
if（NodeNum==MaxSize）
{cout<<"输入字符个数超限,无法存储，请增大MaxSize的值"<exit（0）;
}
}
}
//输出树
voidDisplayTree（）
{inti,j,k;//循环控制变量
inthight,level,SerialNum;//hight树高，level树层,SerialNum序号
//确定树的高度
for（i=0;i{if（pow（2,i）>NodeNum）
break;
}
hight=i;
//从第1层至第hight层进行二叉树的输出
level=1;SerialNum=1;
while（level<=hight）
{//每层前端空格输出控制
for（i=0;icout<<"";
//每层输出的结点个数控制
for（j=0;j{
if（Node[SerialNum]!
=0&&Node[SerialNum]!
=-1）
cout<elseif（Node[SerialNum]==0）
cout<<"";//输出空格
else
break;//遇到结束符-1,跳出输出
for（k=0;kcout<<"";//每层后端空格输出控制
}
cout<level++;//层数增1
}
cout<}
//输出数组
voidDisplayArray（）
{inti=1;
do
{cout<i++;
}while（Node[i]!
=-1）;
cout<}
//主函数
voidmain（）
{CreateTreeArray（）;//创建二叉树结点的一维数组
cout<<"二叉树为"<DisplayTree（）;//输出树
cout<<"结点数组为"<DisplayArray（）;//输出数组
system（"pause"）;
}
用一维数组表示二叉树，这一方法的优点是：
方法直观且容易实现，而且形象地输出二叉树的实际结构。
其缺点是：
访问、插入、删除操作难以实现，特别是当二叉树不是完全二叉树时，会占用过多的内存空间。
例如，存储以下含4结点的二叉树，却要多花费了8个存储单元，才能完整地表现这一结构。
6.3.2二叉树的链表表示法
二叉树的链表表示法是利用链表来存储二叉树，即运用动态存储结构和指针的方式来建立二叉树。
其结点结构如下：
*left
data
*right
二叉树的结点定义如下：
structBinTreeNode
{chardata;
structBinTreeNode*left,*right;
};
【范例5】对下图所示的二叉树
用链表来表示它，其结构图如下：
构建过程如下：
（1）先将倒数第一层的三个结点建子二叉树，并用相应的结点指针指向其根结点。
（2）再将二层的两个结点建子二叉树，并用相应的结点指针指向其根结点。
（3）最后将第一层的一个结点建子二叉树，并用一个结点指针指向其根结点。
上述子二叉树经过连接之后，便成了我们所需要构建的二叉树。
这种建二叉树的过程是，由叶子结点开始，向上逐层扩建成树。
【范例程序】用链表来表示二叉树。
/*
名称：
ch06_03.cpp
示范：
二叉树的链表表示法
*/
#include
usingnamespacestd;
//二叉树结点定义
structBinTreeNode
{chardata;//结点数据
structBinTreeNode*left,*right;//左、右指针
};
//建二叉树
BinTreeNode*MakeBinTree（chardata,BinTreeNode*left,BinTreeNode*right）
{//以data为数据,left,right为左右子树建树
BinTreeNode*newnode;
newnode=newBinTreeNode;
newnode->data=data;
newnode->left=left;
newnode->right=right;
returnnewnode;
}
//主函数
voidmain（）
{BinTreeNode*aptr,*bptr,*cptr,*dptr,*eptr,*fptr;
dptr=MakeBinTree（'D',NULL,NULL）;
eptr=MakeBinTree（'E',NULL,NULL）;
fptr=MakeBinTree（'F',NULL,NULL）;
bptr=MakeBinTree（'B',dptr,eptr）;
cptr=MakeBinTree（'C',NULL,fptr）;
aptr=MakeBinTree（'A',bptr,cptr）;
system（"pause"）;
}
从上述创建链式二叉树的程序可以发现，这种结构在程序实现上十分复杂，不便于实现其程序控制，而且还无法输出它的实际结构，也无法查找结点的父结点。
但这种结构也有其优点：
那就是查找、插入和删除操作方便。
二叉树结点值的输出需要用它二叉树的遍历，在下一节进行介绍。
6.4二叉树的遍历
遍历二叉树最简单的方法就是遍历树中所有结点各一次，并且在遍历后将树的数据转化为线性关系。
其实二叉树的遍历，并不像之前所提到的线性结构那样简单，就一个简单二叉树结点而言，每个结点都可以区分左、右两个分支。
如下图所示的二叉树共有ABC、ACB、BAC、BCA、CAB、CBA等6种遍历方式。
如果是依照二叉树特性一律由左向右遍历，那么只剩下三种遍历方式，即BAC、ABC、BCA。
以上三种遍历的方式的命名如下。
●中序遍历（BAC，Preorder）：
左子树-树根-右子树。
●前序遍历（ABC，Inorder）：
树根-左子树-右子树。
●后序遍历（BCA，Postorder）：
左子树-右子树-树根。
所谓的中序、前序、后序都是针对根结点而言的，例如中序遍历是根结点在中间，前序遍历是根结点在前面，后序遍历是根结点在后面。
而遍历方式一定是先左子树后右子树。
6.4.1中序遍历
中序遍历的顺序为：
左子树-树根-右子树，即沿树的左子树一直往下，直到无法前进时退后到父结点，而后再往右子树一直往下。
如果右子树也走完了就退回上层的左结点，重复左、中、右的顺序遍历，下图是【范例5】中所给出的二叉树，它的中序遍历为：
DBEACF。
中序遍历的递归（回溯）算法如下：
voidInorder（BinTreeNode*ptr）
{if（ptr!
=NULL）
{Inorder（ptr->left）;//遍历左子树
cout<data;//访问树根
Inorder（ptr->right）;//遍历右子树
}
}
6.4.2前序遍历
前序遍历的顺序为：
树根-左子树-右子树，即从根结点开始处理，根结点处理完后往左子树走，直到无法前进再处理右子树。
【范例5】的前序遍历为ABDECF。
前序遍历的递归（回溯）算法如下：
voidPreorder（BinTreeNode*ptr）
{if（ptr!
=NULL）
{cout<data;//访问树根
Preorder（ptr->left）;//遍历左子树
Preorder（ptr->right）;//遍历右子树
}
}
6.4.3后序遍历
后序遍历的顺序为：
左子树-右子树-树根。
后序遍历和前序遍历相反，它是把左、右子树的结点都处理完才处理树根。
【范例5】的后序遍历为：
DEBFCA。
后序遍历的递归（回溯）算法如下：
voidPostorder（BinTreeNode*ptr）
{if（ptr!
=NULL）
{Postorder（ptr->left）;//遍历左子树
Postorder（ptr->right）;//遍历右子树
cout<data;//访问树根
}
}
6.4.4二叉树的遍历实例
对【范例5】中二叉树，进行中序、前序与后序遍历的操作。
并将其结果输出，请与上面的讨论加以对照。
【范例程序】对【范例5】中的二叉树进行中序、前序与后序遍历，并输出其结果。
/*
名称：
ch06_04.cpp
示范：
二叉树的中序、前序、后序遍历
*/
#include
usingnamespacestd;
//二叉树结点定义
structBinTreeNode
{chardata;//结点数据
structBinTreeNode*left,*right;//左、右指针
};
//建二叉树
BinTreeNode*MakeBinTree（chardata,BinTreeNode*left,BinTreeNode*right）
{//以data为数据,left,right为左右子树建树
BinTreeNode*newnode;
newnode=newBinTreeNode;
newnode->data=data;
newnode->left=left;
newnode->right=right;
returnnewnode;
}
//中序遍历
voidInorder（BinTreeNode*ptr）
{if（ptr!
=NULL）
{Inorder（ptr->left）;//遍历左子树
cout<data;//访问树根
Inorder（ptr->right）;//遍历右子树
}
}
//前序遍历
voidPreorder（BinTreeNode*ptr）
{if（ptr!
=NULL）
{cout<data;//访问树根
Preorder（ptr->left）;//遍历左子树
Preorder（ptr->right）;//遍历右子树
}
}
//后序遍历
voidPostorder（BinTreeNode*ptr）
{if（ptr!
=NULL）
{Postorder（ptr->left）;//遍历左子树
Postorder（ptr->right）;//遍历右子树
cout<data;//访问树根
}
}
//主函数
voidmain（）
{BinTreeNode*aptr,*bptr,*cptr,*dptr,*eptr,*fptr;
dptr=MakeBinTree（'D',NULL,NULL）;
eptr=MakeBinTree（'E',NULL,NULL）;
fptr=MakeBinTree（'F',NULL,NULL）;
bptr=MakeBinTree（'B',dptr,eptr）;
cptr=MakeBinTree（'C',NULL,fptr）;
aptr=MakeBinTree（'A',bptr,cptr）;//aptr成为二叉树的根结点指针
cout
升级会员 