治疗白癜风医院哪里好 http://www.bdfyy999.com/index.html什么是赫夫曼树？
赫夫曼树(HuffmanTree)是指给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小。哈夫曼树（也称为最优二叉树）是带权路径长度最短的树，权值较大的结点离根较近。
publicclassHNodeT{publicHNode(){data=default(T);weight=0;leftNode=null;rightNode=null;}publicHNode(Tval){data=val;weight=0;leftNode=null;rightNode=null;}///summary///权重////summarypublicintweight{get;set;}///summary///内容////summarypublicTdata{get;set;}///summary///左树////summarypublicHNodeTleftNode{get;set;}///summary///右树////summarypublicHNodeTrightNode{get;set;}}
///summary///赫夫曼树////summary///typeparamname="T"/typeparampublicclassHTreeT{///summary///树的头结点////summarypublicHNodeThead{get;set;}///summary///构造函数////summary///paramname="val"/parampublicHTree(Tval){head=newHNodeT(val);}publicHTree(){head=newHNodeT();}///summary///构建树结构////summary///paramname="list"/parampublicvoidbuild(ListTlist){//判断是否能构建树结构if(list==null
list.Count2)thrownewArgumentOutOfRangeException("paramserror");//分组统计ListHNodeTnodes=newListHNodeT();nodes.AddRange(fromminlistgroupmbymintogselectnewHNodeT{data=g.Key,weight=g.Count()});//排序nodes=nodes.OrderBy(i=i.weight).ToList();for(inti=1;inodes.Count;i++){HNodeTparentNode=newHNodeT();if(i==1){//先取最小的两个节点parentNode.leftNode=nodes[0];parentNode.rightNode=nodes[1];parentNode.weight=nodes[0].weight+nodes[1].weight;}else{//依次取节点构建树if(head.weight=nodes.weight){parentNode.leftNode=head;parentNode.rightNode=nodes;}else{parentNode.rightNode=head;parentNode.leftNode=nodes;}parentNode.weight=head.weight+nodes.weight;}head=parentNode;}}///summary///先序遍历////summary///paramname="index"/parampublicvoidPreorderTraversal(HNodeTnode){//递归的终止条件if(head==null){Console.WriteLine("当前树为空");return;}if(node!=null){if(node.data!=null)Console.WriteLine($"{node.data}{node.weight}");PreorderTraversal(node.leftNode);PreorderTraversal(node.rightNode);}}}
测试代码：
Liststringlist=newListstring(){"A","B","B","C","C","C","D","D","D","D","E","E","E","E","E"};HTreestringtree=newHTreestring();tree.build(list);tree.PreorderTraversal(tree.head);
打印结果：
A1B2C3D4E5
用这个例子现在我们看下构建的二叉树结构：
温暖如太阳
