数据结构复习指导6Word文档下载推荐.docx
《数据结构复习指导6Word文档下载推荐.docx》由会员分享,可在线阅读,更多相关《数据结构复习指导6Word文档下载推荐.docx(22页珍藏版)》请在冰点文库上搜索。
链式存储结构
二叉链表:
typedefstructBTNode{
ElemTypedata;
structBTNode*lchild,*rchild;
}BTNode,*BinTree;
三叉链表:
structBTNode*lchild,*rchild,*parent;
用二叉链表存储n个结点的二叉树(n>
0),共有(n+1)个空指针域;
采用三叉链表存储,共有(n+2)个空指针域。
5.二叉树的五种基本形态
①空树:
bt==NULL②左右子树均空:
bt->
lchild==NULLandbt->
rchild==NULL
③右子树为空:
rchild==NULL④左子树为空:
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);
rchild);
}
}
中序遍历算法
voidInorder(BinTreebt)
Inorder(bt->
后序遍历
voidPostorder(BinTreebt)
Postorder(bt->
非递归遍历二叉树
一般借助栈实现。
设想一指针沿二叉树中序顺序移动,每当向上层移动时就要出栈。
(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);
//中序访问结点的位置
rchild;
(b)先序非递归遍历
按照中序遍历的顺序,将访问结点的位置放在第一次指向该结点时。
voidPreorder(BinTreebt,VisitFuncvisit)
//先序访问结点的位置
或者,由于访问过的结点便可以弃之不用,只要能访问其左右子树即可,写出如下算法。
Push(S,bt);
while(!
Push(S,p->
//先进栈,后访问,所以
//这里先让右子树进栈
(c)后序非递归遍历
后序遍历时,分别从左子树和右子树共两次返回根结点,只有从右子树返回时才访问根结点,所以增加一个栈标记到达结点的次序。
voidPostOrder(BinTreebt,VisitFuncvisit)
InitStack(S),InitStack(tag);
Push(S,p),Push(tag,1);
//第一次入栈
Pop(S,p),Pop(tag,f);
if(f==1){
//从左子树返回,二次入栈,然后p转右子树
Push(S,p),Push(tag,2);
//从右子树返回(二次出栈),访问根结点,p转上层
p=NULL;
//必须的,使下一步继续退栈
注:
后序非递归遍历的过程中,栈中保留的是当前结点的所有祖先。
这是和先序及中序遍历不同的。
在某些和祖先有关的算法中,此算法很有价值。
7.遍历二叉树的应用
写出遍历序列(前、中、后序)
根据遍历序列画出二叉树
(a)已知前序和中序序列,唯一确定二叉树。
前序:
ABDEGCFH,中序:
DBGEAFHC,画出二叉树。
前序序列的第一个是根,这是解题的突破口。
步骤:
①前序序列的第一个是根②在中序序列中标出根,分成左右子树③在前序序列中标出左右子树(根据结点个数即可)④分别对左右子树的前序和中序序列重复以上步骤直至完成。
(b)已知后序和中序序列,唯一确定二叉树。
后序:
DGEBHFCA,中序:
后序序列的最后一个是根,这是解题的突破口。
①后序序列的最后一个是根②在中序序列中标出根,分成左右子树③在后序序列中标出左右子树(根据结点个数即可)④分别对左右子树的后序和中序序列重复以上步骤直至完成。
(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);
求二叉树叶子结点的个数。
③L;
④R;
⑤L+R。
③④⑤可合并成⑤。
intLeafCount(BinTreebt)
elseif(bt->
lchild==0andbt->
rchild==0)return1;
elsereturnLeafCount(bt->
lchild)+LeafCount(bt->
求二叉树的深度。
③1+L;
⑤1+max(L,R)。
②③④⑤可合并成⑤。
intDepth(BinTreebt)
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
1
A
6
9
2
B
7
3
C
4
D
5
8
E
F
10
13
11
16
29
结果同上。
同样的一组权值可能构造出不同的哈夫曼树,结果不一定唯一,但带权路径长度都是最小的。
技巧:
要使前一种方法构造出的赫夫曼树和课本上算法产生的一样,只要把每次合并产生的二叉树放在树的集合的末尾,并且总是用两个最小树的前者作为左子树后者作为右子树。
二、习题
一定义及性质
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个结点的完全二叉树的深度为______。
深度为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);
对于前序遍历和后序遍历结果相同的二叉树为
(2)。
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
2
3
7
5
8
10
1
Data
J
H
F
D
B
A
E
G
I
Rchild
9
4
0
其中BT为树根结点的指针,其值为6,Lchild,Rchild分别为结点的左、右孩子指针域,data为结点的数据域。
试完成