using System;

​

public struct HFMT

{

    public int weight;

    public int lchild;

    public int rchild;

    public int parent;

}

​

public class HuffmanTree

{

    private const int MAX = 100;

​

    public static void Main()

    {

        int n;

        HFMT[] HF = new HFMT[MAX];

        Console.WriteLine("请输入权值的个数：");

        n = int.Parse(Console.ReadLine());

​

        CreateHFMT(HF, n);

        HFMTnode(HF, n);

    }

​

    public static void InitHFMT(HFMT[] HF, int n)

    {

        for (int i = 0; i < 2 * n - 1; i++)

        {

            HF[i].weight = 0;

            HF[i].lchild = -1;

            HF[i].rchild = -1;

            HF[i].parent = -1;

        }

​

        for (int i = 0; i < n; i++)

        {

            Console.WriteLine("请输入第{0}个结点的权值：",i+1);

            HF[i].weight = int.Parse(Console.ReadLine());

        }

    }

​

    public static void Min(HFMT[] HF, int n, ref int p, ref int r, int j)

    {

        int Min1 = 9999;

        int Min2 = 9999;

​

        for (int i = 0; i < j; i++)

        {

            if (HF[i].parent == -1 && HF[i].weight < Min1)

            {

                Min1 = HF[i].weight;

                p = i;

            }

        }

​

        for (int i = 0; i < j; i++)

        {

            if (HF[i].parent == -1 && HF[i].weight < Min2 && HF[i].weight > Min1)

            {

                Min2 = HF[i].weight;

                r = i;

            }

        }

    }

​

    public static void CreateHFMT(HFMT[] HF, int n)

    {

        int p = 0, r = 0;

        int i;

        InitHFMT(HF, n);

        for (i = n; i < 2 * n - 1; i++)

        {

            Min(HF, n, ref p, ref r, i);

            HF[p].parent = i;

            HF[r].parent = i;

            HF[i].lchild = HF[p].weight;

            HF[i].rchild = HF[r].weight;

            HF[i].weight = HF[i].lchild + HF[i].rchild;

        }

    }

​

    public static void HFnode(HFMT[] HF, int i, int j)

    {

        j = HF[i].parent;

        if (HF[j].rchild == HF[i].weight)

        {

            Console.Write("1");

        }

        else

        {

            Console.Write("0");

        }

        if (HF[j].parent != -1)

        {

            i = j;

            HFnode(HF, i, j);

        }

    }

    public static void HFMTnode(HFMT[] HF, int n)

    {

        int a, i, j = 0;

        Console.WriteLine("\n输入的权值所对应的哈夫曼代码为：");

        for (i = 0; i < n; i++)

        {

            a = i;

            Console.Write("{HF[i].weight}的编码为：");

            HFnode(HF, i, j);

            Console.WriteLine();

            i = a;

        }

    }

}

​

​