霍夫曼树程序.doc.doc

//演示程序二十六：“霍夫曼”树 #includeiostream.h #includestdlib.h const int DefaultSize = 20; /* 声明“扩充二叉树”的类 */ template class Type class ExtBinTree; //定义“扩充二叉树”的结点 template class Type class Element { friend class ExtBinTreeType; //友元类 private: Type data; /* 数据域 指针域 */ ElementType * leftChild, * rightChild; public: //构造函数：一个叶子结点，数据域空 Element ( ) : leftChild (NULL), rightChild (NULL) { } //构造函数：一个非叶子结点，数据域赋值 Element ( Type item, ElementType *left = NULL, ElementType *right = NULL ) : data (item), leftChild (left), rightChild (right) { } //修改结点数据域的值 void SetData ( const Type item ) { data = item; } //修改结点的左孩子指针 void SetLeft ( ElementType * L ) { leftChild = L; } //修改结点的右孩子指针 void SetRight ( ElementType * R ) { rightChild = R; } //返回结点数据域的值 Type GetData ( ) { return data; } }; //定义“扩充二叉树”的类 template class Type class ExtBinTree { private: ElementType *root; //二叉树的根指针 public: //无参构造函数 ExtBinTree() { root= new ElementType; } //构造函数：把两棵扩充二叉树合并成 //一棵扩充二叉树。根的数据域为两棵子 //树的数据域之和。左右指针分别指向 //两棵子树。 ExtBinTree (ExtBinTreeType bt1, ExtBinTreeType bt2 ) { root= new ElementType( bt1.GetRootData( ) +bt2.GetRootData( ), bt1.root,bt2.root); } //成员函数：给根结点赋值 void SetRootData(Type x, ElementType *left, ElementType *right) { root-SetData(x); root-SetLeft(left); root-SetRight(right); } //返回根结点数据域值 Type GetRootData( ) { return root-GetData(); } //返回根结点地址 Element Type * Getroot( ) { return root; } //前序遍历递归输出二叉树 void PreOrder(Element Type *p ) const { if ( p != NULL ) { //输出根结点数据域 cout p-data ; //递归输出p的左子树 PreOrder ( p-leftChild ); //递归输出p的右子树 PreOrder ( p-rightChild ); } } //中序遍历递归输出二叉树 void InOrder(Element Type *p ) const { if ( p != NULL ) { InOrder ( p-leftChild ); cout p-data ; InOrder ( p-rightChild ); } } }; /********** 定义“最小堆”********/ template class Type class MinHeap { private: Type * heap; //存放最小堆元素的数组 int CurrentSize; /