二叉树ADT及哈夫曼编码.pdf

二叉树ADT及哈夫曼编码

问题重述

建立二叉树的ADT,并实现对10个不同大小数进行哈夫曼编码。ADT

实现功能随机生成一棵二叉树，插入节点，删除节点，查找节点，遍历树

(先序，中序，后序和层序)，输出树高，输出节点数，输出叶子数。

算法基本思想

1.树的ADT

(1)随机生成二叉树

用队列实现，随机对队头节点添加左右子树，并将新节点入队，

将其出队，直到节点数到达用户指定的n。

(2)遍历二叉树

先序、中序和后序遍历都用递归实现，层序遍历用队列实现，访

问队头节点，并将其子节点入队，将其出队，直到队列为空。

(3)插入节点

从根节点开始，随机决定往左右插入，如果该方向的子节点为空,

则插入到此位置，否则移动指针到子节点，继续执行上述操作。

(4)删除节点

先找到此节点，如果是叶节点，直接释放该节点，并对其父节点

相应链接进行修改；否则依次将子节点的数据往上移动(这样可

以避免频繁修改父节点的链接，比较方便)，到达一个叶节点后，

将此叶节点释放，并修改其父节点链接。

(5)查找节点

务了让善找结果更明确，用层序遍历查找，最后得到该节点的层

数和在该层的位置。

(6)得到树高

用递归实现，某一节点的高度等于其子节点的最大高度加一。

(7)得到节点数

用递归实现，以某一节点为根的树的节点数等于其左右子树的所

有节点加一。

(8)得到叶节点数

用递归实现，某一节点下所包括的的叶节点数等于其左右子树所

包含的叶子数。

(9)删除树

递归实现，后序遍历所有节点，依次删除。

2.哈夫曼编码的实现

(1)生成哈夫曼树

首先，随机生成10个不同大小的1〜100之间的整数，归一化计算

出每个节点的概率；

然后，利用冒泡算法的思想，每次只得到前两个最小权值节点，

在数组末端加入新节点，其权值等于这两个节点的权值和，左右

儿子分别为第一个节点和第二个节点，将记录数组首位置的游标

加二，这样循环九次之后就得到一棵哈夫曼树。其根节点是数组

末端存储的节点。

(2)得到所有叶节点的哈夫曼编码

用栈实现对路径的记录(左走压入0,右走压入1),后序遍历所

有节点，只输出叶节点的路径。

三、主要数据结构和函数

1.二叉树的节点

typedefstructBinaryNode

(

void*data;

BinaryNode*LCh;

BinaryNode*RCh;

}BN;

2.队列类

(1)公有函数和变量

intEmpty();

函数功能

得到队列是否为空；

返回值

0表示非空，1表示空。

void*GetFront();

函数功能

得到队首元素；

返回值

NULL表示队空，其他为队首元素的指针。

intDel();

函数功能

删除队首元素；

返回值

-1表示队空删除失败，。表示删除成功。