数据结构（张惠涛）第六章习题答案及解析.docx

一、选择题

1.正确答案：B

解析：树中结点总数N=度数之和+1。给定度为4的结点20个、度为3的结点10个、度为2的结点1个、度为1的结点10个，度数之和为4×20+3×10+2×1+1×10=80+30+2+10=122。因此，总结点数N=122+1=123。叶子结点个数为123-20-10-1-10=82个。

2.正确答案：C

解析：叶子结点个数n0=n2+1=8，结点总数N=n0+n1+n2=8+5+7=20。

3.正确答案：C

解析：该完全二叉树，n0=8，n2=n0-1=7，则n=n0+n1+n2=15+n1。完全二叉树中n1=0或n1=1，则n1=1时结点个数最多，此时n=16。最大高度h==5。

4.正确答案：C

解析：完全二叉树的叶子结点只能在最下两层，对于本题，结点最多的情况是第6层为倒数第二层，即1～6层构成一个满二叉树，其结点总数为26-1=63。其中第6层有25=32个结点，含8个叶子结点，则另外有32-8=24个非叶子结点，它们中每个结点有两个孩子结点（均为第7层的叶子结点），计48个叶子结点。这样最多的结点个数=63+48=111。

5.正确答案：A

解析：森林转二叉树时，第一棵树的根作为二叉树的根，其左子树是第一棵树去除根后的子树（结点数为a?1)，右子树是其余树转换的二叉树（结点数为b+c+d)。故二叉树根结点的左子树结点数为a?1。

6.正确答案：C

森林转二叉树后，无右孩子的结点对应原森林中是其父结点最后一个孩子的结点或最后一棵树的根。森林中有n个非叶子结点，每个非叶子结点恰好有一个最后一个孩子，共

n个结点；加上最后一棵树的根（无右孩子），总计n+1个无右孩子的结点。

7.正确答案：D

解析：高度为3的满二叉树有7个结点：根A，左孩子B，右孩子C；B有左孩子D、右孩子E；C有左孩子F、右孩子G。还原为森林：A为第一棵树根，其左子树转换为子树（B为根，D、E为子），右子树转换为子树（C为根，F、G为子）。包含A的树有结点A、B、D、E，共4个。

二、填空题

第一个空：11

第二个空：6

解析：三次树度数之和为3×2+2×1+1×2=6+2+2=10，总结点数=10+1=11，叶子结点数=11?2?1?2=6。

第一个空：14

解析：根据树的性质，度数之和+1=结点总数，可得树的结点总数N为3×2+2×3+2×4+1=21。叶子结点个数=21-3-2-2=14。

3.第一个空：A

第二个空：B、E、G、D

第三个空：4

第四个空：E、F

第五个空：A

解析：括号表示A(B,C(E,F(G)),D)对应树结构：

根：A

A的孩子：B、C、D

C的孩子：E、F

F的孩子：G

叶子：B、E、G、D（无孩子）

C的孩子：E、F

C的双亲：A

应用题

参考答案：

树形表示形式为：

对应的先序序列为：abcedfhgij

解析：由后序序列echfjigdba（根为a），中序序列ecbhfdjiga（左子树中序ecbhfdjig，右子树空）。递归构建：

-左子树后序echfjigdb（根b），中序ecbhfdjig（左子树中序ec，右子树中序hfdjig）。

-左子树：中序ec，后序ec（根c，左e）。

-右子树：中序hfdjig，后序hfjigd（根d），左子树中序hf（根f，左h），右子树中序jig（根g，左i，i左j）。

参考答案：

typedefstructnode

{chardata;

structnode*lchild，*rchild;

}BTNode;

intNodeNum(BTNode*b)

{

if(b==NULL)

return0;

else

returnNodeNum(b-lchild)+NodeNum(b-rchild)+1;

}

参考答案：

typedefstructnode

{chardata;

structnode*lchild，*rchild;

}BTNode;

intcount=0;

voidLnodenum(BTNode*b，inth，intk)

{if(b==NULL)

return0;

else

{if(h==k)count++;

elseif(hk)

{Lnodenum1(b-lchild，h+1，k);

Lnodenum1(b-rchild，h+1，k);

}

}

}

参考答案：

voidfindMinNode(BTNode*b