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

二叉树ADT及哈夫曼编码 问题重述建立二叉树的ADT，并实现对10个不同大小数进行哈夫曼编码。ADT实现功能：随机生成一棵二叉树，插入节点，删除节点，查找节点，遍历树（先序，中序，后序和层序），输出树高，输出节点数，输出叶子数。算法基本思想树的ADT随机生成二叉树：用队列实现，随机对队头节点添加左右子树，并将新节点入队，将其出队，直到节点数到达用户指定的n。遍历二叉树：先序、中序和后序遍历都用递归实现，层序遍历用队列实现，访问队头节点，并将其子节点入队，将其出队，直到队列为空。插入节点：从根节点开始，随机决定往左右插入，如果该方向的子节点为空，则插入到此位置，否则移动指针到子节点，继续执行上述操作。删除节点：先找到此节点，如果是叶节点，直接释放该节点，并对其父节点相应链接进行修改；否则依次将子节点的数据往上移动（这样可以避免频繁修改父节点的链接，比较方便），到达一个叶节点后，将此叶节点释放，并修改其父节点链接。查找节点：为了让查找结果更明确，用层序遍历查找，最后得到该节点的层数和在该层的位置。得到树高：用递归实现，某一节点的高度等于其子节点的最大高度加一。得到节点数：用递归实现，以某一节点为根的树的节点数等于其左右子树的所有节点加一。得到叶节点数：用递归实现，某一节点下所包括的的叶节点数等于其左右子树所包含的叶子数。删除树：递归实现，后序遍历所有节点，依次删除。哈夫曼编码的实现生成哈夫曼树：首先，随机生成10个不同大小的1~100之间的整数，归一化计算出每个节点的概率；然后，利用冒泡算法的思想，每次只得到前两个最小权值节点，在数组末端加入新节点，其权值等于这两个节点的权值和，左右儿子分别为第一个节点和第二个节点，将记录数组首位置的游标加二，这样循环九次之后就得到一棵哈夫曼树。其根节点是数组末端存储的节点。得到所有叶节点的哈夫曼编码：用栈实现对路径的记录（左走压入0，右走压入1），后序遍历所有节点，只输出叶节点的路径。主要数据结构和函数二叉树的节点：typedef struct BinaryNode{void* data;BinaryNode* LCh; BinaryNode* RCh;}BN;队列类：公有函数和变量：int Empty();函数功能： 得到队列是否为空； 返回值： 0表示非空，1表示空。void* GetFront();函数功能： 得到队首元素； 返回值： NULL表示队空，其他为队首元素的指针。int Del();函数功能： 删除队首元素； 返回值： -1表示队空删除失败，0表示删除成功。int Add(void*);函数功能： 往队尾加入元素； 返回值： -1表示队列满加入失败，0表示加入成功。void* QueueData[MAXSIZEQUEUE]; 存储队列元素指针的数组。二叉树类：公有函数及变量： int Create(int n); 函数功能： 随机生成一棵有n个节点的二叉树，并将其作为对象内部默认树； 参数： n 代表节点数； 返回值： -1表示生成失败，1表示生成成功。int GetHeight(); 函数功能： 得到对象内部默认树的高度； 返回值： 该树的高度。 int GetNumNode(); 函数功能： 得到对象内部默认树的节点数 返回值： 该树的节点数。 int GetNumLeaf(); 函数功能： 得到对象内部默认树的叶节点数 返回值： 该树的叶节点数。 void Traversal(int mode,int which); 函数功能： 遍历对象内部的一棵树； 参数： mode 表示遍历方式，可以取以下值： PREORDER先序遍历， INORDER中序遍历， POSTORDER后序遍历， FLOORORDER 层序遍历； which 表示遍历哪棵树，可以取以下值： INNERTREE遍历内部默认树， HUFFMANTREE 遍历生成的哈夫曼树； void Insert(DefType data0); 函数功能： 将节点data0随即插入默认树中； 参数： data0 代表节点标识。int Delete(DefType data0); 函数功能： 删除节点data0； 参数： data0 代表节点标识； 返回值： -1 表示未找到节点，删除失败；0 表示删除成功。 int Find(DefType data0,int Floorth,int FloorNumth); 函数功能： 查找节点data0，并得到其所在层数和在该层的位置； 参数： data0代表节点标识； Floorth存储得到的层数，若小于0表示查找失败； FloorNumth 存储节点在其层的位置，若小于0表示查找失败