数据结构复习指导6.docx
《数据结构复习指导6.docx》由会员分享，可在线阅读，更多相关《数据结构复习指导6.docx（22页珍藏版）》请在冰点文库上搜索。
数据结构复习指导6
树和二叉树
一、基础知识和算法
1.树及有关概念
树，根，子树；结点，结点的度，叶子（终端结点），分支结点（非终端结点），内部结点，树的度；孩子，双亲，兄弟，祖先，子孙，堂兄弟；层次（根所在层为第1层），深度，高度；有序树，无序树，二叉树是有序树；森林。
2.二叉树
二叉树（二叉树与度为2的树不同，二叉树的度可能是0，1，2）；左孩子，右孩子。
二叉树的五种基本形态。
3.二叉树的性质
二叉树的第i层上至多有2i-1个结点。
深度为k的二叉树至多有2k-1个结点。
满二叉树：
深度为k，有2k-1个结点。
完全二叉树：
给满二叉树的结点编号，从上至下，从左至右，n个结点的完全二叉树中结点在对应满二叉树中的编号正好是从1到n。
叶子结点n0，度为2的结点为n2，则n0=n2+1。
考虑结点个数：
n=n0+n1+n2
考虑分支个数：
n-1=2n2+n1
可得n0=n2+1
例：
1）二叉树有n个叶子，没有度为1的结点，共有个结点。
2）完全二叉树的第3层有2个叶子，则共有个结点。
分析：
1）度为2的结点有n-1个，所以共2n-1个结点。
2）注意考虑到符合条件的二叉树的深度可能是3或4，所以有5、10或11个结点。
n个结点的完全二叉树深度为
。
n个结点的完全二叉树，结点按层次编号
有：
i的双亲是
，如果i=1时为根（无双亲）；
i的左孩子是2i，如果2i>n，则无左孩子；
i的右孩子是2i+1，如果2i+1>n则无右孩子。
4.二叉树的存储结构
顺序存储结构
用数组、编号i的结点存放在[i-1]处。
适合于存储完全二叉树。
链式存储结构
二叉链表：
typedefstructBTNode{
ElemTypedata;
structBTNode*lchild,*rchild;
}BTNode,*BinTree;
三叉链表：
typedefstructBTNode{
ElemTypedata;
structBTNode*lchild,*rchild,*parent;
}BTNode,*BinTree;
例：
用二叉链表存储n个结点的二叉树（n>0），共有（n+1）个空指针域；采用三叉链表存储，共有（n+2）个空指针域。
5.二叉树的五种基本形态
①空树：
bt==NULL②左右子树均空：
bt->lchild==NULLandbt->rchild==NULL
③右子树为空：
bt->rchild==NULL④左子树为空：
bt->lchild==NULL
⑤左右子树均非空。
前两种常作为递归结束条件，后三者常需要递归。
6.遍历二叉树
常见有四种遍历方式
按层次遍历，先序遍历，中序遍历，后序遍历。
按层次遍历：
“从上至下，从左至右”，利用队列。
先序遍历：
DLR；中序遍历：
LDR；后序遍历LRD。
例：
写出a+b*（c-d）-e/f的前缀、中缀和后缀表达式。
画出二叉树，分别进行前序、中序、后序遍历即可得到。
前缀表达式：
-+a*b-cd/ef
中缀表达式：
a+b*c-d-e/f
后缀表达式：
abcd-*+ef/-
先序遍历算法
voidPreorder（BinTreebt）
{
if（bt）{
visit（bt->data）;
Preorder（bt->lchild）;
Preorder（bt->rchild）;
}
}
中序遍历算法
voidInorder（BinTreebt）
{
if（bt）{
Inorder（bt->lchild）;
visit（bt->data）;
Inorder（bt->rchild）;
}
}
后序遍历
voidPostorder（BinTreebt）
{
if（bt）{
Postorder（bt->lchild）;
Postorder（bt->rchild）;
visit（bt->data）;
}
}
非递归遍历二叉树
一般借助栈实现。
设想一指针沿二叉树中序顺序移动，每当向上层移动时就要出栈。
（a）中序非递归遍历
指针p从根开始，首先沿着左子树向下移动，同时入栈保存；当到达空子树后需要退栈访问结点，然后移动到右子树上去。
voidInOrder（BinTreebt,VisitFuncvisit）
{
InitStack（S）;
p=bt;
while（p||!
StackEmpty（S））{
if（p）{
Push（S,p）;
p=p->lchild;
}else{
Pop（S,p）;
visit（p）;//中序访问结点的位置
p=p->rchild;
}
}
}
（b）先序非递归遍历
按照中序遍历的顺序，将访问结点的位置放在第一次指向该结点时。
voidPreorder（BinTreebt,VisitFuncvisit）
{
InitStack（S）;
p=bt;
while（p||!
StackEmpty（S））{
if（p）{
visit（p）;//先序访问结点的位置
Push（S,p）;
p=p->lchild;
}else{
Pop（S,p）;
p=p->rchild;
}
}
}
或者，由于访问过的结点便可以弃之不用，只要能访问其左右子树即可，写出如下算法。
voidPreorder（BinTreebt,VisitFuncvisit）
{
InitStack（S）;
Push（S,bt）;
while（!
StackEmpty（S））{
Pop（S,p）;
if（p）{
visit（p）;
Push（S,p->rchild）;//先进栈，后访问，所以
Push（S,p->lchild）;//这里先让右子树进栈
}
}
}
（c）后序非递归遍历
后序遍历时，分别从左子树和右子树共两次返回根结点，只有从右子树返回时才访问根结点，所以增加一个栈标记到达结点的次序。
voidPostOrder（BinTreebt,VisitFuncvisit）
{
InitStack（S）,InitStack（tag）;
p=bt;
while（p||!
StackEmpty（S））{
if（p）{
Push（S,p）,Push（tag,1）;//第一次入栈
p=p->lchild;
}else{
Pop（S,p）,Pop（tag,f）;
if（f==1）{
//从左子树返回，二次入栈，然后p转右子树
Push（S,p）,Push（tag,2）;
p=p->rchild;
}else{
//从右子树返回（二次出栈），访问根结点，p转上层
visit（p）;
p=NULL;//必须的，使下一步继续退栈
}
}
}
}
注：
后序非递归遍历的过程中，栈中保留的是当前结点的所有祖先。
这是和先序及中序遍历不同的。
在某些和祖先有关的算法中，此算法很有价值。
7.遍历二叉树的应用
写出遍历序列（前、中、后序）
根据遍历序列画出二叉树
（a）已知前序和中序序列，唯一确定二叉树。
例：
前序：
ABDEGCFH，中序：
DBGEAFHC，画出二叉树。
分析：
前序序列的第一个是根，这是解题的突破口。
步骤：
①前序序列的第一个是根②在中序序列中标出根，分成左右子树③在前序序列中标出左右子树（根据结点个数即可）④分别对左右子树的前序和中序序列重复以上步骤直至完成。
（b）已知后序和中序序列，唯一确定二叉树。
例：
后序：
DGEBHFCA，中序：
DBGEAFHC，画出二叉树。
分析：
后序序列的最后一个是根，这是解题的突破口。
步骤：
①后序序列的最后一个是根②在中序序列中标出根，分成左右子树③在后序序列中标出左右子树（根据结点个数即可）④分别对左右子树的后序和中序序列重复以上步骤直至完成。
（c）已知前序和后序序列，不存在度为1的结点时能唯一确定二叉树。
例：
前序：
ABDEC，后序：
DEBCA，画出二叉树。
又前序AB，后序BA则不能唯一确定二叉树。
注：
对于不存在度为1的结点的二叉树，首先确定根结点，然后总可以将其余结点序列划分成左右子树，以此类推即可确定二叉树。
说明：
画出二叉树后可以进行遍历以便验证。
编写算法
思路：
按五种形态（①--⑤）分析，适度简化。
例：
求二叉树结点的个数。
分析：
①0;②1;③L+1;④1+R;⑤1+L+R。
简化：
②1+L=0+R=0③1+L+R=0④1+L=0+R⑤1+L+R可合并成⑤一种情况。
intNodeCount（BinTreebt）
{
if（bt==0）return0;
elsereturn1+NodeCount（bt->lchild）+NodeCount（bt->rchild）;
}
例：
求二叉树叶子结点的个数。
分析：
①0;②1;③L;④R;⑤L+R。
简化：
③④⑤可合并成⑤。
intLeafCount（BinTreebt）
{
if（bt==0）return0;
elseif（bt->lchild==0andbt->rchild==0）return1;
elsereturnLeafCount（bt->lchild）+LeafCount（bt->rchild）;
}
例：
求二叉树的深度。
分析：
①0;②1;③1+L;④1+R;⑤1+max（L,R）。
简化：
②③④⑤可合并成⑤。
intDepth（BinTreebt）
{
if（bt==0）return0;
elsereturn1+max（Depth（bt->lchild）,Depth（bt->rchild））;
}
8.线索二叉树
线索
n个结点的二叉链表中有n+1个空指针，可以利用其指向前驱或后继结点，叫线索，同时需附加一个标志，区分是子树还是线索。
lchild有左子树，则指向左子树，标志ltag==0；
没有左子树，可作为前驱线索，标志ltag==1。
rchild有右子树，则指向右子树，标志rtag==0；
没有右子树，可作为后继线索，标志rtag==1。
线索化二叉树
利用空指针作为线索指向前驱或后继。
左边空指针可以作为前驱线索，右边空指针可以作为后继线索，可以全线索化或部分线索化。
表6.1线索化二叉树的类型
前驱、后继线索
前驱线索
后继线索
中序线索化
中序全线索
中序前驱线索
中序后继线索
前序线索化
前序全线索
前序前驱线索
前序后继线索
后序线索化
后序全线索
后序前驱线索
后序后继线索
画出线索二叉树
思路：
先写出遍历序列，再画线索。
步骤：
标出必要的空指针（前驱左指针；后继右指针，要点：
“不要多标，也不要少标”）。
写出对应的遍历序列（前序，中序或后序）。
对照遍历结果画线索。
例：
画出图中二叉树的后序后继线索。
步骤：
先标出所有空的右指针（DGCH）；写出后序遍历结果：
DGEBHFCA；标出后继线索：
DG,GE,CA,HF。
如图。
遍历线索二叉树
反复利用孩子和线索进行遍历，可以避免递归。
9.树和森林
树的存储结构
双亲表示法，孩子表示法，孩子兄弟表示法。
特点：
双亲表示法容易求得双亲，但不容易求得孩子；孩子表示法容易求得孩子，但求双亲麻烦；两者可以结合起来使用。
孩子兄弟表示法，容易求得孩子和兄弟，求双亲麻烦，也可以增加指向双亲的指针来解决。
树与二叉树的转换
表6.2树和二叉树的对应关系
树
对应的二叉树
根
根
第一个孩子
左孩子
下一个兄弟
右孩子
特点：
由树转化成的二叉树，根结点没有右孩子
例：
树转换成二叉树。
森林与二叉树的转换
森林中第1棵树的根作为对应的二叉树的根；其他的树看作第1棵树的兄弟；森林中的树转换成对应的二叉树。
则森林转换成对应的二叉树。
例：
将森林转换成对应的二叉树。
参见课本P138。
树的遍历
树的结构：
①根，②根的子树。
先根遍历：
①②。
例：
ABCDEFGHIJK。
后根遍历：
②①。
例：
CEDFBHGJKIA。
遍历森林
森林的结构：
①第一棵树的根，②第一棵树的根的子树森林，③其余树（除第一棵外）组成的森林。
先序遍历：
①②③。
例：
ABCDEFGHIJ。
中序遍历：
②①③。
例：
BDCEAGFIJH。
注：
先序遍历森林，相当于依次先根遍历每一棵树；中根遍历森林相当于后根遍历每一棵树。
遍历树、森林与遍历二叉树的关系
表6.3遍历树、森林和二叉树的关系
树
森林
二叉树
先根遍历
先序遍历
先序遍历
后根遍历
中序遍历
中序遍历
10.赫夫曼树及其应用
最优二叉树（赫夫曼树，哈夫曼树）
树的带权路径长度：
所有叶子结点的带权路径长度之和。
路径长度lk按分支数目计算。
带权路径长度最小的二叉树称为最优二叉树，或赫夫曼树（哈夫曼树）。
构造赫夫曼树
算法：
参见课本P145。
简单说，“每次取两个最小的树组成二叉树”（不准确的说法，只为便于理解和记忆，不要在正式场合引用。
）。
赫夫曼编码（前缀码）
向左分支为0，向右分支为1，从根到叶子的路径构成叶子的前缀编码。
例：
字符及其权值如下：
A（6）,B（7）,C
（1）,D（5）,E
（2）,F（8），构造哈夫曼树和哈夫曼编码，计算带权路径长度。
或采用课本上的算法计算，如下。
表6.4赫夫曼算法
weight
parent
lchild
rchild
weight
parent
lchild
rchild
1
A
6
0
0
0
1
A
6
9
0
0
2
B
7
0
0
0
2
B
7
9
0
0
3
C
1
0
0
0
3
C
1
7
0
0
4
D
5
0
0
0
4
D
5
8
0
0
5
E
2
0
0
0
5
E
2
7
0
0
6
F
8
0
0
0
6
F
8
10
0
0
7
0
0
0
0
7
3
8
3
5
8
0
0
0
0
8
8
10
4
7
9
0
0
0
0
9
13
11
1
2
10
0
0
0
0
10
16
11
6
8
11
0
0
0
0
11
29
0
9
10
结果同上。
说明：
同样的一组权值可能构造出不同的哈夫曼树，结果不一定唯一，但带权路径长度都是最小的。
技巧：
要使前一种方法构造出的赫夫曼树和课本上算法产生的一样，只要把每次合并产生的二叉树放在树的集合的末尾，并且总是用两个最小树的前者作为左子树后者作为右子树。
二、习题
一定义及性质
1、设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为（D）
A．5B．6C．7D．8
5.在下述结论中，正确的是（D）【南京理工大学1999一、4（1分）】
①只有一个结点的二叉树的度为0;②二叉树的度为2；③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。
A．①②③B．②③④C．②④D．①④
16.有关二叉树下列说法正确的是（B）【南京理工大学2000一、11（1.5分）】
A．二叉树的度为2B．一棵二叉树的度可以小于2
C．二叉树中至少有一个结点的度为2D．二叉树中任何一个结点的度都为2
17．二叉树的第I层上最多含有结点数为（C）
A．2IB．2I-1-1C．2I-1D．2I-1
19．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有（B）结点
A．2hB．2h-1C．2h+1D．h+1
24．高度为K的二叉树最大的结点数为（C）。
A．2kB．2k-1C．2k-1D．2k-1-1
二叉树由_
（1）__，__
（2）_，_（3）__三个基本单元组成。
1.
（1）根结点
（2）左子树（3）右子树
具有256个结点的完全二叉树的深度为______。
9
深度为H的完全二叉树至少有_
（1）__个结点；至多有_
（2）__个结点；H和结点总数N之间的关系是（3）__。
（1）2H-1
（2）2H-1（3）H=log2N+1
22．完全二叉树中，若一个结点没有左孩子，则它必是树叶。
√
二二叉树存储
在下列存储形式中，哪一个不是树的存储形式？
（D）A．双亲表示法B．孩子链表表示法C．孩子兄弟表示法D．顺序存储表示法
二叉树只能用二叉链表表示。
×
用链表（llink-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n-1个空指针。
×。
应为n+1个
三二叉树遍历
2．算术表达式a+b*（c+d/e）转为后缀表达式后为（B）
A．ab+cde/*B．abcde/+*+C．abcde/*++D．abcde*/++
30．若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（）遍历方法最合适。
C
A．前序B．中序C．后序D．按层次
33．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（A）。
A．CBEFDAB．FEDCBAC．CBEDFAD．不定
34．已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历是（D）。
A．acbedB．decabC．deabcD．cedba
15.用一维数组存储二叉树时，总是以前序遍历顺序存储结点。
×
21．由一棵二叉树的前序序列和后序序列可以唯一确定它。
×。
必须知道中序
39.某二叉树T有n个结点，设按某种顺序对T中的每个结点进行编号，编号为1，2，…，n，且有如下性质：
T中任一结点V，其编号等于左子树上的最小编号减1，而V的右子树的结点中，其最小编号等于V左子树上结点的最大编号加1。
这时是按（B）编号的。
A.中序遍历序列B.前序遍历序列C.后序遍历序列D.层次顺序
对于前序遍历与中序遍历结果相同的二叉树为
（1）;F
对于前序遍历和后序遍历结果相同的二叉树为
（2）。
B
A．一般二叉树B．只有根结点的二叉树C．根结点无左孩子的二叉树
D．根结点无右孩子的二叉树E．所有结点只有左子数的二叉树F．所有结点只有右子树的二叉树
四线索化
52．n个结点的线索二叉树上含有的线索数为（C）
A．2nB．n－lC．n＋lD．n
18.后序线索二叉树是不完善的，要对它进行遍历，还需要使用栈。
√
47.一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是：
（D）
A．不确定B.0C.1D.2
49.若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为（C）
A.X的双亲B.X的右子树中最左的结点C.X的左子树中最右结点D.X的左子树中最右叶结点
50.引入二叉线索树的目的是（A）
A．加快查找结点的前驱或后继的速度B．为了能在二叉树中方便的进行插入与删除
C．为了能方便的找到双亲D．使二叉树的遍历结果唯一
51.线索二叉树是一种（C）结构。
A．逻辑B．逻辑和存储C．物理D．线性
54．二叉树在线索后，仍不能有效求解的问题是（D）。
A．前（先）序线索二叉树中求前（先）序后继B．中序线索二叉树中求中序后继
C．中序线索二叉树中求中序前驱D．后序线索二叉树中求后序后继
五哈弗曼树
13.设给定权值总数有n个，其哈夫曼树的结点总数为（D）
A．不确定B．2nC．2n+1D．2n-1
62．下述编码中哪一个不是前缀码（B）。
A．（00，01，10，11）B．（0，1，00，11）C．（0，10，110，111）D．（1，01，000，001）
树与二叉树转换
27.利用二叉链表存储树，则根结点的右指针是（C）。
【青岛大学2001五、5（2分）】
A．指向最左孩子B．指向最右孩子C．空D．非空
38．将一棵树t转换为孩子—兄弟链表表示的二叉树h，则t的后根序遍历是h的
A．前序遍历B．中序遍历C．后序遍历（B）
55.设F是一个森林，B是由F变换得的二叉树。
若F中有n个非终端结点，则B中右指针域为空的结点有（C）个。
A．n-1B．nC．n+1D．n+2
56．如果T2是由有序树T转换而来的二叉树，那么T中结点的后序就是T2中结点的（B）。
A．先序B．中序C．后序D．层次序
六综合
1．从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。
1．树的孩子兄弟链表表示法和二叉树二叉链表表示法，本质是一样的，只是解释不同，也就是说树（树是森林的特例，即森林中只有一棵树的特殊情况）可用二叉树唯一表示，并可使用二叉树的一些算法去解决树和森林中的问题。
树和二叉树的区别有三：
一是二叉树的度至多为2，树无此限制；二是二叉树有左右子树之分，即使在只有一个分枝的情况下，也必须指出是左子树还是右子树，树无此限制；三是二叉树允许为空，树一般不允许为空（个别书上允许为空）。
71．设二叉树BT的存储结构如下:
12345678910
Lchild
0
0
2
3
7
5
8
0
10
1
Data
J
H
F
D
B
A
C
E
G
I
Rchild
0
0
0
9
4
0
0
0
0
0
其中BT为树根结点的指针，其值为6,Lchild,Rchild分别为结点的左、右孩子指针域,data为结点的数据域。
试完成
升级会员 