哈夫曼算法建立最优二叉树.doc

#include#include#include#include#define MAX_NUMBER_OF_TREE_NODES 20/树的结点的类型定义typedef structunsigned int weight;unsigned int parent,lchild,rchild;HTNode,*HuffmanTree;/子函数的声明部分void InitTreeNode(HTNode);void CinWeightForTreeNode(HTNode);void GiveOrderForTreeNode(HTNode);void CopyTreeNodeOrTree(HTNode,HTNode);int main()/定义将要用于构造哈弗曼树的结点HTNode TreeNodesMAX_NUMBER_OF_TREE_NODES+1;/调用函数初始化数组结点InitTreeNode(TreeNodes);/由用户输入各个结点的权值CinWeightForTreeNode(TreeNodes);/对数组中的结点进行排序GiveOrderForTreeNode(TreeNodes);return true;/初始化结点值，使全部为NULLvoid InitTreeNode(HTNode *treenodes)int i=1/数组的首结点用来存数一些信息，如weight域用来存储节点的多少/突然想到了一个好处就是：等会我们几点不断减少的过程中可以用首结点的/weight来指示剩余结点的数目，做访问数组元素的界限treenodes0.weight=MAX_NUMBER_OF_TREE_NODES;treenodes0.lchild=NULL;treenodes0.parent=NULL;treenodes0.rchild=NULL;for(;i=MAX_NUMBER_OF_TREE_NODES;i+)treenodesi.weight=0;treenodesi.lchild=0;treenodesi.rchild=0;treenodesi.parent=0;void CinWeightForTreeNode(HTNode *treenodes)int i=1;cout请输入每个结点的权值：endl;for(;i=MAX_NUMBER_TREE_NODES;i+)cout第i个结点的权值是：treenodesi.weight;void GiveOrderForTreeNode(HTNode *treenodes)HTNode TemporarySave;/CopyTreeNodeOrTree(treenodes1,TemporarySave);int i=2;int count=1;int j=treenodes0.weight;for(;itreenodesi.weight)count=i;CopyTreeNodeOrTree(treenodescount,TemporarySave);for(;ij;i+)CopyTreeNodeOrTree(treenodesi,treenodesi+1)CopyTreeNodeOrTree(treenodesweight,TemporarySave);treenodes0.weight-;void CopyTreeNodeOrTree(HTNode Node1,HTNode Node2)/功能描述：用Node1的值去修改Node2的值Node2.lchild = Node1.lchild;Node2.parent = Node1.parent;Node2.parent = Node1.rchild;Node2.weight = Node1.weight;/检测左右孩子是否为空，如果不为空，则进行再次深度复制/采用递归调用执行if(Node1.lchild) CopyTreeNod