数据结构（哈夫曼树）

系统管理员 2022-06-05 03:45 150阅读 0赞

**几个基本概念**：  
路径：从树中的一个结点到另一个结点之间的分支构成这两个结点间的路径。  
路径长度：路径上的分支数。  
树的路径长度：从树的根结点到每个结点的路径长度之和。在结点数目相同的二叉树中，完全二叉树的路径长度最短。  
结点的权：在一些应用中，赋予树中结点的一个有实际意义的数。  
结点的带权路径长度：从该结点到树的根结点的路径长度与该结点的权的乘积。  
树的带权路径长度：树中所有叶子结点的带权路径长度之和  
哈夫曼树又叫最优二叉树，值得是对于一组具有确定权值的叶子结点的具有最小带权路径长度的二叉树。  
**构造哈夫曼树的方法**：  
1>根据给定的n个权值\{w1,w2,…,wn\}，构造n棵只有根结点的二叉树集合F=\{T1,T2,…,Tn\}；  
2>从集合F中选取两棵根结点的权最小的二叉树作为左右子树，构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树根结点权值之和。  
3>在集合F中删除这两棵树，并把新得到的二叉树加入到集合F中；  
4>重复上述步骤，直到集合中只有一棵二叉树为止，这棵二叉树就是哈夫曼树。  
**结点类**：

class NewNode
        {
            private int weight;//权值
            private int lChild;//左孩子节点
            private int rChild;//右孩子结点
            private int parent;//双亲节点
            public int Weight
            {
                get { return weight; }
                set { weight = value; }
            }
            public int LChild { get { return lChild; } set { lChild = value; } }
            public int RChild { get { return rChild; } set { RChild = value; } }
            public int Parent { get { return parent; } set { parent = value; } }
    
            public NewNode()
            {
                weight = 0;
                lChild = -1;
                rChild = -1;
                parent = -1;
            }
    
            public NewNode(int w, int l, int r, int p)
            {
                weight = w;
                lChild = l;
                rChild = r;
                parent = p;
            }
        }

**哈夫曼树的构造**：

class HuffmanTree
        {
            //哈发曼树可用于哈夫曼编码
            private NewNode []data;//子树的集合
            private int leafNum;//结点数目
            public NewNode this[int index] { get { return data[index]; } set { data[index] = value; } }
    
            public int LeafNum { get { return leafNum; } set { leafNum = value; } }
    
            public HuffmanTree(int n)
            {
                data=new NewNode[2*n-1];
                leafNum = n;
            }
    
            public void CreateHuffmanTree()
            {
                int m1, m2;//所有树中的两个最小权值
                int temp1, temp2;//最小权值的两树的位置
                for (int i = 0; i < leafNum; i++)
                {
                    data[i].Weight = Console.Read();
                }
                for (int i = 0; i < leafNum-1; i++)
                {
                    m1 = m2 = Int32.MaxValue;
                    temp1 = temp2 = 0;
                    for (int j = 0; j < leafNum+i; j++)
                    {
                        if (data[j].Weight<m1&&data[j].Parent==-1)
                        {
                            m2 = m1;
                            temp2 = temp1;
                            m1 = data[j].Weight;
                            temp1 = j;
                        }
                        else if (data[j].Weight < m2 && data[j].Parent == -1)
                        {
                            temp2 = j;
                            m2 = data[j].Weight;
                        }
                    }
                    data[temp1].Parent = data[temp2].Parent = leafNum + i;
                    data[leafNum + i].Weight = data[temp1].Weight + data[temp2].Weight;
                    data[leafNum + i].LChild = temp1;
                    data[leafNum + i].RChild = temp2;
                }
            }
        }