第六章 树和二叉树
第一次作业
6.1试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。
分析：一棵度为2的有序树与一棵二叉树的区别是：度为2的树有二个分支，没有左右
之分；一棵二叉树也有两个分支，但有左右之分，且左右不能交换.
3个结点树形态：
3个结点的二叉树：
6.4 一个深度为
H的满k叉树有如下性质：第H层上的结点都是叶子结点，其
余各层上每个结点都有k棵非空子树。如果按层次顺序（同层自左至右）从未有
过开始对全部结点编号，问：
（1） 各层的结点数目是多少？
（2
） 编号为i的结点的双亲结点（若存在）的编号是多少？
（3） 编号为
i的结点的第j个孩子结点（若存在）的编号是多少？
（4） 编号为i
的结点有右兄弟的条件是什么？其右兄弟的编号是多少？
解：
（1） Ki-1
（2） i =1时，该节点为根，无父节点；
A
B C A
C B
A
B
C A
B
C A
C B 否则其父节点编号为(2)ik
k （k2）
分析：编号为p的孩子结点的范围[（p-1）*k+2, p*k+1] 得出(i-1)/kp(i-2)/k+1
（3） K*i+j+1-k
（4）(i-1)MOD K<>0,该结点有右兄弟,其右兄弟的编号是i+1
6.5 已知一棵度为k的树中有1n个度为1的结点，2n个度为2的结点，…，kn
个度为k的结点，问该树中有多少个叶子结点?
解:
k
1ii0n)1i(1n
分析：
结点总数：n=n0+n1+n2+……+nk，n=1+n1+2n2+……+knk 所以得n0 = n2 + 2n3 + …… + (k-1)nk + 1
6.6 已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结
点，试求该树的叶子结点数目
解：
度：一个结点含有的子树的个数称为该节点的度；
设有nk个度为k的分支结点，n0个度为0的分支结点 各点度数总和为：n=k*nk+1,
第6章 树与森林
66 第6章 树与森林
6-5 在结点个数为n (n>1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？
6-6 试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。
6-7 如果一棵树有n1个度为1的结点, 有n2个度为2的结点, … , nm个度为m的结点, 试问有多少个度为0的结点? 试推导之。
6-9 若用二叉链表作为二叉树的存储表示，试针对以下问题编写递归算法：
(1) 统计二叉树中叶结点的个数。
(2) 以二叉树为参数，交换每个结点的左子女和右子女。
6-10 一棵高度为h的满k叉树有如下性质: 第h层上的结点都是叶结点, 其余各层上每个结点都有k棵非空子树, 如果按层次自顶向下, 同一层自左向右, 顺序从1开始对全部结点进行编号, 试问:
(1) 各层的结点个数是多少?
(2) 编号为i的结点的父结点(若存在)的编号是多少?
(3) 编号为i的结点的第m个孩子结点(若存在)的编号是多少?
(4) 编号为i的结点有右兄弟的条件是什么? 其右兄弟结点的编号是多少?
(5) 若结点个数为 n, 则高度h是n 的什么函数关系?
6-16 请画出右图所示的树所对应的二叉树。
【解答】
6-17 在森林的二叉树表示中，用llink存储指向结点第一个子女的指针，用rlink存储指向结点下一个兄弟的指针，用data存储结点的值。如果我们采用静态二叉链表作为森林的存储表示，同时按森林的先根次序依次安放森林的所有结点，则可以在它们的结点中用只有一个二进位的标志ltag代替llink，用rtag代替rlink。并设定若ltag = 0，则该结点没有子女，若ltag 0，则该结点有子女；若rtag = 0，则该结点没有下一个兄弟，若rtag 0，则该结点有下一个兄弟。试给出这种表示的结构定义，并设计一个算法，将用这种表示存储的森林转换成用llink
..WORD完美格式..
..专业知识编辑整理..
第六章树和二叉树（下载后用阅读版式视图或web版式可以看清）
习 题
一、选择题
1．有一“遗传”关系：设x是y的父亲，则x可以把它的属性遗传给y。表示该遗传关系最适合的数据结构为( )。
A.向量 B.树 C图 D.二叉树
2．树最合适用来表示( )。
A.有序数据元素 B元素之间具有分支层次关系的数据
C无序数据元素 D.元素之间无联系的数据
3．树B的层号表示为la，2b，3d，3e，2c，对应于下面选择的( )。
A. la (2b (3d,3e),2c) B. a(b(D,e),c)
C. a(b(d,e),c) D. a(b,d(e),c)
4.高度为h的完全二叉树至少有( )个结点，至多有( )个结点。
A. 2h_l B.h C．2h-1 D. 2h
5.在一棵完全二叉树中，若编号为f的结点存在右孩子，则右子结点的编号为( )。
A. 2i B. 2i-l C. 2i+l D. 2i+2
6.一棵二叉树的广义表表示为a(b(c)，d(e(，g(h))，f))，则该二叉树的高度为 ( )。
A.3 B.4 C.5 D.6
7.深度为5的二叉树至多有( )个结点。
A. 31 B. 32 C. 16 D. 10
第6章树和二叉树(2) 第六章 树和二叉树
一、选择题
1．算术表达式a+b*（c+d/e）转为后缀表达式后为（ ）
A．ab+cde/* B．abcde/+*+ C．abcde/*++ D．abcde*/++
2. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（ ）
A．m-n B．m-n-1 C．n+1 D．条件不足，无法确定
3．若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为（ ）。
A．n-1 B．n/m-1 C．(n-1)/(m-1) D． n/(m-1)-1
E．(n+1)/(m+1)-1
4．深度为h的满m叉树的第k层有（ ）个结点。(1=
A．mk-1 B．mk-1 C．mh-1 D．mh-1
5. 若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为( )
A.X的双亲 B.X的右子树中最左的结点 C.X的左子树中最右结点 D.X的左子树中最右叶结点
6. 引入二叉线索树的目的是（ ）
A．加快查找结点的前驱或后继的速度 B．为了能在二叉树中方便的进行插入与删除
C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一
7．由3 个结点可以构造出多少种不同的二叉树？（ ）
A．2 B．3 C．4 D．5
8．下述编码中哪一个不是前缀码（ ）。 A．（00，01，10，11） B．（0，1，00，11） C．（0，10，110，111）
D．（1，01，000，001）
二、判断题
1. 给定一棵树，可以找到唯一的一棵二叉树与之对应。
