当前位置：文档之家 › 第6章 树1

第6章 树1

  • 格式：ppt
  • 大小：471.50 KB
  • 文档页数：83

下载文档原格式

  / 83

合集下载

第六章 树

第六章 树

第六章树一、选择题1．对于一棵具有n个结点的树，该树中所有结点的度数之和为________。

A． n-1 B. n C. n+1 D. (n+1)/22．设结点A 有3个兄弟结点且结点B为结点A的双亲结点，则结点B 的度数为________。

A． 3 B. 4 C.5 D. 13．根据二叉树的定义可知二叉树共有________种不同的形态。

A． 4 B. 5 C. 6 D. 74．在一棵树中，________没有前驱结点。

A. 分支结点B. 叶结点C. 树根结点D. 空结点5．设某棵二叉树中只有度数为0和度数为2的结点,且度数为0的结点数为 n，则这棵二叉中共有________个结点。

A． 2n B.n+1 C. 2n-1 D.2n+16．设某棵二叉树的高度为10，则该二叉树上叶子结点最多有________。

A． 20 B.256 C. 512 D.10247.一棵具有5层满二叉树中结点总数为________。

A． 31 B. 32 C.33 D.168. 如下图所示的4 棵二叉树，_______不是完全二叉树。

9.具有65个结点的完全二叉树的高度为________。

(根的层次号为1)A.8B.7C.6D.510.把一棵深度4的左单支二叉树改造成完全二叉树时，要增添个空结点。

A．10 B．8 C．6 D．411.设按照从上到下、从左到右的顺序从 1 开始对完全二叉树进行顺序编号，则编号为 i结点的左孩子结点的编号为________。

A． 2i+1 B. 2i C. i/2 D. 2i-112.首先访问结点的左子树，然后访问该结点，最后访问结点的右子树，这种遍历称为________。

A.前序遍历B.后序遍历C.中序遍历D.层次遍历13.已知一棵二叉树的前序遍历结果为 ABCDEF ，中序遍历结果为 CBAEDF，则后序遍历的结果为________。

A．CBEFDA B. FEDCBA C. CBEDFA D. 不定14.已知某二叉树的后序遍历序列是 dabec, 中序遍历序列是 debac,它的前序遍历序列是________。

数据结构-第6章 树和二叉树---4. 树和森林(V1)

数据结构-第6章 树和二叉树---4. 树和森林(V1)
ElemType data ; struct CSnode *firstchild, *nextsibing ; }CSNode;
6.4.1 树的存储结构
R AB C D EG F
R⋀
A
⋀D
⋀B
⋀E ⋀
C⋀
⋀G
⋀F ⋀
6.4.2 树、森林和二叉树的转换
1. 树转换为二叉树 将树转换成二叉树在“孩子兄弟表示法”中已 给出，其详细步骤是： ⑴ 加线。在树的所有相邻兄弟结点之间加一 条连线。 ⑵ 去连线。除最左的第一个子结点外，父结点 与所有其它子结点的连线都去掉。 ⑶ 旋转。将树以根结点为轴心，顺时针旋转 450，使之层次分明。
B C
D
A E
L HK
M
技巧：无左孩子 者即为叶子结点
6.4.3 树和森林的遍历
1. 树的遍历 由树结构的定义可知，树的遍历有二种方法。 ⑴ 先序遍历：先访问根结点，然后依次先序 遍历完每棵子树等。价于对应二叉树的先序遍历
⑵ 后序遍历：先依次后序遍历完每棵子树，然 后访问根结点。等价于对应二叉树的中序遍历
0 R -1 1A 0 2B 0 3C 0
}Ptree ; R
4D 1 5E 1
AB C
6F 3
7G 6
DE
F
8H 6
9I 6
G H I 10~MAX_Size-1 ... ...
6.4.1 树的存储结构
2. 孩子表示法
每个结点的孩子结点构成一个单链表，即有n 个结点就有n个孩子链表；
n个孩子的数据和n个孩子链表的头指针组成一 个顺序表； 结点结构定义： 顺序表定义：
typedef struct PTNode { ElemType data ;

第6章树和二叉树

第6章树和二叉树
2.孩子表示法 孩子表示法 在结点中设置指向每个孩子的指针域， 在结点中设置指向每个孩子的指针域，利用指针 指向该结点的所有孩子结点。 指向该结点的所有孩子结点。 大多采用按树的度设置结点的指针域的个数。 大多采用按树的度设置结点的指针域的个数。
9
6.1.4 树的存储结构
3.孩子兄弟表示法 孩子兄弟表示法 在结点中设置两个指针域， 在结点中设置两个指针域，一个指针域指向该结 点的第一个孩子，另一个指针域指向其右兄弟。 点的第一个孩子，另一个指针域指向其右兄弟。
2
6.1.1树的定义 树的定义
结点的度：结点所拥有子树的个数称为结点的度。 结点的度：结点所拥有子树的个数称为结点的度。 子树 称为结点的度 树的度：树中所有结点的度的最大值称为树的度。 最大值称为树的度 树的度：树中所有结点的度的最大值称为树的度。 叶结点：度为零的结点称为叶结点。也称终端结点 终端结点或 叶结点：度为零的结点称为叶结点。也称终端结点或叶 子 分支结点：度不为零的结点称为分支结点。也称非终端 分支结点：度不为零的结点称为分支结点。也称非终端 结点。除根结点以外，分支结点也称为内部结点。 结点。除根结点以外，分支结点也称为内部结点。 孩子结点和双亲结点： 孩子结点和双亲结点：树中一个结点的子树的根结点称 为孩子结点。该结点就称为孩子结点的双亲结点。 为孩子结点。该结点就称为孩子结点的双亲结点。 兄弟结点：具有同一双亲的孩子结点互为兄弟结点。 兄弟结点：具有同一双亲的孩子结点互为兄弟结点。 结点的祖先：从根到该结点所经分支上的所有结点， 结点的祖先：从根到该结点所经分支上的所有结点，称 为结点的祖先。 为结点的祖先。
17
6.2.2 二叉树的性质
性质4 具有n（ 性质 具有 （n>0）个结点的完全二叉树的深度 ）个结点的完全二叉树的深度h= log 2 n + 1 证明： 证明： 根据完全二叉树的定义可知深度为h-1层及以上的结点构成 根据完全二叉树的定义可知深度为 层及以上的结点构成 满二叉树，因此由性质2得深度为 得深度为h的完全二叉树满足 满二叉树，因此由性质 得深度为 的完全二叉树满足 n>2h-1-1和n≤2h-1 和 整理后得到 2h-1≤n<2h 不等式两边取对数， 不等式两边取对数，得 h-1≤log2n<h 由于h为正整数 为正整数， 由于 为正整数，因此 h= log 2 n + 1

第六章树 作业讲解

第六章树 作业讲解

6-10 插入最右子结点
template<class T> int Tree<T> :: InsertChild（T value） { if（current = = NULL） return 0; if（current→firstChild == NULL） { current→firstChild=new TreeNode<T>(value,NULL,NULL); return 1 ;} else { TreeNode<T> *temp= current→firstChild; while(temp→nextBrother!=NULL) temp= temp→nextBrother; temp→nextBrother=new TreeNode<T>(value,NULL,NULL); return 1 ; }
6-13 后根遍历树——非递归算法
6-13 后根遍历树——递归算法
template<class T> void Tree<T> :: PostOrder（） { if（! IsEmpty（）） { TreeNode<T> *p = current ; // 保存当前结点 int k = FirstChild（）; while（k）// 后根遍历当前结点的诸子树 { PostOrder（）; k = NextBrother（）; } current = p ; // 恢复当前指针 visit（）; // 访问当前结点 } }
6-11 删除子结点
int k=1; while(temp→nextBrother!=NULL && k<i) { pred=temp; temp=temp→nextBrother; k++;} if(k = =i) { pred→nextBrother= temp→nextBrother; DelSubtree(temp); return 1;} else return 0; }

第六章 树基础知识)

第六章 树基础知识)

第六章树（基础知识）选择题部分1.在线索化二叉树中,t所指结点没有左子树的充要条件是（）答案（A）t-〉left==NULL （B）t-〉ltag==1（C）t-〉ltag=1且t-〉left=NULL （D）.以上都不对2.二叉树按某种顺序线索化后,任一结点均有指向其前趋和后继的线索,这种说法答案（A）正确（B）错误3.二叉树的前序遍历序列中,任意一个结点均处在其子女结点的前面,这种说法（）答案(A)正确(B)错误4.由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树,这种说法答案（A）正确（B）错误5.设高度为h的二叉树上只有度为0和度为2的结点,则此类二叉树中所包含的结点数至少为（）。

答案（A）2h （B）2h-1（C）2h+1（D）h+16.已知某二叉树的后序遍历序列是dabec。

中序遍历序列是debac,它的前序遍历序列是（）。

答案（A）acbed （B）decab（C）deabc （D）cedba7.如果T2是由有序树T转换而来的二叉树,那么T中结点的前序就是T2中结点的（）答案（A）前序（B）中序（C）后序D.层次序8.某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是（）。

答案（A）bdgcefha （B）gdbecfha （C）bdgaechf （D）gdbehfca9.二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。

这种说法（）答案（A）正确（B）错误10.按照二叉树的定义,具有3个结点的二叉树有（）种。

答案（A）3（B）4（C）5（D）611.在一非空二叉树的中序遍历序列中,根结点的右边（）答案（A）只有右子树上的所有结点（B）只有右子树上的部分结点（C）只有左子树上的部分结点（D）只有左子树上的所有结点12.树最适合用来表示（）。

答案（A）有序数据元素（B）无序数据元素（C）元素之间具有分支层次关系的数据（D）元素之间无联系的数据13.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）答案（A）不发生改变（B）发生改变（C）不能确定D.以上都不对14.实现任意二叉树的后序遍历的非递归算法而不使用栈结构,最佳方案是二叉树采用（）存储结构。

测树学—第6章 角规测树

测树学—第6章 角规测树

各径阶林木株数(Nj)之和即为林分每公顷 林木株数N，则 k 1
N = Fg ∑
j=1
gj
Zj
用角规测算每公顷林木株数计算表(Fg=1)
计数木 号 1 2 3 4 5 6 7 8 9 合计 胸径 (cm) 12.8 17.3 20.2 19.5 20.7 18.9 19.3 16.6 15.3
1 gj
77.70 42.54 31.20 33.49 29.72 35.64 34.18 46.21 54.38 385.06
径阶
1 gj
Zj
各径阶株数 N j = Fg
Zj gj
12 16 18 20
88.42 49.73 39.29 31.83
1 2 2 4
88.42 99.46 78.58 127.32
学期望为0的随机误差，Fg越大，误差越大。
由G＝Fg×Z可知，当Fg=0.5，1，2，4时， 角规仪器误差分别为：± 0.5m2 ， ± 1m2 ， ± 2m2 ， ± 4m2 。
二、断面积系数的选定
2. 由于Fg选择不当，使扩大样园半径过大 而产生的观测误差 观测误差。 观测误差 50 D R= 以林分Dg＝20cm为例： Fg
例如：某林分中Dmax=40cm，若取=1，则角 规点到林缘的距离(S)应大于20m(即 S≥R)。若取 ＝4，则距离应大于l0m。
（2）长方形林地，可进行绕测其半园或1/4 长方形林地，可进行绕测其半园或 长方形林地 园，再将绕测结果加倍或乘以4得林地绕测 结果。
五、角规控制检尺
• 角规控制检尺 角规控制检尺:在角规样点上，对绕测计数的树木量 测其胸径，并按径阶统计株数的工作。 50
这种原理是以测点为中心，对每株树作一圆形 样地（样圆）。样圆的面积取决于D的大小，因此 样地的面积是可变地，故称不等概抽样。 1）假设林内所有林木地胸径相等为 Dj，如图 设P2为临界树（相切），则用角规绕测时，形成以 Rj为半径，O为中心的假想扩大圆 令角规尺长为L，缺口宽为l， L 则: Rj = • Dj l 2 样圆面积： L 2 2

图论 第6章 树和割集

图论 第6章 树和割集
推论1 任一非平凡树中至少有两个度为1的顶点。 推论2 任一非平凡树都是偶图。 推论3 任一非平凡树都是2-色的。
1.3 极小连通图
定义2 若连通图G中去掉任一条边后得到一个不连通图，则称G 为极小连通图。 推论4 图G是树当且仅当G是极小连通图。
1.4 树的中心
定义3 设G=(V，E)是连通图，v∈V，数 e(v)=max{d(v,u)} 称为v在G中的偏心率。 数 r(G)=min{e(v)} 称为G的半径。 满足r(G)=e(v)的顶点v称为G的中心点。G的所有中心点组成 的集合称为G的中心，G的中心记为C(G)。 定理2 每棵树的中心或含有一个顶点，或含有两个邻接的顶点。
（2）∑deg v=2q
（3）根据具体的题设条件进行特殊的不等式的放缩[解题关键] 例3 设G是一棵树且Δ(G)≥k，证明：G中至少有k个1度顶点。
1.7 生成树（包含所有顶点的树）
定义1 设G=(V,E)是一个图，若G的一个生成子图 T=(V,F)是树，则称T是G的生成树。 定义2 设G=(V，E)是一个图，若G的一个生成子图 T=(V，F)是一个森林，则称T是G的生成森林。
1.8 生成树存在问题
定理1 图G有生成树的充分必要条件是G为一个连通图。
3极小连通图定义2若连通图g中去掉任一条边后得到一个不连通图则称g为极小连通图
第六章
树和割集
内容
树及其性质、生成树、割集
第一节
1.1 树和森林向树，简称树， 记为T。 定义2 无圈的无向图称为无向森林，简称森林。
1.2 树的特征性质
定理1 设G=(V,E)是一个(p,q)图，则下列命题等价： (1) G是树； (2) G的任两个不同顶点间有唯一的一条路联结； (3) G连通且 p=q+1； (4) G无圈且 p=q+1； (5) G无圈且任加一条边得到有唯一圈； (6) G连通且任去掉一条边得不连通图。

数据结构练习_第六章_树

数据结构练习_第六章_树

数据结构练习第六章树一、选择题1.树最适合用来表示( )。

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据2.二叉树的第k层的结点数最多为( ).A．2k-1 B.2K+1 C.2K-1 D. 2k-13.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。

A. 2m-1B. 2mC. 2m+1D. 4m4．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）。

A. BADCB. BCDAC. CDABD. CBDA5.设某棵二叉树中有2000个结点，则该二叉树的最小高度为（）。

A. 9B. 10C. 11D. 126．设一棵二叉树的深度为k，则该二叉树中最多有（）个结点。

A. 2k-1 B .2k C. 2k-1 D. 2k-17．设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（）。

A. N0=N1+1 B. N=Nl+N2C. N=N2+1 D. N=2N1+l8．设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，……，度数为m的结点数为Nm，则N=（）。

A. Nl +N2+……+Nm B. l+N2+2N3+3N4+……+(m-1)NmC. N2+2N3+3N4+……+(m-1)Nm D. 2Nl+3N2+……+(m+1)Nm9．设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为（）。

A. 20B. 30C. 40D. 4510．设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（）。

A. 空或只有一个结点B. 高度等于其结点数C. 任一结点无左孩子D. 任一结点无右孩子11．设某棵三叉树中有40个结点，则该三叉树的最小高度为（）。

A. 3B. 4C. 5D. 612．深度为k的完全二叉树中最少有（）个结点。

哈工大集合论习题课-第六章 树及割集 习题课(学生)

哈工大集合论习题课-第六章 树及割集 习题课(学生)

第六章 树及割集习题课1课堂例题例1 设T 是一棵树，T 有3个度为3顶点，1个2度顶点，其余均是1度顶点。

则（1）求T 有几个1度顶点？（2）画出满足上述要求的不同构的两棵树。

分析：对于任一棵树T ，其顶点数p 和边数q 的关系是：1q p =-且1deg()2ipi v q ==∑，根据这些性质容易求解。

解：（1）设该树T 的顶点数为p ，边数为q ，并设树T 中有x 个1度顶点。

于是1deg()33122ipi v x q ==⨯+⨯+=∑且31p x =++，1q p =-，得5x =。

（2）满足上述要求的两棵不同构的无向树，如图1所示。

图1例2设G 是一棵树且()G k ∆≥，证明G 中至少有k 个度为1顶点。

证：设T 中有p 个顶点，s 个树叶，则T 中其余p s -个顶点的度数均大于等于2，且至少有一个顶点的度大于等于k 。

由握手定理可得：1222()2(1)pi i q p deg v p s k s ==-=≥--++∑，有s k ≥。

所以T 中至少有k 个树叶 。

习题例1 若无向图G 中有p 个顶点，1p -条边，则G 为树。

这个命题正确吗？为什么？解：不正确。

3K 与平凡图构成的非连通图中有四个顶点三条边，显然它不是树。

例2设树T 中有2n 个度为1的顶点，有3n 个度为2的顶点，有n 个度为3的顶点，则这棵树有多少个顶点和多少条边？解：设T 有p 个顶点，q 条边，则123161q p n n n n =-=++-=-。

由deg()2v Vv q ∈=∑有：1223322(61)122n n n q n n ⨯+⨯+⨯==-=-，解得：n =2。

故11,12q p ==。

例3证明恰有两个顶点度数为1的树必为一条通路。

证：设T 是一棵具有两个顶点度数为1的(,)p q 树，则1q p =-且1deg()2pii v q ==∑2(1)p =-。

又T 除两个顶点度数为1外，其他顶点度均大于等于2，故211deg()2deg()2(1)p p iii i v v p -===+=-∑∑，即21deg()2(2)p ii v p -==-∑。

数据结构第六章：树和二叉树

数据结构第六章：树和二叉树

性质2：深度为 的二叉树至多有 个结点(k≥ 性质 ：深度为k的二叉树至多有2 k 1 个结点 ≥1)
证明：由性质 ，可得深度为k 证明：由性质1，可得深度为 的二叉树最大结点数是
(第i层的最大结点数 ) = ∑ 2 i 1 = 2 k 1 ∑
i =1 i =1
k
k
10
性质3：对任何一棵二叉树 ，如果其终端结点数(即 性质 ：对任何一棵二叉树T，如果其终端结点数 即 叶节点)为 度为2的结点数为 的结点数为n 叶节点 为n0，度为 的结点数为 2，则n0=n2+1 证明： 为二叉树 中度为1的结点数 为二叉树T中度为 证明：n1为二叉树 中度为 的结点数 因为：二叉树中所有结点的度均小于或等于2 因为：二叉树中所有结点的度均小于或等于 所以：其结点总数n=n0+n1+n2 所以：其结点总数 又二叉树中，除根结点外， 又二叉树中，除根结点外，其余结点都只有一个 分支进入； 分支进入； 为分支总数， 设B为分支总数，则n=B+1 为分支总数 又：分支由度为1和度为 的结点射出，∴B=n1+2n2 分支由度为 和度为2的结点射出， 和度为 的结点射出 于是， 于是，n=B+1=n1+2n2+1=n0+n1+n2 ∴n0=n2+1
7
结点A的度：3 结点 的度： 的度 结点B的度：2 结点 的度： 的度 结点M的度：0 结点 的度： 的度 结点A的孩子： ， ， 结点 的孩子：B，C，D 的孩子 结点B的孩子 的孩子： ， 结点 的孩子：E，F 树的度： 树的度：3 E K 结点A的层次： 结点 的层次：1 的层次 结点M的层次 的层次： 结点 的层次：4 L B F A C G H M

数据结构第6章树习题

数据结构第6章树习题

第六章树习题1单项选择题1、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则叶子结点个数是（B）。

A、9B、11C、15D、无法确定2、设给定权值总数有n个，其哈夫曼树的结点总数为( D )。

A、不确定B、2nC、2n+1D、2n–13、有关二叉树下列说法正确的是（B）。

A、二叉树的度为2B、一棵二叉树的度可以小于2C、二叉树中至少有一个结点的度为2D、二叉树中任何一个结点的度都为24、一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点。

A、2hB、2h-1C、2h+1D、h+15、对于有n个结点的二叉树, 其高度为（）。

log D、不确定A、n log2nB、log2nC、⎣⎦n26、利用二叉链表存储树，则根结点的右指针是（）。

A、指向最左孩子B、指向最右孩子C、空D、非空7、树的后根遍历序列等同于该树对应的二叉树的( )。

A、先序遍历B、中序遍历C、后序遍历D、层序遍历8、在下列存储形式中，哪一个不是树的存储形式？（）A、双亲表示法B、孩子链表表示法C、孩子兄弟表示法D、顺序存储表示法9、已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（）。

A、CBEFDAB、FEDCBAC、CBEDFAD、不定10、某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。

A、空的或只有一个结点B、任一结点无左子树C、高度等于其结点数D、任一结点无右子树11、一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是：( )。

A、不确定B、0C、1D、212、若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为( )。

A、X的双亲B、X的右子树中最左的结点C、X的左子树中最右结点D、X的左子树中最右叶结点13、引入二叉线索树的目的是（）.A、加快查找结点的前驱或后继的速度B、为了能在二叉树中方便的进行插入和删除C、为了能方便的找到双亲D、使二叉树的遍历结果唯一14、下述编码中哪一个不是前缀码（）。

严蔚敏《数据结构》教学笔记第六章 树和二叉树

严蔚敏《数据结构》教学笔记第六章 树和二叉树

来自
转载请注明
严蔚敏数据结构教学笔记
CountLeaf( T->rchild, count); // 统计右子树中叶子结点个数 } }
2、求二叉树的深度(后序遍历) int Depth (BiTree T ) { if ( !T ) depthval = 0; else { depthLeft = Depth( T->lchild ); depthRight= Depth( T->rchild ); depthval = 1 + (depthLeft> depthRight?depthLeft:depthRight); } return depthval; }
五、遍历算法的应用举例: 1、统计二叉树中叶子结点的个数(先序遍历) void CountLeaf (BiTree T, int& count) { if ( T ) { if ((!T->lchild)&& (!T->rchild)) count++; CountLeaf( T->lchild, count); // 统计左子树中叶子结点个数 9
LeftChild(T, cur_e); RightSibling(T, cur_e);
TreeEmpty(T); TreeDepth(T);
TraverseTree(T, Visit()); 插入： InitTree(&T); CreateTree(&T, definition);
Assign(T, cur_e, value); InsertChild(&T, &p, i, c); 1
3、复制二叉树(后序遍历) // 生成一个二叉树的结点 BiTNode *GetTreeNode(TElemType item, BiTNode *lptr , BiTNode *rptr ){ if (!(T = (BiTNode*)malloc(sizeof(BiTNode)))) 10

数据结构第6章 树习题+答案

数据结构第6章 树习题+答案

第六章 树和二叉树一、选择题1．已知一算术表达式的中缀形式为 A+B*C-D/E ，后缀形式为ABC*+DE/-，其前缀形式为( D )A ．-A+B*C/DE B. -A+B*CD/E C ．2. 设有一表示算术表达式的二叉树（见下图）， 它所表示的算术表达式是（ C ） A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (A*B+C)/(D*E+（F-G ）) D. A*B+C/D*E+F-G 3. 在下述结论中，正确的是（ D ）①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换;④深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。

A ．①②③B ．②③④C ．②④D ．①④4. 设森林F 对应的二叉树为B ，它有m 个结点，B 的根为p,p 的右子树结点个数为n,森林F 中第一棵树的结点个数是（ A ）A ．m-nB ．m-n-1C ．n+1D ．条件不足，无法确定5．设森林F 中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。

与森林F 对应的二叉树根结点的右子树上的结点个数是（ D ）。

A ．M1B ．M1+M2C ．M3D ．M2+M36. 设给定权值总数有n 个，其哈夫曼树的结点总数为( D )A ．不确定B ．2nC ．2n+1D ．2n-17．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( B )结点A ．2hB ．2h-1C ．2h+1D ．h+18. 一棵具有 n 个结点的完全二叉树的树高度（深度）是（ A ）A ．⎣logn ⎦+1B ．logn+1C ．⎣logn ⎦D ．logn-19．深度为h 的满m 叉树的第k 层有（ A ）个结点。

(1=<k=<h)A ．m k-1B ．m k -1C ．m h-1D ．m h -110. 一棵树高为K 的完全二叉树至少有（ C ）个结点A ．2k –1 B. 2k-1 –1 C. 2k-1 D. 2k11. 利用二叉链表存储树，则根结点的右指针是（ C ）。

数据结构 第六章-树

数据结构 第六章-树

20
A B C D
E
F
G H
I J
A
E F H
G
B C
D A
I J
A
B C F
E H
G
B C D F
E G H I J
21
I
D
J
5. 二叉树转换成树和森林
二叉树转换成树 1. 加线：若p结点是双亲结点的左孩子，则将p的右孩 子，右孩子的右孩子，……沿分支找到的所有右孩 子，都与p的双亲用线连起来 2. 抹线：抹掉原二叉树中双亲与右孩子之间的连线 3. 调整：将结点按层次排列，形成树结构7Fra bibliotek6.3.2
树和森林的存储结构
树的存储结构有很多，既可以采用顺序存储结构， 也可以采用链式存储结构。但无论采用哪种存储方式， 都要求存储结构不仅能存储各结点本身的数据信息，还 要能惟一地反映树中各结点之间的逻辑关系。 双亲表示法 孩子链表表示法 孩子兄弟表示法
8
1.双亲表示法 除根外，树中的每个结点都有惟一的一个双亲结点，所以可以用一 组连续的存储空间存储树中的各结点。一个元素表示树中一个结点， 包含树结点本身的信息及结点的双亲结点的位臵。 A B E F C G H D I
}CTBox;
//树结构 typedef struct {CTBox nodes[MAX_TREE_SIZE]; int n, r; }Ctree
12
3. 孩子-兄弟表示法（树的二叉链表）
孩子兄弟表示法用二叉链表作为树的存储结构。将树中的多支关系用 二叉链表的双支关系体现。 ※ 结点的左指针指向它的第一个孩子结点
//孩子结点结构 typedef struct CTNode
1 2 3 4 5 6

第6章-1( 树的基本概念)

第6章-1( 树的基本概念)

10．层数 根结点的层数为1，其它结点的层数为从根结点到该 结点所经过的分支数目再加1。 11. 树的高度（深度） 树中结点所处的最大层数称为树的高度，如空树的 高度为0，只有一个根结点的树高度为1。 12.树的度 树中结点度的最大值称为树的度。
13. 有序树
若一棵树中所有子树从左到右的排序是有顺序的，不 能颠倒次序。称该树为有序树。 14. 无序树
性质3 对任意一棵二叉树，如果叶子结点个数为n0， 度为2的结点个数为n2，则有n0=n2+1。 证明：设二叉树中度为1的结点个数为n1，根据二叉树 的定义可知，该二叉树的结点数n=n0+n1+n2。又因为 在二叉树中，度为0的结点没有孩子，度为1的结点有1 个孩子，度为2的结点有2个结孩子，故该二叉树的孩 子结点数为 n0*0+n1*1+n2*2 ，而一棵二叉树中，除根 结点外所有都为孩子 结点，故该二叉树的结点数应为 孩子结点数加1即：n=n0*0+n1*1+n2*2+1因此,有 n=n0+n1+n2=n0*0+n2*1+n2*2+1，最后得到n0=n2+1。 先定义两种特殊的二叉树:
初始化树T。 (2) root(T) 求树T的根结点。
(3) parent(T,x)
求树T中，值为x的结点的双亲。 (4) child(T,x,i)
求树T中，值为x的结点的第i个孩子。
(5) addchild(y,i,x) 把值为x的结点作为值为y的结点的第i个孩子插入到树 中。 (6) delchild(x,i)
图 6-1 树的示意图
2. 凹入法表示法
具体参见图6-3 。
A B E J K L F C G D H M I 图 6-3 图 6-1(c)的树的凹入法表示
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

满二叉树的定义： 满二叉树的定义： 一棵高度为k的满二叉树， 一棵高度为k的满二叉树，是具有 2k+1－1个结点且高度为k的二叉树。 个结点且高度为k的二叉树。 1 2 4 8 9 10 5 11 6 12 13 3 7 14 15
完全二叉树的定义： 完全二叉树的定义： 是一棵具有n个结点，高度为k的二叉树， 是一棵具有n个结点，高度为k的二叉树， 且树中所有结点对应高度为k的满二叉树中编号 且树中所有结点对应高度为k的满二叉树中编号 对应高度为 的那些结点。 由1至n的那些结点。 1 2 4 8 9 10 5 6 3 7
树的表示 1.集合嵌套表示法 1.集合嵌套表示法 2.凹入表示法 2.凹入表示法 3.广义表表示法 3.广义表表示法 4.树形表示法 4.树形表示法
2 A B C 3 A(B,C(D,E)) D E
1
B
Hale Waihona Puke ADCE
4 B
A C D E
树的基本操作
1、判树空：TREEEMPTY(T) 判树空： 2、求根：ROOT(T) 求根： 3、求树的深度：TREEDEPTH(T) 求树的深度： 4、 求某结点的兄弟: BROTHERS(T) 求某结点的兄弟: 5、求结点的双亲：PARENT(T) 求结点的双亲： 6、求结点的孩子：CHILD(T,e,i) 求结点的孩子： 7、建立树：CREATE_TREE(T, T1 , T2 , … , Tm ) 建立树： 8、遍历树：TRAVERSAL(T) 遍历树：
引理6.2 高度为k的二叉树中至多 引理6.2 高度为k的二叉树中至多有2k+1－1 至多有 (k≧0)个结点。 (k≧0)个结点 个结点。 根据引理 根据引理6.1 引理6.1 层上至多有2 个结点， 第0层上至多有20个结点， 层上至多有2 个结点, 第1层上至多有21个结点, ……， ……， 层上至多有2 个结点, 第k层上至多有2k个结点, 因此，高度为k的二叉树中至多 至多有 因此，高度为k的二叉树中至多有 20＋ 21＋……+ 2k= 2k+1－1 个结点。 个结点。
●
二叉树的五种不同形态
二叉树的性质 引理6.1 二叉树中层数为i的结点至多 至多有 i≧0。 引理6.1 二叉树中层数为i的结点至多有2i个，i≧0。 证明：用数学归纳法。 证明：用数学归纳法。 仅有一个根结点，其层数为0 因此i=0 当 i=0 时，仅有一个根结点，其层数为0，因此i=0 时引理成立。 时引理成立。 (j≥0)时 引理成立， 层上至多有2 假定当 i=j (j≥0)时，引理成立，即第 j 层上至多有2j个 结点。 结点。 对于二叉树的任意结点，其子结点个数最大为2 对于二叉树的任意结点，其子结点个数最大为2，故 j+1层上至多有 个结点， i=j+1时 第j+1层上至多有 2*2j= 2j+1 个结点，因此当 i=j+1时， 引理成立。 引理成立。 由数学归纳法可知，对于所有的i≥0，均有“ 由数学归纳法可知，对于所有的i≥0，均有“第 i 层上 个结点” 至多有 2i 个结点”。 证毕。 证毕。
合作管理结构
树在计算机领域也有广泛的应用， 树在计算机领域也有广泛的应用，如: • • • • 在编译中， 用树来表示源程序的语法结构 在编译中 ， 用树来表示源程序的 语法结构 ； 语法结构； 在数据库系统中，可用树来组织信息 组织信息； 在数据库系统中，可用树来组织信息； 在分析算法时， 可用树来描述其执行过程 执行过程； 在分析算法时 ， 可用树来描述其 执行过程 ； 操作系统中， 文件及文件夹的存储， 操作系统中 ， 文件及文件夹的存储 ， 软件 工程中，软件的菜单等都是树 等都是树。 工程中，软件的菜单等都是树。
树结构在客观世界中大量存在，如家谱、行 树结构在客观世界中大量存在， 家谱、 政组织机构等都可用树形象地表示。 政组织机构等都可用树形象地表示。 等都可用树形象地表示
[合作机构] 合作机构] 在层次中地位最高的人（此处为总裁） 在层次中地位最高的人（此处为总裁）在图 中位置最高。在层次中地位次之的（即副总裁） 中位置最高。在层次中地位次之的（即副总裁） 在图中位于总裁之下等等。副总裁为总裁的下属， 在图中位于总裁之下等等。副总裁为总裁的下属， 总裁是他们的上级。每个副总裁都有自己的下属， 总裁是他们的上级。每个副总裁都有自己的下属， 而其下属又有自己的下属。 而其下属又有自己的下属。
A B E F C I D
层次0 层次 层次1 层次 层次2 层次 层次3 层次
G
H
图6.1 树
与线性结构的比较 线性结构
第一个数据元素 无前驱) (无前驱) 最后一个数据元素 无后继) (无后继)
树结构
根结点 (无前驱 无前驱) (无前驱) 多个叶子结点 (无后继 无后继) (无后继)
其它数据元素 树中其它结点 一个前驱、一个后继) (一个前驱 多个后继) 一个前驱、 (一个前驱、一个后继) (一个前驱、多个后继)
树的特点： 树的特点： ① 有一个总根。 有一个总根。 ② 没有分枝相交。 没有分枝相交。 树有层次。 ③ 树有层次。
基本术语
结点(node) 结点(node) 结点的度(degree) 结点的度(degree) 分支(branch)结点 分支(branch)结点 叶子(leaf)结点 叶子(leaf)结点 孩子(child)结点 孩子(child)结点 双亲(parent)结点 双亲(parent)结点
图6.1为一棵由根结点A出发的树，其中，A有三 6.1为一棵由根结点 出发的树，其中， 为一棵由根结点A 个子结点B 有一个子结点E 个子结点B、C和D；B有一个子结点E；E有一个子 结点F 有两个子结点G 有一个子结点I 结点F；C有两个子结点G和H；D有一个子结点I； F， G，H，I是叶子结点，因为它们没有子结点。 是叶子结点，因为它们没有子结点。 的路径为A 路径长度为3 从A到F的路径为A-B-E-F，路径长度为3。
6.1 6.2 6.3 6.4 6.5
基本概念 二叉树 线索二叉树 树和森林 压缩与哈夫曼树
定义6.1 定义6.1 树（t r e e） e） 树是由唯一的起始结点“根结点” 树是由唯一的起始结点“根结点” 出发的 结点集合，其中， 结点集合，其中，任何非根结点都有且仅有一 个前趋结点，称之为该结点的父结点 父结点； 个前趋结点，称之为该结点的父结点；任何结 点都可能有多个后继结点，称之为该结点的子 点都可能有多个后继结点，称之为该结点的子 结点；若某结点没有后继结点，则称之为叶子 结点；若某结点没有后继结点，则称之为叶子 结点。 结点。 若存在路径v 其中v 若存在路径vm-vm+1-…-vn，其中vi+1是vi的后 继结点，则称v 子孙结点， 继结点，则称vn为vm的子孙结点，称vm为vn的祖 先结点，该路径所经历的边的个数被称为路径 先结点，该路径所经历的边的个数被称为路径 的长度。 的长度。一个结点到它的某个子孙结点有且仅 有一条路径。 有一条路径。
引理6.3 引理6.3 设T是由n个结点构成的二叉树，其 是由n个结点构成的二叉树， 中,叶子结点个数为n0，度为2的结点个数 叶子结点个数为n 度为2 为n2，则有：n0＝ n2＋1 则有： 证明：若设度为1的结点有n 证明：若设度为1的结点有n1个，总结点个 数为n 总边数为e 数为n，总边数为e，则 n = n0 + n1 + n2 e=n–1 (子结点与父结点的连接) 子结点与父结点的连接) e = 2n2 + n1 (所有发出分支的结点) 所有发出分支的结点) 因此， 因此，有 2n2 + n1 = n0 + n1 + n2 - 1 n2 = n0 - 1 n0 = n2 + 1
6.1 6.2 6.3 6.4 6.5
基本概念 二叉树 线索二叉树 树和森林 压缩与哈夫曼树
6.2 二叉树
6.2.1 二叉树的性质和定义 6.2.2 二叉树的实现 6.2.3 二叉树的遍历 6.2.4 遍历二叉树的应用
6.2.1 二叉树的主要性质和定义
●
二叉树的定义：二叉树是结点的有限集合， 二叉树的定义：二叉树是结点的有限集合，它 必须满足下述条件： 必须满足下述条件： 它是空集； （1）它是空集； 它由一个根结点、 （2）它由一个根结点、根结点的左右子 树构成，且其左右子树满足二叉树定义。 树构成，且其左右子树满足二叉树定义。 二叉树的特征 二叉树每个结点最多有2个子结点； （1） 二叉树每个结点最多有2个子结点； 二叉树的子树有左右之分。 （2） 二叉树的子树有左右之分。
用归纳法证明 i=1，如果n≥2，则左孩子的编号显然为2 若i=1，如果n≥2，则左孩子的编号显然为2. 假定对所有满足j≤i的 假定对所有满足j≤i的j，知j的左孩子编号为 2j. 那么对结点i+1，我们证明其左孩子编号为 那么对结点i+1 2(i+1). (i+1 如果2(i+1)≤n， 则由层次次序得知， i+1 如果 2(i+1)≤n ， 则由层次次序得知 ， i+1 的 左孩子之前的两个结点是i的左孩子和右孩子， 左孩子之前的两个结点是i的左孩子和右孩子， 因为i的左孩子编号为2i(归纳假设 归纳假设) 因为i的左孩子编号为2i(归纳假设)，故i的右孩 子编号为2i+1 从而i+1 的左孩子编号为2i+2 子编号为 2i+1 ， 从而 i+1 的左孩子编号为 2i+2= 2(i+1). (i+1
（A） ） B （B） ） G （C） ） C
G E
H
F
图6.2 子树
定义6.2 定义6.2 从根结点到某个结点的路径长度被称为 结点的层数 树的高度是指树中结点的最 层数。 结点的层数。树的高度是指树中结点的最 大层数。 大层数。 对于根结点的层数，目前有两种规定， 对于根结点的层数，目前有两种规定， 一种规定根结点的层数为0 一种规定根结点的层数为0，另一种规定根 结点的层数为1 本书采纳前者。 结点的层数为1，本书采纳前者。 非根结点的层数 = 其父结点的层数 + 1