[工学]二叉树ADT及哈夫曼编码.doc

《[工学]二叉树ADT及哈夫曼编码.doc》由会员分享，可在线阅读，更多相关《[工学]二叉树ADT及哈夫曼编码.doc（62页珍藏版）》请在三一办公上搜索。

1、二叉树ADT及哈夫曼编码 一、 问题重述建立二叉树的ADT，并实现对10个不同大小数进行哈夫曼编码。ADT实现功能：随机生成一棵二叉树，插入节点，删除节点，查找节点，遍历树（先序，中序，后序和层序），输出树高，输出节点数，输出叶子数。二、 算法基本思想1 树的ADT（1） 随机生成二叉树：用队列实现，随机对队头节点添加左右子树，并将新节点入队，将其出队，直到节点数到达用户指定的n。（2） 遍历二叉树：先序、中序和后序遍历都用递归实现，层序遍历用队列实现，访问队头节点，并将其子节点入队，将其出队，直到队列为空。（3） 插入节点：从根节点开始，随机决定往左右插入，如果该方向的子节点为空，则插入到此

2、位置，否则移动指针到子节点，继续执行上述操作。（4） 删除节点：先找到此节点，如果是叶节点，直接释放该节点，并对其父节点相应链接进行修改；否则依次将子节点的数据往上移动（这样可以避免频繁修改父节点的链接，比较方便），到达一个叶节点后，将此叶节点释放，并修改其父节点链接。（5） 查找节点：为了让查找结果更明确，用层序遍历查找，最后得到该节点的层数和在该层的位置。（6） 得到树高：用递归实现，某一节点的高度等于其子节点的最大高度加一。（7） 得到节点数：用递归实现，以某一节点为根的树的节点数等于其左右子树的所有节点加一。（8） 得到叶节点数：用递归实现，某一节点下所包括的的叶节点数等于其左右子树所

3、包含的叶子数。（9） 删除树：递归实现，后序遍历所有节点，依次删除。2 哈夫曼编码的实现（1） 生成哈夫曼树：首先，随机生成10个不同大小的1100之间的整数，归一化计算出每个节点的概率；然后，利用冒泡算法的思想，每次只得到前两个最小权值节点，在数组末端加入新节点，其权值等于这两个节点的权值和，左右儿子分别为第一个节点和第二个节点，将记录数组首位置的游标加二，这样循环九次之后就得到一棵哈夫曼树。其根节点是数组末端存储的节点。（2） 得到所有叶节点的哈夫曼编码：用栈实现对路径的记录（左走压入0，右走压入1），后序遍历所有节点，只输出叶节点的路径。三、 主要数据结构和函数1 二叉树的节点：type

4、def struct BinaryNodevoid* data;BinaryNode* LCh; BinaryNode* RCh;BN;2 队列类：（1） 公有函数和变量：int Empty();函数功能： 得到队列是否为空； 返回值： 0表示非空，1表示空。void* GetFront();函数功能： 得到队首元素； 返回值： NULL表示队空，其他为队首元素的指针。int Del();函数功能： 删除队首元素； 返回值： -1表示队空删除失败，0表示删除成功。int Add(void*);函数功能： 往队尾加入元素； 返回值： -1表示队列满加入失败，0表示加入成功。void* Queue

5、DataMAXSIZEQUEUE; 存储队列元素指针的数组。3 二叉树类：（1） 公有函数及变量： int Create(int n); 函数功能： 随机生成一棵有n个节点的二叉树，并将其作为对象内部默认树； 参数： n 代表节点数； 返回值： -1表示生成失败，1表示生成成功。int GetHeight(); 函数功能： 得到对象内部默认树的高度； 返回值： 该树的高度。 int GetNumNode(); 函数功能： 得到对象内部默认树的节点数 返回值： 该树的节点数。 int GetNumLeaf(); 函数功能： 得到对象内部默认树的叶节点数 返回值： 该树的叶节点数。 void Tr

6、aversal(int mode,int which); 函数功能： 遍历对象内部的一棵树； 参数： mode 表示遍历方式，可以取以下值： PREORDER 先序遍历， INORDER 中序遍历， POSTORDER 后序遍历， FLOORORDER 层序遍历； which 表示遍历哪棵树，可以取以下值： INNERTREE 遍历内部默认树， HUFFMANTREE 遍历生成的哈夫曼树； void Insert(DefType data0); 函数功能： 将节点data0随即插入默认树中； 参数： data0 代表节点标识。int Delete(DefType data0); 函数功能： 删

7、除节点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); 函数

8、功能： 得到节点data0的父节点； 参数： data0 代表节点标识； 返回值： 父节点标识。 void HuffmanCreate(); 函数功能： 随机生成一棵有10个叶节点的哈夫曼树。 void ShowHuffmanCode(); 函数功能： 输出哈夫曼树各叶节点的哈夫曼编码。 void UpdateInnerTree(); 函数功能： 更新内部默认树，即将新生成的哈夫曼树作为内部默认树。 void ClearInnerTree(); 函数功能： 删除对象内部默认的树。 int LeafAmount; 存储树的叶节点数。 int NodeAmount; 存储树的节点数。 int He

9、ight; 存储树的高度。（2） 私有函数和变量：BN* NewBN(DefType* data); 函数功能： 新建一个节点； 参数： data 代表此节点所具有的标识； 返回值： 此节点的指针。 int MaxHeight(BN* now); 函数功能： 得到默认树的高度； 参数： now 代表当前节点指针； 返回值： 以当前节点为根的树的高度。 int NumNode(BN* now); 函数功能： 得到默认树的节点数； 参数： now 代表当前节点指针； 返回值： 当前节点及其下所有节点的数目。 int NumLeaf(BN* now); 函数功能： 得到默认树的叶节点数； 参数： n

10、ow 代表当前节点指针； 返回值： 当前节点及其下所有节点中的叶节点数目。 void PreOrder(BN* now); 函数功能： 先序遍历默认树； 参数： now 代表当前节点指针。 void InOrder(BN* now); 函数功能： 中序遍历默认树； 参数： now 代表当前节点指针。 void PostOrder(BN* now); 函数功能： 后序遍历默认树； 参数： now 代表当前节点指针。 void FloorOrder(BN* root); 函数功能： 层序遍历默认树； 参数： root 代表此树根节点的地址。BN* FindInOrder(DefType data0

11、,BN* now); 函数功能： 得到某节点的指针； 参数： data0 代表所查找的节点表示； now 代表当前节点指针； 返回值： NULL 表示未找到该节点，否则为该节点的指针。 void DeleteThis(BN* pos); 函数功能： 删除某一节点并调整树的结构； 参数： pos 代表所删除的节点指针。 int ReArrange(BN* now); 函数功能： 移动某节点后调整树的结构； 参数： now 代表当前节点指针； 返回值： 1 表示调整的节点为叶节点，0表示调整节点不是叶节点。 BN* GetFather(BN* ThisNode,BN* now); 函数功能： 递归

12、得到某一节点的父节点； 参数： ThisNode 代表所查找的节点指针； now 代表当前节点指针； 返回值： NULL 表示未找到该节点，其他情况为找到的父节点指针。 void PostShowHuffmanLeaf(BN* now,int Stack,int &top); 函数功能： 后序遍历哈夫曼树所有叶节点； 参数： now 代表当前节点指针； Stack 存储路径用到的栈； &top 栈顶游标。void DeleteAll(BN* now); 函数功能： 删除对象内部默认的树及所有数据； 参数：now 代表当前节点指针。BN* Root; 存储对象内部默认树的根节点 BN* Root

13、All; 存储树根的父节点BN* HuffmanBTRoot; 存储哈夫曼树的根节点。四、 样例1 总界面：2 随机生成有20个节点二叉树的层序遍历结果：3 随机生成的10个节点哈弗曼编码：4 此哈夫曼树的层序遍历结果：五、 算法复杂度及性能 1本程序中空间复杂度不变的都是节点的个数 O(n)，遍历的时间复杂度也是节点的个数O(n)，递归遍历的空间复杂度等于树的高度 log2(n+1)。 生成哈夫曼树的时间复杂度是数O(n*n/2)。2 本程序用指针实现，对节点个数的限制小，时间上不如数组实现的快。3 用void*实现对不同数据类型的兼容，使用方便，而且只需改变默认数据类型即可改变节点的数据域

14、的数据类型。六、 源代码 BinaryTree.h: #include Queue.h#include #include #include #include #include typedef struct BinaryNodevoid* data;BinaryNode* LCh; BinaryNode* RCh;BN;/定义二叉树的节点typedef float DefType;/定义默认数据类型#define PREORDER 0#define INORDER 1#define POSTORDER 2#define FLOORORDER 3#define DEFAULTNUMLEAF 10#

15、define DEFAULTNUMNODE 2*DEFAULTNUMLEAF-1#define HUFFMANNODERANGE 1000/定义哈夫曼树叶节点的范围#define HUFFMANTREE 1#define INNERTREE 0#define MAXSTACK 1000class BinaryTree public:int Create(int n); /* 函数功能： 随机生成一棵有n个节点的二叉树，并将其作为对象内部默认树； 参数：n 代表节点数；返回值：-1表示生成失败，1表示生成成功。*/int GetHeight();/* 函数功能： 得到对象内部默认树的高度返回值：

16、 该树的高度。*/int GetNumNode();/* 函数功能： 得到对象内部默认树的节点数返回值： 该树的节点数。*/int GetNumLeaf();/* 函数功能： 得到对象内部默认树的叶节点数返回值： 该树的叶节点数。*/void Traversal(int mode,int which); /* 函数功能： 遍历对象内部的一棵树； 参数：mode 表示遍历方式，可以取以下值： PREORDER 先序遍历， INORDER 中序遍历， POSTORDER 后序遍历， FLOORORDER 层序遍历； which 表示遍历哪棵树，可以取以下值： INNERTREE 遍历内部默认树，

17、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 代表节点标识； &Fl

18、oorth 存储得到的层数，若小于0表示查找失败；&FloorNumth 存储节点在其层的位置，若小于0表示查找失败；返回值：-1 表示未找到，-2 表示没有默认树导致查找失败，1 表示查找成功。*/DefType GetFather(DefType data0); /* 函数功能： 得到节点data0的父节点； 参数：data0 代表节点标识；返回值：父节点标识。*/void HuffmanCreate(); /* 函数功能： 随机生成一棵有10个叶节点的哈夫曼树。*/void ShowHuffmanCode(); /* 函数功能： 输出哈夫曼树各叶节点的哈夫曼编码。*/void Updat

19、eInnerTree(); /* 函数功能： 更新内部默认树，即将新生成的哈夫曼树作为内部默认树。*/void ClearInnerTree(); /* 函数功能： 删除对象内部默认的树。*/int LeafAmount;/存储树的叶节点数。int NodeAmount;/存储树的节点数。int Height;/存储树的高度。BinaryTree();virtual BinaryTree();private:BN* NewBN(DefType* data);/* 函数功能： 新建一个节点； 参数：data 代表此节点所具有的标识；返回值：此节点的指针。*/int MaxHeight(BN* n

20、ow);/* 函数功能： 得到默认树的高度； 参数：now 代表当前节点指针；返回值：以当前节点为根的树的高度。*/int NumNode(BN* now);/* 函数功能： 得到默认树的节点数； 参数：now 代表当前节点指针；返回值：当前节点及其下所有节点的数目。*/int NumLeaf(BN* now);/* 函数功能： 得到默认树的叶节点数； 参数：now 代表当前节点指针；返回值：当前节点及其下所有节点中的叶节点数目。*/void PreOrder(BN* now);/* 函数功能： 先序遍历默认树； 参数：now 代表当前节点指针。*/void InOrder(BN* now);

21、/* 函数功能： 中序遍历默认树； 参数：now 代表当前节点指针。*/void PostOrder(BN* now);/* 函数功能： 后序遍历默认树； 参数：now 代表当前节点指针。*/void FloorOrder(BN* root);/* 函数功能： 层序遍历默认树； 参数：root 代表此树根节点的地址。*/BN* FindInOrder(DefType data0,BN* now);/* 函数功能： 得到某节点的指针； 参数：data0 代表所查找的节点表示；now 代表当前节点指针；返回值：NULL 表示未找到该节点，否则为该节点的指针。*/void DeleteThis(BN

22、* pos); /* 函数功能： 删除某一节点并调整树的结构； 参数：pos 代表所删除的节点指针。*/int ReArrange(BN* now);/* 函数功能： 移动某节点后调整树的结构； 参数：now 代表当前节点指针；返回值：1 表示调整的节点为叶节点，0表示调整节点不是叶节点。*/BN* GetFather(BN* ThisNode,BN* now); /* 函数功能： 递归得到某一节点的父节点； 参数：ThisNode 代表所查找的节点指针；now 代表当前节点指针；返回值：NULL 表示未找到该节点，其他情况为找到的父节点指针。*/void PostShowHuffmanLea

23、f(BN* now,int Stack,int &top);/* 函数功能： 后序遍历哈夫曼树所有叶节点； 参数：now 代表当前节点指针； Stack 存储路径用到的栈；&top 栈顶游标。*/void DeleteAll(BN* now);/* 函数功能： 删除对象内部默认的树及所有数据； 参数：now 代表当前节点指针。*/BN* Root;/存储对象内部默认树的根节点BN* RootAll;/存储树根的父节点BN* HuffmanBTRoot;/存储哈夫曼树的根节点; BinaryTree.cpp: / BinaryTree.cpp: implementation of the Bin

24、aryTree class./#include stdafx.h#include BinaryTree.h/ Construction/Destruction/BinaryTree:BinaryTree()srand(time(0);RootAll = NewBN(new DefType(0);Root = NULL;HuffmanBTRoot = NULL;Height = 0;LeafAmount = 0;NodeAmount = 0;BinaryTree:BinaryTree()DeleteAll(Root);int BinaryTree:Create(int n)NodeAmount

25、= n;if (nLCh = Root;while (n0LCh = New;que.Del();else if (1 = flag)Old-RCh = New;que.Del();elseif (Old-LCh = NULL)Old-LCh = New;elseOld-RCh = New;que.Del();return 1; void BinaryTree:Traversal(int mode,int which)if (INNERTREE = which) if (PREORDER = mode) PreOrder(Root); if (INORDER = mode) InOrder(R

26、oot); if (POSTORDER = mode) PostOrder(Root); if (FLOORORDER = mode) FloorOrder(Root);else if (PREORDER = mode) PreOrder(HuffmanBTRoot); if (INORDER = mode) InOrder(HuffmanBTRoot); if (POSTORDER = mode) PostOrder(HuffmanBTRoot); if (FLOORORDER = mode) FloorOrder(HuffmanBTRoot);void BinaryTree:PreOrde

27、r(BN* now)if (now != NULL) cout.setf(ios:fixed); coutsetprecision(4)dataLCh); PreOrder(now-RCh);void BinaryTree:InOrder(BN *now) if (now != NULL) InOrder(now-LCh);cout.setf(ios:fixed); coutsetprecision(4)dataRCh);void BinaryTree:PostOrder(BN *now)if (now != NULL) PostOrder(now-LCh); PostOrder(now-RC

28、h);cout.setf(ios:fixed); coutsetprecision(4)dataendl;void BinaryTree:FloorOrder(BN* root)Queue que;que.Add(root);int n0=0;int i;for (;)n0+;cout第n0层:endl;int rear0 = que.rear;for (i=que.front;i=rear0;i+)BN* Now = (BN*)que.GetFront();cout.setf(ios:fixed); coutsetprecision(4)dataLCh != NULL) cout左儿子:se

29、tprecision(4)LCh-dataRCh != NULL) cout右儿子:setprecision(4)RCh-data ;coutLCh != NULL)que.Add(Now-LCh);if (Now-RCh != NULL)que.Add(Now-RCh);que.Del();if (que.Empty() = 1)break;BN* BinaryTree:NewBN(DefType* data)BN* New = new BN;New-data = data;New-LCh = NULL;New-RCh = NULL;return New;void BinaryTree:De

30、leteAll(BN* now)if (now != NULL)DeleteAll(now-LCh);DeleteAll(now-RCh); delete now-data; delete now;int BinaryTree:GetHeight()return Height = MaxHeight(Root);int BinaryTree:MaxHeight(BN *now)if (now != NULL)int left = MaxHeight(now-LCh);int right = MaxHeight(now-RCh);if (leftright)return 1+left;elser

31、eturn 1+right;elsereturn 0;int BinaryTree:GetNumNode()return NodeAmount = NumNode(Root);int BinaryTree:NumNode(BN *now)if (now != NULL)return 1+NumNode(now-LCh)+NumNode(now-RCh);elsereturn 0;int BinaryTree:GetNumLeaf()return LeafAmount = NumLeaf(Root);int BinaryTree:NumLeaf(BN *now)if (now-LCh = NUL

32、L)&(now-RCh = NULL)return 1;else int left;int right;if (now-LCh != NULL) left = NumLeaf(now-LCh);else left = 0; if (now-RCh != NULL) right = NumLeaf(now-RCh);elseright = 0;return left+right;void BinaryTree:Insert(DefType data0)BN* New = NewBN(new DefType(data0);BN* now = Root;if (Root = NULL)Root =

33、New;return;int flag;for (;)flag = rand()%2;if (0 = flag)if (now-LCh = NULL)now-LCh = New;NodeAmount+;break;elsenow = now-LCh;elseif (now-RCh = NULL)now-RCh = New;NodeAmount+;break;elsenow = now-RCh;int BinaryTree:Find(DefType data0,int &Floorth,int &FloorNumth)if (Root = NULL)Floorth = -1;FloorNumth

34、 = -1;return -2;Queue que;que.Add(Root);int n0=0;int i;for (;)n0+;int rear0 = que.rear;int front0 = que.front;BN* Now;for (i=front0;idata = data0)Floorth = n0;FloorNumth = i-front0+1;return 1;if (Now-LCh != NULL)que.Add(Now-LCh);if (Now-RCh != NULL)que.Add(Now-RCh);que.Del();if (que.Empty() = 1)Floorth = -1;FloorNumth = -1;return -1;