数据结构(C语言版)课后习题答案 下载本文

方案比较: 字 母编号 1 2 3 4 5 6 方案1的WPL=2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61 方案2的WPL=3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3 结论:哈夫曼编码优于等长二进制编码

(4)已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、8,11,试填写出其对应哈夫曼树HT的存储结构的初态和终态。

答案: 初态:

1 2 3 4 5 6 7 8 9 10 11 12 13 weight 3 12 7 4 2 8 11 parent 0 0 0 0 0 0 0 0 0 0 0 0 0 lchild 0 0 0 0 0 0 0 0 0 0 0 0 0 rchild 0 0 0 0 0 0 0 0 0 0 0 0 0

7 8 对应编码 1100 00 11110 1110 10 11111 01 1101 出现频率 0.07 0.19 0.02 0.06 0.32 0.03 0.21 0.10 字母编号 1 2 3 4 5 6 7 8 对应编码 000 001 010 011 100 101 110 111 出现频率 0.07 0.19 0.02 0.06 0.32 0.03 0.21 0.10 XXXVII

终态:

1 2 3 4 5 6 7 8 9 10 11 12 13

3.算法设计题

以二叉链表作为二叉树的存储结构,编写以下算法: (1)统计二叉树的叶结点个数。

[题目分析]如果二叉树为空,返回0,如果二叉树不为空且左右子树为空,返回1,如果二叉树不为空,且左右子树不同时为空,返回左子树中叶子节点个数加上右子树中叶子节点个数。 [算法描述]

int LeafNodeCount(BiTree T) { }

(2)判别两棵树是否相等。

if(T==NULL)

return 0; //如果是空树,则叶子结点个数为0

return 1; //判断结点是否是叶子结点(左孩子右孩子都为空),若是则返回1 return LeafNodeCount(T->lchild)+LeafNodeCount(T->rchild); else if(T->lchild==NULL&&T->rchild==NULL) else

weight 3 12 7 4 2 8 11 5 9 15 20 27 47 parent 8 12 10 9 8 10 11 9 11 12 13 13 0 lchild 0 0 0 0 0 0 0 5 4 3 9 2 11 rchild 0 0 0 0 0 0 0 1 8 6 7 10 12

XXXVIII

[题目分析]先判断当前节点是否相等(需要处理为空、是否都为空、是否相等),如果当前节点不相等,直接返回两棵树不相等;如果当前节点相等,那么就递归的判断他们的左右孩子是否相等。 [算法描述]

int compareTree(TreeNode* tree1, TreeNode* tree2)

//用分治的方法做,比较当前根,然后比较左子树和右子树 {bool tree1IsNull = (tree1==NULL); bool tree2IsNull = (tree2==NULL); if(tree1IsNull != tree2IsNull) { return 1; }

if(tree1IsNull && tree2IsNull) {//如果两个都是NULL,则相等 return 0;

}//如果根节点不相等,直接返回不相等,否则的话,看看他们孩子相等不相等 if(tree1->c != tree2->c) { return 1; }

return (compareTree(tree1->left,tree2->left)&compareTree(tree1->right,tree2->right))

(compareTree(tree1->left,tree2->right)&compareTree(tree1->right,tree2->left)); }//算法结束

(3)交换二叉树每个结点的左孩子和右孩子。

[题目分析]如果某结点左右子树为空,返回,否则交换该结点左右孩子,然后递归交换左右子树。

[算法描述]

void ChangeLR(BiTree &T) {

BiTree temp;

if(T->lchild==NULL&&T->rchild==NULL) else {

temp = T->lchild; T->lchild = T->rchild; T->rchild = temp;

XXXIX

return;

}

}//交换左右孩子

ChangeLR(T->lchild); //递归交换左子树 ChangeLR(T->rchild); //递归交换右子树

(4)设计二叉树的双序遍历算法(双序遍历是指对于二叉树的每一个结点来说,先访问这个结点,再按双序遍历它的左子树,然后再一次访问这个结点,接下来按双序遍历它的右子树)。

[题目分析]若树为空,返回;若某结点为叶子结点,则仅输出该结点;否则先输出该结点,递归遍历其左子树,再输出该结点,递归遍历其右子树。

[算法描述]

void DoubleTraverse(BiTree T) { }

(5)计算二叉树最大的宽度(二叉树的最大宽度是指二叉树所有层中结点个数的最大值)。

[题目分析] 求二叉树高度的算法见上题。求最大宽度可采用层次遍历的方法,记下各层结点数,每层遍历完毕,若结点数大于原先最大宽度,则修改最大宽度。

[算法描述]

int Width(BiTree bt)//求二叉树bt的最大宽度 {if (bt==null) return (0); //空二叉树宽度为0 else

{BiTree Q[];//Q是队列,元素为二叉树结点指针,容量足够大 front=1;rear=1;last=1;

//front队头指针,rear队尾指针,last同层最右结点在队列中的位置 temp=0; maxw=0; //temp记局部宽度, maxw记最大宽度 Q[rear]=bt; //根结点入队列 while(front<=last)

XL

if(T == NULL) { }

cout<data;

DoubleTraverse(T->lchild); //递归遍历左子树 cout<data;

DoubleTraverse(T->rchild); //递归遍历右子树 return;

cout<data; //叶子结点输出 else if(T->lchild==NULL&&T->rchild==NULL) else