南邮陈慧南版数据结构课后习题5参考答案

5.2

（1）无序树：9棵 （2）有序树：12棵 （3）二叉树：30棵 5.4

（1）2k-1 （2）??i?1?? k??（3）k(i-1) + m + 1 （4） i +1≤??i?1??k?1 ?k?5.5

(1) 空二叉树和所有结点均无左孩子的二叉树 (2) 空二叉树和只有一个根

(3) 空二叉树和所有结点均无右孩子 5.6

5.7

先：DEHFJGCKAB 中：HEJFGKCDAB 后：HJKCGFEBAD 5.9 (1)

template

void BinaryTree::Del(BTNode *p) //private { if (p!=NULL) { Del(p->lChild); Del(p->rChild); delete p; } }

template

void BTree::Del() //public {

Del(root); root = NULL; } (2)

/*求二叉树中度为1的结点个数*/ template

int BinaryTree::CountDegree1() {

int total = 0;

CountDegree1(root, total); return total; }

template

void BinaryTree::CountDegree1(BTNode *t, int &num) {

if (t) {

if ( ( (t->lChild != NULL) && (t->rChild == NULL) ) || ( (t->lChild == NULL) && (t->rChild != NULL)) ) {

++num; }

CountDegree1(t->lChild, num); CountDegree1(t->rChild, num); } } (3)

template

void BinaryTree::Exch(BTNode *p) //private { if (p!=NULL) { BTNode *temp; temp=p->lchild; p->lchild=p->rchild; p->rchild=temp; Exch(p->lchild); Exch(p->rchild);

} }

template

void BTree::Exchange() //public {

Exch(root); } 5.14

ADEFJGHKLCMBADE HBGCKFJ 5.16

分别以下列数据为输入，构造最小堆。

(1) 10，20，30，40，50，60，70，80 (2) 80，70，60，50，40，30，20，10 (3) 80，10，70，20，60，30，50，40 （1）

（2）

（3）

5.17分别以上题的数据为输入，从空的优先权队列开始，依此插入这些元素，求结果优先权队列的状态。

5.19 （1）

3801016102217910DE011255FC0123AB （2）WPL = 91

（3）各字符的编码 A:1010 B:1011 C:100 D:00 E:01 F:11