第07篇2 自定义数据类型.pptVIP

例7-5 设有字符集{A, B, C, D}，各字符在电文中出现的次数集为{1, 3, 5, 7}，设计各字符的哈夫曼编码。 程序设计如下： #include iostream.h #include stdlib.h ? const int MaxValue = 10000; //初始设定的权值最大值 const int MaxBit = 4; //初始设定的最大编码位数 const int MaxN = 10; //初始设定的最大结点个数 ? #include HaffmanTree.h void main(void) { int i, j, n = 4; int weight[] = {1,3,5,7}; HaffNode *myHaffTree = new HaffNode[2*n+1]; Code *myHaffCode = new Code[n]; if(n MaxN) { cout 定义的n越界，修改MaxN! endl; exit(0); } Haffman(weight, n, myHaffTree); HaffmanCode(myHaffTree, n, myHaffCode); //输出每个叶结点的哈夫曼编码 for(i = 0; i n; i++) { cout Weight = myHaffCode[i].weight Code = ; for(j = myHaffCode[i].start+1; j n; j++) cout myHaffCode[i].bit[j]; cout endl; } } 7.8 树与二叉树的转换 1.树转换为二叉树 树转换为二叉树的方法是： （1）树中所有相同双亲结点的兄弟结点之间加一条连线。 （2）对树中不是双亲结点第一个孩子的结点，只保留新添加的该结点与左兄弟结点之间的连线，删去该结点与双亲结点之间的连线。 （3）整理所有保留的和添加的连线，使每个结点的第一个孩子结点连线位于左孩子指针位置，使每个结点的右兄弟结点连线位于右孩子指针位置。 A B C D E F G A B C D E F G A B C D E F G A B E F C D G ( a ) ( b ) ( c ) ( d ) 树转换为二叉树的过程 （a）树;（b）相临兄弟加连线;（c）删除双亲与非第一个孩子连线;（d）二叉树 2.二叉树还原为树 二叉树还原为树的方法是： （1）若某结点是其双亲结点的左孩子，则把该结点的右孩子、右孩子的右孩子……都与该结点的双亲结点用线连起来。 （2）删除原二叉树中所有双亲结点与右孩子结点的连线。 （3）整理所有保留的和添加的连线，使每个结点的所有孩子结点位于相同层次高度。 二叉树还原为树的过程 （a）二叉树;（b）双亲与非第一个孩子加连线; （c）删除结点与右孩子连线;（d）树 A B E F C D G A B E F C D G A B E F C D G A B C D E F G ( a ) ( b ) ( c ) ( d ) * * 7.4 二叉树类 二叉树类设计如下： template class T class BiTree { private: BiTreeNodeT *root; //根结点指针 ? void Destroy(BiTreeNodeT* t); void PreOrder(BiTreeNodeT* t, void (*Visit)(T item)); void InOrder(BiTreeNodeT* t, void (*Visit)(T item)); void PostOrder(BiTreeNodeT* t, void (*Visit)(T item)); public: BiTree(void):root(NULL){}; //构造函数 ~BiTree(void){}; //析构函数 ? //构造二叉树 void MakeTree(const T item, BiTreeT left, BiTreeT right); void Destroy(void); //撤消二叉树 ? void PreOrder(void (*Visit)(T item)); //前序遍历 void InOrder(void (*Visit)(T item)); //中序遍历 void PostOrder(void (*Visit)(T item)); //后序遍历 }; template class T void BiTreeT::MakeTree(const T it