数据结构第6章 树和二叉树Word文件下载.docx
《数据结构第6章 树和二叉树Word文件下载.docx》由会员分享，可在线阅读，更多相关《数据结构第6章 树和二叉树Word文件下载.docx（32页珍藏版）》请在冰点文库上搜索。
子的双亲子孙。
以某结点为根的子树中的所有结点都被称为是该结点的子孙。
祖先。
从根结点到该结点路径上的所有结点。
兄弟。
同一个双亲的孩子之间互为兄弟。
堂兄弟。
双亲在同一层的结点互为堂兄弟。
3、树的基本运算
常用操作：
（1）构造一个树CreateTree（T）
（2）清空以T为根的树ClearTree（T）
（3）判断树是否为空TreeEmpty（T）
（4）获取给定结点的第i个孩子Child（T,linklist,i）
（5）获取给定结点的双亲Parent（T,linklist）
（6）遍历树Traverse（T）
对树遍历的主要目的是将非线性结构通过遍历过程线性化，即获得一个线性序列。
树的遍历顺序有两种，一种是先序遍历，即先访问根结点，然后再依次用同样的方法访问每棵子树；
另一种是后序遍历，即先依次用同样的方法访问每棵子树,在访问根节点。
6.1.2树的存储结构
图6-2双亲表示法
类型定义：
#defineMAX_TREE_LINKLIST_SIZE100
typedefstruct{
TElemtypeinfo;
intparent;
}ParentLinklist;
ParentLinklistelem[MAX_TREE_LINKLIST_SIZE];
intn;
//树中当前的结点数目
}ParentTree;
这种存储方法的特点是寻找结点的双亲很容易，但寻找结点的孩子比较困难。
算法实现举例：
intParent（ParentTreeT,intlinklist）
{if（linklist<
0||linklist>
=T.n）return-2;
elsereturnT.elem[linklist].parent;
}
图6-3孩子表示法
在C语言中，这种存储形式定义如下：
#defineMAX_TREE_LINKLIST_SIZE10
typedefstructChildLinklist{
intchild;
//该孩子结点在一维数组中的下标值
structChileLinklist*next;
//指向下一个孩子结点
}CLinklist;
typedefstruct{
Elemtypeinfo;
//结点信息
CLinklist*firstchild;
//指向第一个孩子结点的指针
}TLinklist;
TLinklistelem[MAX_TREE_LINKLIST_SIZE];
intn,root;
//n为树中当前结点的数目，root为根结点在一维数组中的位置
}ChildTree;
这种存储结构的特点是寻找某个结点的孩子比较容易，但寻找双亲比较麻烦，所以，在必要的时候，可以将双亲表示法和孩子表示法结合起来，即将一维数组元素增加一个表示双亲结点的域parent，用来指示结点的双亲在一维数组中的位置。
获取给定结点第i个孩子的操作算法实现：
intChild（ChildTreeT,intlinklist,inti）{
if（linklist<
=T.n）return-2；
p=T.elem[linklist].firstchild;
j=1;
while（p&
&
j!
=i）{p=p->
next;
j++;
}
if（!
p）return-2;
elsereturnp->
child;
}
3、孩子兄弟表示法
孩子兄弟表示法也是一种链式存储结构。
它通过描述每个结点的一个孩子和兄弟信息来反映结点之间的层次关系，其结点结构为：
图6-4孩子兄弟表示法
在C语言中，这种存储形式定义如下：
typedefstructCSLinklist{
Elemtypeelem;
structCSLinklist*firstchild,*nextsibling;
}CSLinklist,*CSTree;
voidAllChild（CSTreeT,CSTreep）
//输出树中p指针所指结点的所有孩子信息
{
q=p->
fisrtchild;
while（q）{
printf（"
%c"
q->
elem）;
q=q->
nextsibling;
6.2二叉树
6.2.1二叉树的定义和基本运算
定义：
二叉树是另一种树形结构。
它与树形结构的区别是：
（1）每个结点最多有两棵子树；
（2）子树有左右之分。
二叉树也可以用递归的形式定义：
二叉树是n（n≥0）个结点的有限集合。
当n=0时，称为空二叉树；
当n>
0时，有且仅有一个结点为二叉树的根，其余结点被分成两个互
不相交的子集，一个作为左子集，另一个作为右子集，每个子集又是一个二叉树。
（如图6-5）
图6-5二叉树
二叉树的5种形态（如图6-6）
图6-6二叉树的5中形态
2、二叉树的基本运算
（1）构造一棵二叉树CreateBTree（BT）
（2）清空以BT为根的二叉树ClearBTree（BT）
（3）判断二叉树是否为空BTreeEmpty（BT）
（4）获取给定结点的左孩子LeftChild（BT,linklist），
（5）获取给定结点的右孩子RightChild（BT,linklist）
（6）获取给定结点的双亲Parent（BT,linklist）
（7）求二叉树的深度BiTreeDepth（linklistBT）
（8）遍历二叉树Traverse（BT）
6.2.2二叉树的性质
二叉树具有下列5个重要的性质。
性质1在二叉树的第i层上最多有2i-1个结点（i≥1）。
二叉树的第1层只有一个根结点，所以，i=1时，2i-1=21-1=20=1成立。
假设对所有的j，1≤j<
i成立，即第j层上最多有2j-1个结点成立。
若j=i-1，则第j层上最多有2j-1=2i-2个结点。
由于在二叉树中，每个结点的度最大为2，所以可以推导出第i层最多的结点个数就是第i-1层最多结点个数的2倍，即2i-2*2=2i-1。
性质2深度为K的二叉树最多有2K-1个结点（K≥1）。
由性质1可以得出，1至K层各层最多的结点个数分别为：
20,21,22,23,...,2k-1。
这是一个以2为比值的等比数列，前n项之和的计算公式为：
性质3对于任意一棵二叉树BT，如果度为0的结点个数为n0，度为2的结点
个数为n2，则n0=n2+1。
证明：
假设度为1的结点个数为n1，结点总数为n，B为二叉树中的分支数。
因为在二叉树中，所有结点的度均小于或等于2，所以结点总数为：
n=n0+n1+n2
（6.1）
再看分支数。
在二叉树中，除根结点之外，每个结点都有一个从上向下的分支
指向，所以，总的结点个数n与分支数B之间的关系为：
n=B+1。
又因为在二叉树中，度为1的结点产生1个分支，度为2的结点产生2个分支，
所以分支数B可以表示为：
B=n1+2n2。
将此式代入上式，得：
n=n1+2n2+1
（6.2）
用（6.1）式减去（6.2）式，并经过调整后得到：
n0=n2+1。
满二叉树：
如果一个深度为K的二叉树拥有2K-1个结点，则将它称为满二叉树。
如图6-7。
图6-7完全二叉树
完全二叉树：
有一棵深度为h，具有n个结点的二叉树，若将它与一棵同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为1~n的结点位置一一对应，则称这棵二叉树为完全二叉树。
请判断在下图6-7的二叉树中，哪些是完全二叉树？
哪些不是完全二叉树？
图6-7
性质4具有n个结点的完全二叉树的深度为[log2n]+1。
其中，[log2n]的结果是不大于log2n的最大整数。
假设具有n个结点的完全二叉树的深度为K，则根据性质2可以得出：
2K-1-1<
n≤2K-1
将不等式两端加1得到：
2K-1≤n<
2K
将不等式中的三项同取以2为底的对数，并经过化简后得到：
K-1≤log2n<
K
由此可以得到：
log2n=K-1。
整理后得到：
K=log2n+1。
性质5对于有n个结点的完全二叉树中的所有结点按从上到下，从左到右的顺序进行编号，则对任意一个结点i（1≤i≤n），都有：
（1）如果i=1，则结点i是这棵完全二叉树的根，没有双亲；
否则其双亲结点的编号为[i/2]。
（2）如果2i>
n，则结点i没有左孩子；
否则其左孩子结点的编号为2i。
（3）如果2i+1>
n，则结点i没有右孩子；
否则其右孩子结点的编号为2i+1。
利用数学归纳法证明。
首先证明
（2）和（3）。
当i=1时，若n≥3，则根的左、右孩子的编号分别是2，3；
若n<
3，则根没有右孩子；
若n<
2，则根将没有左、右孩子；
以上对于
（2）和（3）均成立。
假设：
对于所有的1≤j≤i结论成立。
即：
结点j的左孩子编号为2j；
右孩子编号为2j+1。
图6-8完全二叉树编号
由完全二叉树的结构可以看出：
结点i+1或者与结点i同层且紧邻i结点的右侧，或者i位于某层的最右端，i+1位于下一层的最左端。
可以看出，i+1的左、右孩子紧邻在结点i的孩子后面，由于结点i的左、右孩子编号分别为2i和2i+1，所以，结点i+1的左、右孩子编号分别为2i+2和2i+3，经提取公因式可以得到：
2（i+1）和2（i+1）+1，即结点i+1的左孩子编号为2（i+1）；
右孩子编号为2（i+1）+1。
又因为二叉树由n个结点组成，所以，当2（i+1）+1>
n，且2（i+1）=n时，结点i+1只有左孩子，而没有右孩子；
当2（i+1）>
n，结点i+1既没有左孩子也没有右孩子。
以上证明得到
（2）和（3）成立。
利用上面的结论证明
（1）。
对于任意一个结点i，若2i≤n，则左孩子的编号为2i，反过来结点2i的双亲就是i，而[2i/2]=i；
若2i+1≤n，则右孩子的编号为2i+1，反过来结点2i+1的双亲就是i，而
[（2i+1）/2]=i，由此可以得出
（1）成立。
6.2.3二叉树的存储结构
二叉树也可以采用两种存储方式：
顺序存储结构和链式存储结构。
1、顺序存储结构
这种存储结构适用于完全二叉树。
其存储形式为：
用一组连续的存储单元按照完全二叉树的每个结点编号的顺序存放结点内容。
下面是一棵二叉树及其相应的存储结构（如图6-9）
图6-9二叉树的顺序存储
在C语言中，顺序存储结构的类型定义如下所示：
Elemtypeelem[MAX_TREE_LINKLIST_SIZE];
//根存储在下标为1的数组单元中intn;
//当前完全二叉树的结点个数
}QBTree;
这种存储结构的特点是空间利用率高、寻找孩子和双亲比较容易。
二叉树在这种存储形式下的操作算法。
（1）构造一棵完全二叉树
voidCreateBTree（QBTree*BT,Elemtypeelem[],intn）{
if（n>
=MAX_TREE_LINKLIST_SIZE）n=MAX_TREE_LINKLIST_SIZE-1;
for（i=1;
i<
=n;
i++）
BT->
elem[i]=elem[i];
n=n;
（2）获取给定结点的左孩子
intLeftCHild（QBTreeBT,intlinklist）{
if（2*linklist>
BT.n）return0;
elsereturn2*linklist;
RightChild（BT,linklist）与这个操作类似，读者可试着自行完成。
（3）获取给定结点的双亲
intParent（QBTreeBT,intlinklist）{
if（1<
=linklist&
linklist<
=BT.n）returni/2;
elsereturn-1;
2、链式存储结构
在顺序存储结构中，利用编号表示元素的位置及元素之间孩子或双亲的关系，因此对于非完全二叉树，需要将空缺的位置用特定的符号填补，若空缺结点较多，势必造成空间利用率的下降。
在这种情况下，就应该考虑使用链式存储结构。
常见的二叉树结点结构如下所下所示：
其中，Lchild和Rchild是分别指向该结点左孩子和右孩子的指针，elem是数据元素的内容。
在C语言中的类型定义为：
typedefstructBTLinklist{
Elemtypeelem;
structBTLinklist*Lchild,*Rchlid;
}BTLinklist,*BTree;
下面是一棵二叉树及相应的链式存储结构（如图6-10）
图6-10二叉树的链式存储
这种存储结构的特点是寻找孩子结点容易，双亲比较困难。
因此，若需要频繁地寻找双亲，可以给每个结点添加一个指向双亲结点的指针域，其结点结构如下所示。
6.2.4二叉树地遍历
1．二叉树的遍历概念及遍历方式
二叉树的遍历概念
二叉树是一种非线性数据结构，在对它进行操作时，总是逐一对每个数据元素实施操作，这样就存在一个操作顺序问题，由此提出了二叉树的遍历操作。
按某种顺序对二叉树中的每个结点访问一次且仅访问一次的过程称为遍历二叉树。
这里的访问可以是输出、比较、更新、查看元素内容等等各种操作。
（2）二叉树的遍历遍历方式
二叉树的遍历方式分为两大类：
第一类是按根、左子树、右子树三个部分进行访问；
第二类按层次访问。
其中第一类按遍历方式按其遍历的顺序不同又可分为6种：
TLR（根左右）,TRL（根右左）
LTR（左根右）,RTL（右根左）
LRT（左右根）,RLT（右左根）
其中，TRL、RTL和RLT三种顺序在左右子树之间均是先右子树后左子树，这与人们先左后右的习惯不同，因此，往往不予采用。
余下的三种顺序TLR、LTR和LRT根据根访问的位置不同分别被称为先序遍历、中序遍历和后序遍历。
例：
以下是一棵二叉树及其经过三种遍历所得到的相应遍历序列（如图6-11）
图6-11二叉树及其遍历
2.遍历二叉树的递归算法
（1）先序遍历递归算法
算法思想：
if（二叉树为空）{则结束遍历操作}；
else{访问根结点；
先序遍历左子树；
先序遍历右子树；
算法过程：
voidPreOrder（BTreeBT）{
if（BT）{Visit（BT）;
PreOrder（BT->
Lchild）;
Rchild）;
（2）中序遍历递归算法
if（二叉树为空）{结束遍历操作；
else{中序遍历左子树；
访问根结点；
中序遍历右子树。
voidInOrder（BTreeBT）{
if（BT）{InOrder（BT->
Visit（BT）;
InOrder（BT->
（3）后序遍历递归算法
if（二叉树为空）{则结束遍历操作；
else{后序遍历左子树；
后序遍历右子树；
访问根结点。
voidPostOrder（BTreeBT）{
if（BT）{PostOrder（BT->
PostOrder（BT->
3．
层次遍历二叉树
实现方法为从上层到下层，每层中从左侧到右侧依次访问每个结点。
下面我们将给出一棵二叉树及其按层次顺序访问其中每个结点的遍历序列。
（如图6-12）
6-12二叉树的层次遍历
voidLevelOreder（QBTreeBT）{
for（i=1;
i<
=BT.n;
if（BT.elem[i]!
='
#'
）Visite（BT.elem[i]）;
二叉树用链式存储结构表示时，按层遍历的算法实现访问过程描述如下：
访问根结点，并将该结点记录下来；
若记录的所有结点都已处理完毕，则结束遍历操作；
否则重复下列操作。
取出记录中第一个还没有访问孩子的结点，若它有左孩子，则访问左孩子，并将记录下来；
若它有右孩子，则访问右孩子，并记录下来。
在这个算法中，应使用一个队列结构完成这项操作。
所谓记录访问结点就是入队操作；
而取出记录的结点就是出队操作。
这样一来，我们的算法就可以描述成下列形式：
（1）访问根结点，并将根结点入队；
（2）当队列不空时，重复下列操作：
从队列退出一个结点；
若其有左孩子，则访问左孩子，并将其左孩子入队；
若其有右孩子，则访问右孩子，并将其右孩子入队；
算法描述如下：
voidLevelOrder（BTree*BT）{
if（!
BT）exit;
InitQueue（Q）;
p=BT;
//初始化
Visite（p）;
EnQueue（&
Q,p）;
//访问根结点，并将根结点入队
while（!
QueueEmpty（Q））{//当队非空时重复执行下列操作
DeQueue（&
Q,&
p）;
//出队
p->
Lchild）{Visite（p->
EnQueue（&
Q,p->
//入左子树
Rchild）{Visite（p->
//入右子树
5．对遍历二叉树的讨论
（1）各种遍历序列中左右孩子结点的顺序不变性
对一棵二叉树中序遍历时，若我们将二叉树严格地按左子树的所有结点位
于根结点的左侧，右子树的所有结点位于根右侧的形式绘制，就可以对每个结点
做一条垂线，映射到下面的水平线上，由此得到的顺序就是该二叉树的中序遍历
序列：
（如图6-13）
图6-13二叉树的中序遍历映射
（2）遍历过程的本质是将非线性结构线性化的过程
任何一棵二叉树都可以将它的外部轮廓用一条线绘制出来，我们将它称为
二叉树的包线，这条包线对于理解二叉树的遍历过程很有用。
如图6-14。
图6-14二叉树的外部轮廓
由此可以看出：
遍历操作实际上是将非线性结构线性化的过程，其结果为线
性序列，并根据采用的遍历顺序分别称为先序序列、中序序列或后序序列；
遍历
操作是一个递归的过程，因此，这三种遍历操作的算法可以用递归函数实现。
（3）
三种遍历过程的区别
遍历过程中，每个结点经过三次，三种遍历的区别是：
先序遍历，第一次经过时就访问；
中序遍历，第二次经过时访问；
后序遍历，第三次经过时才访问；
（4）
遍历序列与二叉树形态特点的关系
先、中序遍历序列相同或相反二叉树的形态特点分别是什么？
先、后序遍历序列相同或相反二叉树的形态特点分别是什么？
中、后序遍历序列相同或相反二叉树的形态特点分别是什么？
（5）遍历的递归算法转化为非递归算法一般方法是什么？
6.2.5二叉树遍历算法的应用
1、按二叉树的先序遍历序列构造这棵二叉树
为了保证唯一地构造出所希望的二叉树，在键入这棵树的先序序列时，需要在所有空二叉树的位置上填补一个特殊的字符，比如，'
。
在算法中，需要对每个输入的字符进行判断，如果对应的字符是'
，则在相应的位置上构造一棵空二叉树；
否则，创建一个新结点。
整个算法结构以先序遍历递归算法为基础，二叉树中结点之间的指针连接是通过指针参数在递归调用返回时完成。
算法：
BTreePre_Create_BT（）{
getch（ch）;
if（ch=='
）returnNULL;
//构造空树
else{BT=（BTree）malloc（sizeof（BTLinklist））;
//构造新结点
data=ch;
lchild=Pre_Create_BT（）;
//构造左子树
rchild=Pre_Create_BT（）;
//构造右子树
returnBT;
2、计算一棵二叉树的叶子结点数目（度为1或2的结点的个数）
这个操作可
升级会员 