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

二叉树ADT及哈夫曼编码问题重述建立二叉树的ADT,并实现对10个不同大小数进行哈夫曼编码。ADT 实现功能：随机生成一棵二叉树，插入节点，删除节点，查找节点，遍历树(先序，中序，后序和层序)，输出树高，输出节点数，输出叶子数。算法基本思想1.树的ADT(1)随机生成二叉树：用队列实现，随机对队头节点添加左右子树，并将新节点入队，将其出队，直到节点数到达用户指定的n。(2)遍历二叉树：先序、中序和后序遍历都用递归实现，层序遍历用队列实现，访 问队头节点，并将其子节点入队，将其出队，直到队列为空。(3)插入节点：从根节点开始，随机决定往左右插入，如果该方向的子节点为空,则插入到此位置，否则移动指针到子节点，继续执行上述操作。(4)删除节点：先找到此节点，如果是叶节点，直接释放该节点，并对其父节点 相应链接进行修改；否则依次将子节点的数据往上移动(这样可 以避免频繁修改父节点的链接，比较方便)，到达一个叶节点后，将此叶节点释放，并修改其父节点链接。(5)查找节点：务了让善找结果更明确，用层序遍历查找，最后得到该节点的层 数和在该层的位置。(6)得到树高：用递归实现，某一节点的高度等于其子节点的最大高度加一。(7)得到节点数：用递归实现，以某一节点为根的树的节点数等于其左右子树的所 有节点加一。(8)得到叶节点数：用递归实现，某一节点下所包括的的叶节点数等于其左右子树所 包含的叶子数。(9)删除树：递归实现，后序遍历所有节点，依次删除。2.哈夫曼编码的实现(1)生成哈夫曼树：首先，随机生成10个不同大小的1100之间的整数，归一化计算 出每个节点的概率；然后，利用冒泡算法的思想，每次只得到前两个最小权值节点，在数组末端加入新节点，其权值等于这两个节点的权值和，左右 儿子分别为第一个节点和第二个节点，将记录数组首位置的游标 加二，这样循环九次之后就得到一棵哈夫曼树。其根节点是数组 末端存储的节点。(2)得到所有叶节点的哈夫曼编码：用栈实现对路径的记录(左走压入0,右走压入1),后序遍历所 有节点，只输出叶节点的路径。三、主要数据结构和函数1.二叉树的节点：typedef struct BinaryNode(void*data;BinaryNode*LCh;BinaryNode*RCh;BN;2.队列类：(1)公有函数和变量：int Empty();函数功能：得到队列是否为空；返回值：0表示非空，1表示空。void*GetFront();函数功能：得到队首元素；返回值：NULL表示队空，其他为队首元素的指针。int Del();函数功能：删除队首元素；返回值：-1表示队空删除失败，。表示删除成功。int Add(void*);函数功能：往队尾加入元素；返回值：-1表示队列满加入失败，。表示加入成功。void*QueueDataMAXSIZEQUEUE;存储队列元素指针的数组。3.二叉树类:(1)公有函数及变量：int Create(int n);函数功能：随机生成一棵有n个节点的二叉树，并将其作为对象内部默认 树；参数：n代表节点数；返回值：-1表示生成失败，1表示生成成功。int GetHeight();函数功能：得到对象内部默认树的高度;返回值:该树的高度。int GetNumNodeQ;函数功能：得到对象内部默认树的节点数返回值：该树的节点数。int GetNumLeaf();函数功能：得到对象内部默认树的叶节点数返回值:该树的叶节点数。void Traversal(int mode,int which);函数功能：遍历对象内部的一棵树；参数：mode表示遍历方式,PREORDER INORDERPOSTORDER FLOORORDER可以取以下值:先序遍历，中序遍历，后序遍历，层序遍历；which表示遍历哪棵树，可以取以下值：INNERTREE 遍历内部默认树，HUFFMANTREE遍历生成的哈夫曼树;void Insert(DefType dataO);函数功能：将节点dataO随即插入默认树中;参数：dataO代表节点标识。int Delete(DefType dataO);函数功能：删除节点dataO；参数：dataO代表节点标识；返回值:-1表示未找到节点，删除失败；0表示删除成功。int Find(DefType dataO,int&Floorth,int&FloorNumth);函数功能：查找节点data。，并得到其所在层数和在该层的位置；参数：dataO 代表节点标识；&Floorth 存储得到的层数，若小于0表示查找失败；&FloorNumth存储节点在其层的位置，若小于。表示查找失败;返回值:-1表示未找到，-2表示没有默认树导致查找失败，1成功。DefType GetFather(DefType dataO);函数功能：得到节点dataO的父节点；参数：dataO代表节点标识；返回值:父节点标识。void HuffmanCreate();函数功能：随机生成一棵有10个叶节点的哈夫曼树。void ShowHuffmanCodeQ;函数功能：输出哈夫曼树各叶节点的哈夫曼编码。void UpdatelnnerTreeQ;函数功能：更新内部默认树，即将新生成的哈夫曼树作为内部默认树。void ClearInnerTree();函数功能：删除对象内部默认的树。int Leaf Amount;存储树的叶节点数。int NodeAmount;存储树的节点数。int Height;存储树的高度。(2)私有函数和变量：BN*NewBN(DefType*data);函数功能：新建一个节点；参数：data 代表此节点所具有的标识；返回值：此节点的指针。int MaxHeight(BN*now);函数功能：得到默认树的高度；参数：now 代表当前节点指针；返回值：以当前节点为根的树的高度。int NumNode(BN*now);函数功能：得到默认树的节点数；参数：now 代表当前节点指针；返回值：当前节点及其下所有节点的数目。int NumLeaf(BN*now);函数功能：得到默认树的叶节点数；参数：now 代表当前节点指针；返回值：当前节点及其下所有节点中的叶节点数目。void PreOrder(BN*now);函数功能：先序遍历默认树；参数：now 代表当前节点指针。void InOrder(BN*now);函数功能：中序遍历默认树；参数：now 代表当前节点指针。void PostOrder(BN*now);函数功能：后序遍历默认树；参数：now 代表当前节点指针。void FloorOrder(BN*root);函数功能：层序遍历默认树；参数：root 代表此树根节点的地址。BN*FindInOrder(DefType dataO,BN*now);函数功能：得到某节点的指针；参数：dataO代表所查找的节点表示；now 代表当前节点指针；返回值:NULL表示未找到该节点，否则为该节点的指针。void DeleteThis(BN*pos);函数功能：删除某一节点并调整树的结构；参数：pos代表所删除的节点指针。int ReArrange(BN*now);函数功能：移动某节点后调整树的结构；参数：now 代表当前节点指针；返回值:1表示调整的节点为叶节点，0表示调整节点不是叶节点。BN*GetFather(BN*ThisNode,BN*now);函数功能：递归得到某一节点的父节点；参数：ThisNode代表所查找的节点指针；now 代表当前节点指针；返回值：NULL表示未找到该节点，其他情况为找到的父节点指针。void PostShowHuffmanLeaf(BN*now,int Stack,int&top);函数功能：后序遍历哈夫曼树所有叶节点；参数：now 代表当前节点指针；Stack存储路径用到的栈；&top 栈顶游标。void DeleteA11(BN*now);函数功能：删除对象内部默认的树及所有数据；参数：now 代表当前节点指针。BN*Root;存储对象内部默认树的根节点BN*RootAll;存储树根的父节点BN*HuffmanBTRoot;存储哈夫曼树的根节点。四、样例1.总界面：WC6.0vclSDev98lyProjectslyBinaryTreeDebuglyBinaryTree.exe二叉树ADT及哈夫曼编码华丽的分割线请输入操作:蓿 3 4请2人入 Xi华丽的分割线叉请，5人入人父 二，数数入棵度点子矍 一高*E詈，百 成的的的，点点点个 和打打列历、,A除找常，随店唐唐仔遍插删查得入入12分 的 请输丽，华 fi，一 鼻赏码一 夫默编一 哈普克一 的一 点象哈一 n对的一点-个 T一 10 一 fBtl一 棵清一一哈曼夫 生成哈机生出 随将输髓欲觐鹦然2.随机生成有20个节点二叉树的层序遍历结果:点WH 6 7 8 节011 1线 番16.0000c：:*F:WC6.0vclSDev98lyPro ject slyBinaryTreeDebugMyBinaryTree,exe*第1层：1.0000 第2层：2.0000 3.0000 第3层：4.0000 5.0000 第4层:6.0000 7.0000 密广左儿子：2.0000右儿子：3.0000右儿子：4.0000右兀字鸣.0000右儿子;6.0000右兀字：7.。0左儿子：8.0000左兀字：9.00。0右儿子：10.00008.0000 右儿子：T1.00009.0000 无兀字：12.000010.0000 左儿子：13.0000第6层：11.0000 右儿子：14.000012.0000 左兀字：15.0000 右儿子：16.000013.0000 左兀字：17.0000 右兀字：18.0000第7层:14.0000 左儿子：19.000015.0000 左兀字：20.0000二117.000018.00003.随机生成的10个节点哈弗曼编码:Pn|xWC6.0vclSDev98lyProjectslyBinaryTreeDebuglyBinaryTree.exe：00：0100：0101：011：10：110：11100：111010：111011；11113333333333 扁扁扁扁扁扁扁扁扁扁 昌titttttttx.4/4/dz4/dzdzdzdz4zdz-哈哈哈哈哈哈哈哈哈哈 的的的的内的的内内的卖 AHH2.1T2.二2.二2,二 AHH2.二2,二 AHH AHH 3 821745736 8 卷 713821918 5AZ-0550563128 津-200121000 0 牧.znA 000000000 0 HH4 点点点点点点点点点点任-RRRRRRRREE按 什叶叶叶4管4.此哈夫曼树的层序遍历结果:c:*F:VC6.0vclSDev98lyProjectslyBinaryTreeDebuglyBinaryTree.exe*n|x第1层:1.0000 第2层:0.4208 0.5792 第3层:0.2078 0.2130 0.2524 0.3268 第4层:0.1043 0.108?0.1615 0.1653 第5层:0.0512 0.0531 0.0?96 0.0858 第6层:0.0397 0.0399 第7层:0.0113左儿子：0.4208右儿子：0.5792 左儿子：0.2078右儿子：0.2130 左兀字：0.2524右兀字：0.3268左儿子：01043右儿子：0，087 左儿子：01615右儿子1653 左儿子：0.0512右儿子：0.0531左儿子：0.0796右儿子：0.0858左儿子右儿子：0.0399左儿子右儿子:00286二1五、算法复杂度及性能1.本程序中空间复杂度不变的都是节点的个数。(9,遍历的时间复杂度也是节点的个数双通，递归遍历的空间复杂度等于树的高度log2(n+l)o 生成哈夫曼树的时间复杂度是数。2.本程序用指针实现，对节点个数的限制小，时间上不如数组实现的快。3.用void*实现对不同数据类型的兼容，使用方便，而且只需改变默认数据 类型即可改变节点的数据域的数据类型。六、源代码Binary Tree.h:#include nQueue.hn#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#define DEFAULTNUMNODE 2*DEFAULTNUMLEAF-1#define HUFFMANNODERANGE 1000定义哈夫曼树叶节点的范围#define HUFFMANTREE 1#define INNERTREE 0#define MAXSTACK 1000class Binary Tree(public:int Create(int n);/*函数功能：随机生成一棵有n个节点的二叉树，并将其作为对象内部默 认树；参数：n代表节点数；返回值：-1表示生成失败，1表示生成成功。*/int GetHeightQ;/*函数功能：得到对象内部默认树的高度返回值：该树的高度。*/int GetNumNodeQ;/*函数功能:得到对象内部默认树的节点数返回值：该树的节点数。*/int GetNumLeaf();/*函数功能：得到对象内部默认树的叶节点数返回值：该树的叶节点数。*/void Traversal(int mode,int which);/*函数功能：遍历对象内部的一棵树；参数：mode表示遍历方式，可以取以下值：PREORDER 先序遍历，INORDER 中序遍历，POSTORDER 后序遍历，FLOORORDER 层序遍历；which表示遍历哪棵树，可以取以下值：INNERTREE 遍历内部默认树，HUFFMANTREE 遍历生成的哈夫曼树；*/void Insert(DefType dataO);/*函数功能:将节点dataO随即插入默认树中；参数：dataO代表节点标识。*/int Delete(DefType dataO);/*函数功能：删除节点dataO；参数：dataO代表节点标识；返回值：-1表示未找到节点，删除失败；0表示删除成功。*/int Find(DefType dataO,int&Floorth,int&FloorNumth);/*函数功能：查找节点dataO,并得到其所在层数和在该层的位置；参数：dataO 代表节点标识；&Floorth 存储得到的层数，若小于0表示查找失败；&FloorNumth存储节点在其层的位置，若小于0表示查找失 败；返回值：-1表示未找到，-2表示没有默认树导致查找失败，1表示查找成功。*/DefType GetFather(DefType dataO);/*函数功能：得到节点dataO的父节点；参数：dataO代表节点标识；返回值：父节点标识。*/void HuffmanCreate();/*函数功能：随机生成一棵有10个叶节点的哈夫曼树。*/void ShowHuffmanCode();/*函数功能：输出哈夫曼树各叶节点的哈夫曼编码。*/void UpdateInnerTree();/*函数功能：更新内部默认树，即将新生成的哈夫曼树作为内部默认树。void ClearInnerTree();/*函数功能：删除对象内部默认的树。*/int Leaf Amount;存储树的叶节点数。int NodeAmount;存储树的节点数。int Height;存储树的高度。BinaryTreeQ;virtual Binary Tree。；private:BN*NewBN(DefType*data);/*函数功能：新建一个节点；参数：data 代表此节点所具有的标识;返回值：此节点的指针。*/int MaxHeight(BN*now);/*函数功能：得到默认树的高度；参数：now代表当前节点指针;返回值：以当前节点为根的树的高度。*/int NumNode(BN*now);/*函数功能：得到默认树的节点数;参数：now 代表当前节点指针；返回值：当前节点及其下所有节点的数目。*/int NumLeaf(BN*now);/*函数功能：得到默认树的叶节点数；参数：now 代表当前节点指针；返回值：当前节点及其下所有节点中的叶节点数目。*/void PreOrder(BN*now);/*函数功能：先序遍历默认树；参数：now 代表当前节点指针。*/void InOrder(BN*now);/*函数功能:中序遍历默认树；参数：now 代表当前节点指针。*/void PostOrder(BN*now);/*函数功能：后序遍历默认树；参数：now 代表当前节点指针。*/void FloorOrder(BN*root);/*函数功能：层序遍历默认树；参数：root 代表此树根节点的地址。*/BN*FindInOrder(DefType data。,BN*now);/*函数功能：得到某节点的指针；参数：dataO代表所查找的节点表示；now 代表当前节点指针；返回值：NULL表示未找到该节点，否则为该节点的指针。*/void DeleteThis(BN pos);/*函数功能：删除某一节点并调整树的结构；参数：pos代表所删除的节点指针。*/int ReArrange(BN*now);/*函数功能：移动某节点后调整树的结构；参数：now 代表当前节点指针；返回值：1表示调整的节点为叶节点，0表示调整节点不是叶节点。*/BN*GetFather(BN*ThisNode,BN*now);/*函数功能：递归得到某一节点的父节点；参数：ThisNode代表所查找的节点指针；now 代表当前节点指针；返回值：NULL表示未找到该节点，其他情况为找到的父节点指针。*/void PostShowHuffmanLeaf(BN*now,int Stack,int&top);/*函数功能：后序遍历哈夫曼树所有叶节点；参数：now 代表当前节点指针；Stack存储路径用到的栈；&top 栈顶游标。*/void DeleteA11(BN*now);/*函数功能：删除对象内部默认的树及所有数据;参数：now 代表当前节点指针。*/BN*Root;存储对象内部默认树的根节点BN*RootAll;存储树根的父节点BN*HuffmanBTRoot;存储哈夫曼树的根节点)；BinaryTree.cpp:/Binary Tree.cpp:implementation of the Binary Tree class./#include nstdafx.hn#include BinaryTree.h/Construction/DestructionBinaryTree:BinaryTree()(srand(time(O);RootAll=NewBN(new DefType(O);Root=NULL;HuffmanBTRoot=NULL;Height=0;LeafAmount=0;Node Amount=0;Binary Tree:-BinaryTree()Delete All(Root);)int BinaryTree:Create(int n)(Node Amount=n;if(nLCh=Root;while(nOLCh=New;que.Del();else if(1=flag)01d-RCh=New;que.Del();)else(if(Old-LCh=NULL)Old-LCh=New;else(Old-RCh=New;que.DelQ;)return 1;)void Binary Tree:Traver sal(int modejnt which)if(INNERTREE=which)(if(PREORDER=mode)PreOrder(Root);if(INORDER=mode)InOrder(Root);if(POSTORDER=mode)PostOrder(Root);if(FLOORORDER=mode)FloorOrder(Root);)else(if(PREORDER=mode)PreOrder(HuffmanB TRoot);if(INORDER=mode)InOrder(HuffmanBTRoot);if(POSTORDER=mode)PostOrder(HuffmanBTRoot);if(FLOORORDER=mode)FloorOrder(HuffmanB TRoot);)void Binary Tree:PreOrder(BN*now)(if(now!=NULL)(cout.setf(ios:fixed);coutsetprecision(4)(DefType)now-dataendl;PreOrder(now-LCh);PreOrder(now-RCh);)void BinaryTree:InOrder(BN*now)(if(now!=NULL)InOrder(now-LCh);cout.setf(ios:fixed);coutdataendl;InOrder(now-RCh);)void Binary Tree:PostOrder(BN*now)|if(now!=NULL)(PostOrder(now-LCh);PostOrder(no w-RCh);cout.setf(ios:fixed);coutsetprecision(4)*(DefType*)now-dataendl;)void Binary Tree:FloorOrder(BN*root)(Queue que;que.Add(root);int nO=O;inti;for(;)(n0+;cout v v第”v vnO v v 层“v v”:“v vendl;int rearO=que.rear;for(i=que.front;i=rearO;i+)(BN*Now=(BN)que.GetFront();cout.setf(ios:fixed);coutdatan n;if(Now-LCh!=NULL)coutH 左 儿:nsetprecision(4)*(DefType*)Now-LCh-datan n;if(Now-RCh!=NULL)coutn 右 儿-F：nsetprecision(4)*(DefType*)Now-RCh-datan n;coutendl;if(Now-LCh!=NULL)que.Add(Now-LCh);if(Now-RCh!=NULL)que.Add(Now-RCh);que.DelQ;if(que.Empty()=1)break;)BN*Binary Tree:NewBN(DefType*data)(BN*New=new BN;New-data=data;New-LCh=NULL;New-RCh=NULL;return New;)void Binary Tree:DeleteAll(BN*now)if(now!=NULL)DeleteAll(now-LCh);DeleteAll(now-RCh);delete now-data;delete now;)int Binary Tree: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;elsereturn 1+right;elsereturn 0;)int BinaryTree:GetNumNode()(return Node Amount=NumNode(Root);)int BinaryTree:NumNode(BN*now)(if(now!=NULL)return 1+NumNode(now-LCh)+NumNode(now-RCh);elsereturn 0;)int BinaryTree:GetNumLeaf()return Leaf Amount=NumLeaf(Root);)int BinaryTree:NumLeaf(BN*now)if(now-LCh=NULL)&(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 Binary Tree:Insert(DefType dataO)BN*New=NewBN(new DefType(dataO);BN*now=Root;if(Root=NULL)(Root=New;return;)int flag;for(;)(flag=rand()%2;if(0=flag)(if(now-LCh=NULL)(now-LCh=New;N odeAmount+;break;elsenow=now-LCh;)else(if(now-RCh=NULL)(now-RCh=New;N odeAmount+;break;)elsenow=now-RCh;)int Binary Tree:Find(DefType dataOjnt&Floorth,int&FloorNumth)(if(Root=NULL)(Floorth=-1;FloorNumth=-1;return-2;Queue que;que.Add(Root);int n0=0;int i;for(;)(n0+;int rearO=que.rear;int frontO=que.front;BN*Now;for(i=frontO;idata=(Floorth=nO;FloorNumth=i-frontO+1;dataO)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;)int BinaryTree:Delete(DefType dataO)(BN*pos=FindInOrder(dataO,Root);if(NULL=pos)return-1;elseDeleteThis(pos);return 0;)BN*Binary Tree:FindlnOrder(DefType dataO,BN*now)(if(now!=NULL)if(*(DefType*)no w-data=dataO)return now;else(BN*left=FindInOrder(dataO,now-LCh);if(left=NULL)BN*right=FindInOrder(dataO,now-RCh);return right;elsereturn left;)elsereturn NULL;void Binary Tree:DeleteThis(BN*pos)(if(pos-LCh!=NULL)(void*temp=pos-data;pos-data=pos-LCh-data;delete temp;if(ReArrange(pos-LCh)=1)pos-LCh=NULL;)else if(pos-RCh!=NULL)(void*temp=pos-data;pos-data=pos-RCh-data;delete temp;if(ReArrange(pos-RCh)=1)pos-RCh=NULL;)else(BN*father=GetFather(pos,Root);if(father!=NULL)(if(father-LCh=pos)father-LCh=NULL;elsefather-RCh=NULL;)delete pos-data;delete pos;)NodeAmount;)int BinaryTree:ReArrange(BN*now)if(now-LCh!=NULL)now-data=now-LCh-data;if(ReArrange(now-LCh)=1)now-LCh=NULL;return 0;)else if(now-RCh!=NULL)(now-data=now-RCh-data;if(ReArrange(now-RCh)=1)now-RCh=NULL;return 0;)else(delete now;return 1;)BN*BinaryTree:GetFather(BN*ThisNode,BN*now)if(now!=NULL)if(now-LCh=ThisNode)ll(now-RCh=ThisNode)return now;else(BN*left=GetFather(ThisNode,now-LCh);if(left=NULL)(BN*right=GetFather(ThisNode,now-RCh);if(right=NULL)return NULL;elsereturn right;)elsereturn left;)elsereturn NULL;DefType BinaryTree:GetFather(DefType dataO)(BN*pos=FindInOrder(dataO,Root);if(pos=NULL)return-1;BN*father=GetFather(pos,RootAll);return*(DefType*)father-data;)void BinaryTree:HuffmanCreate()(BN*LinkDEFAULTNUMNODE;DefType Data DEFAULTNUMNODE;int HashHUFFMANNODERANGE+1;int i,j,k;int Leaf=DEFAULTNUMLEAF;int Range=HUFFMANNODERANGE;int Node=DEFAULTNUMNODE;int flag;DefType sum;for(i=O;i=Range;i+)Hashi=0;for(i=0;iLeaf;i+)(for(;)(DefType temp;temp=(DefType)(rand()%Range+1);if(Hash(int)temp=0)(Hash(int)temp=1;Datai=(int)temp;Linki=NewBN(new DefType(temp);break;sum=0;for(i=0;iLeaf;i+)sum+=Datai;for(i=0;idata/=sum;)flag=0;for(i=Leaf;iNode;i+)(for(j=flag;j=flag+l;j+)(DefType min=Dataj;int minO 二 j;DefType temp;BN*tempo；for(k=j+l;ki;k+)if(DatakLCh=Linkflag;Linki-RCh=Linkflag+1;flag 十二 2;)HuffmanBTRoot=LinkNode-l;void Binary Tree:UpdateInnerTree()if(HuffmanBTRoot!=NULL)(Root=HuffmanBTRoot;RootAll-LCh=Root;GetNumLeaf();GetNumNode();GetHeightQ;)void Binary Tree:ClearInnerTree()(Delete All(Root);Root=NULL;RootAll-LCh=NULL;Height=0;LeafAmount=0;Node Amount=0;)void BinaryTree:ShowHuffmanCode()int StackMAXSTACK;int top=0;PostShowHuffmanLeaf(HuffmanBTRoot,Stack,top);)void BinaryTree:PostShowHuffmanLeaf(BN*now,int Stack jnt&top)if(now-LCh!=NULL)(top+;Stacktop=0;PostShowHuffmanLeaf(now-LCh,Stack,top);top-;)if(now-RCh!=NULL)top+;Stacktop=1;PostShowHuffmanLeaf(now-RCh,Stack,top);)top-；if(now-LChNULL)&(now-RCh=NULL)cout.setf(ios:fixed);coutn 叶 节 点 ndatan的哈夫曼编码为：”;for(int i=l;i=MAXSIZEQUEUE-l)return-1;else if(front=0)front+;rear+;QueueData rear=DataO;return 0;)else(rear+;QueueData rear=DataO;return 0;)int Queue:Del()(if(frontrear)return-1;else(front+;return 0;)void*Queue:GetFront()if(front=0)return NULL;elsereturn QueueDatafront;int Queue:Empty()if(front=rear)return 0;elsereturn 1;Main函数：#include stdafx.h”#include nBinaryTree.hnint main(int argc,char*argv)(Binary Tree bt;for(;)(输出操作界 面system(nclsn);coutn-二叉树 ADT 及哈夫曼编码-nendl;coutn请输 入操作：vvendl;coutH-华 丽 的 分 割 线-nendl;coutn随机生成一棵二叉树，请输入1 vvendl;coutn得到树的高度，请输入2Nvendl;coutn得到树的节点数，请输入3endl;coutn得到树的叶子数，请输入4 nendl;coutn遍历树，请输入5endl;coutn插入节点，请输入6vendl;coutn 册I 除节点，请输入7vendl;coutn查找节点，请输入8”vvendl;响应用户操作int operation;cinoperation;int nO;intmode,which;intfloorth,floornumth;int flag;DefTypeflagO;DefTypedataO;system(nclsn);switch(operation)(case 1:coutn请输入要生成的树节点数 vvendl;cinnO;bt.Create(nO);coutvv”生成成功 o nendl;break;case 2:度是：nbt.GetHeight()endl;点数是：nbt.GetNumNode()endl;节点数是：vvbt.GetNumLeaf。vvendl;遍历方式611(11；先序遍历请输入Ikvendl;中序遍历请输入2nendl;后序遍历请输入3nendl;层序遍历请输入4nendl;coutn树的高break;case 3