数据结构-王红梅-课后答案

⑷ 编写算法，要求输出二叉树后序遍历序列的逆序。

【解答】要想得到后序的逆序，只要按照后序遍历相反的顺序即可，即先访问根结点，再遍历根结点的右

子树，最后遍历根结点的左子树。注意和前序遍历的区别，具体算法如下：

⑸ 以二叉链表为存储结构，编写算法求二叉树中结点x的双亲。

【解答】对二叉链表进行遍历，在遍历的过程中查找结点x并记载其双亲。具体算法如下：

⑹ 以二叉链表为存储结构，在二叉树中删除以值x为根结点的子树。

【解答】对二叉链表进行遍历，在遍历的过程中查找结点x并记载其双亲，然后将结点x的双亲结点中指

向结点x的指针置空。具体算法如下：

⑺ 一棵具有n个结点的二叉树采用顺序存储结构，编写算法对该二叉树进行前序遍历。 【解答】按照题目要求，设置一个工作栈以完成对该树的非递归算法，思路如下：

① 每访问一个结点，将此结点压栈，查看此结点是否有左子树，若有，访问左子树，重复执行该过程直到 左子树为空。

② 从栈弹出一个结点，如果此结点有右子树，访问右子树执行步骤①，否则重复执行步骤②。

具体算法如下：

⑻ 编写算法交换二叉树中所有结点的左右子树。

【解答】对二叉树进行后序遍历，在遍历过程中访问某结点时交换该结点的左右子树。 具体算法如下：

⑼ 以孩子兄弟表示法做存储结构，求树中结点x的第i个孩子。

【解答】先在链表中进行遍历，在遍历过程中查找值等于x的结点，然后由此结点的最左孩子域firstchild

找到值为x结点的第一个孩子，再沿右兄弟域rightsib找到值为x结点的第i个孩子并返回指向这个孩子的 指针。

树的孩子兄弟表示法中的结点结构定义如下： template struct TNode {

T data;

TNode *firstchild, *rightsib; };

具体算法如下：

学习自测及答案

1．前序遍历和中序遍历结果相同的二叉树是（ ）。

A 根结点无左孩子的二叉树

B 根结点无右孩子的二叉树

C 所有结点只有左子树的二叉树

D 所有结点只有右子树的二叉树

【解答】D

2．由权值为{3, 8, 6, 2, 5}的叶子结点生成一棵哈夫曼树，其带权路径长度为（ ）。 A 24 B 48 C 53 D 72 【解答】C

3．用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组A[1] ~ A[n]中，结点A[i]

若有左子树，

则左子树的根结点是（ ）。 A A[2i-1] B A[2i+1] C A[i/2] D A[2i] 【解答】D

4．对任何一棵二叉树T，如果其终端结点的个数为n0，度为2的结点个数为n2，则（ ）。 A n0=n2-1 B n0=n2 C n0=n2+1 D 没有规律 【解答】C

5．一棵满二叉树中共有n个结点，其中有m个叶子结点，深度为h，则（ ）。 A n=h+m B h+m=2n C m=h-1 D n=2h-1 【解答】D

6．对于完全二叉树中的任一结点，若其右分支下的子孙的最大层次为h，则其左分支下的子孙的最大层次 为（ ）。

A h B h+1 C h或h+1 D 任意 【解答】C

7．假定一棵度为3的树中结点数为50，则其最小高度应为 。 A 3 B 4 C 5 D 6

【解答】C

8．在线索二叉树中，一个结点是叶子结点的充要条件为（ ）。

A 左线索标志为0，右线索标志为1 B 左线索标志为1，右线索标志为0 C 左、右线索标志均为0 D 左、右线索标志均为1 【解答】C

9．对于一棵具有n个结点的树，其所有结点的度之和为（ ）。 【解答】n-1

10．在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是（ ）。 【解答】

11．现有按前序遍历二叉树的结果ABC，问有哪几种不同的二叉树可以得到这一结果？ 【解答】共有5种二叉树可以得到这一结果，如图5-15所示。

12．试找出分别满足下列条件的所有二叉树： ⑴ 前序序列和中序序列相同。 ⑵ 中序序列和后序序列相同。 ⑶ 前序序列和后序序列相同。

【解答】 ⑴ 空二叉树、只有一个根结点的二叉树和右斜树。 ⑵ 空二叉树、只有一个根结点的二叉树和左斜树。 ⑶ 空二叉树、只有一个根结点的二叉树

13．将下面图5-16所示的树转换为二叉树，图5-17所示的二叉树转换为树或森林。

【解答】图5-16所示树转换的二叉树如图5-18所示，图5-17所示二叉树转换的森林如图5-19所示。

14．以孩子兄弟表示法作为存储结构，编写算法求树的深度。

【解答】采用递归算法实现。若树为空树，则其深度为0，否则其深度等于第一棵子树的深度+1和兄弟子

树的深度中的较大者。具体算法如下：

15．设计算法，判断一棵二叉树是否为完全二叉树。

【解答】根据完全二叉树的定义可知，对完全二叉树按照从上到下、从左到右的次序（即层序）遍历应该 满足：

⑴ 若某结点没有左孩子，则其一定没有右孩子；

⑵ 若某结点无右孩子，则其所有后继结点一定无孩子。 若有一结点不满足其中任意一条，则该二叉树就一定不是完全二叉树。因此可采用按层次遍历二叉树的方

法依次对每个结点进行判断是否满足上述两个条件。为此，需设两个标志变量BJ和CM，其中BJ表示已扫

描过的结点是否均有左右孩子，CM存放局部判断结果及最后的结果。 具体算法如下：