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

二叉树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表示查找失败；返回值：-1 表示未找到，-2 表示没有默认树导致查找失败，1成功。DefType GetFather(DefType data0);函数功能：