数据结构---二叉树的详解

桃扇骨 2022-07-15 04:57 153阅读 0赞

*前言*  
The only thing that overcomes hard luck is hard word.  
Name:Willam  
Time:2017/2/22

## 1、名词解释 ##

树是使用了递归定义的数据结构，树的子树还是树，其结构如下图所示：  
![这里写图片描述][SouthEast]

*  度：结点拥有的子树数目，例如上图结点A的度为3，结点E的度为0
 *  叶子或终端结点：度为0的结点（没有子树的结点）
 *  树的度：各个结点中度的最大值
 *  孩子：结点的子树的根，称为根的孩子
 *  层次：根的层次为0，根的孩子为1，以此类推
 *  深度：树中结点的最大层次，称为树的深度

## 2、二叉树的定义 ##

二叉树是一种每个结点至多只有两个子树（即二叉树的每个结点的度不大于2），并且二叉树的子树有左右之分，其次序不能任意颠倒。

**二叉树的性质**

*  在二叉树的第i层，至多有2^(i-1)个结点
 *  深度为k的二叉树至多有：(2^k)-1个结点，其实这个结果就是一个等比数列的求和得到的。
 *  对任意一颗二叉树，如果其叶子结点数量为：n0,度为2的结点数为：n2，则：n0=n2+1
    
    注释：这里对第三个性质做一个解释，首先我们都知道一个二叉树每个结点都是由度为0，1，2，三种情况，我们这里假设，二叉树有n个结点，其中度为1的结点数为：n1，于是由已知条件可知：n=n1+n0+n2;  
    好，现在，我们在从另外一个角度想，我们二叉树有B条边，假设这些边都是从父亲结点指向它的孩子，那么我们会发现除了根结点外，其他结点都是有一天边的，所以：n=B+1,其中这些边都是由度为1和2的结点射出来的，所以：B=n1+2\*n2,因此：n=n1+2\*n2+1.所以，联立等式：n1+2\*n2+1=n1+n0+n2,我们可以得到一个等式：n0=n2+1;
 *  具有n个结点的完全二叉树的深度为：\[log2n\]+1，其中\[log2n\]+1是向下取整。  
    注释：首先我们先定义满二叉树：一颗深度为k且结点数为：（2^k）-1的二叉树，我们称为满二叉树，然后，我们对满二叉树进行编号，从根结点开始，从左往右，从上到下。然后就是可以定义一个完全二叉树：深度为k，结点数为n的二叉树，而且，每一个结点的位置都和深度为k的完全二叉树中编号为1到n的结点一一对应，我们称为完全二叉树。如下图所示：  
    ![这里写图片描述][SouthEast 1]
    
    然后，我们现在就可以解释第四个性质了，假设我们的深度为k，由我们的完全二叉树的定义，我们可以知  
    道：2^(k-1)-1< n <=(2^k)-1 即：2^(k-1)<=n<(2^k)，所以：k-1 < = \[log2n\] < k,因为k是整数，所以k=\[log2n\]+1，其中\[log2n\]+1是向下取整。
 *  有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：  
    　若i为结点编号则 如果i>1，则其父结点的编号为\[i/2\]，\[i/2\]是往下取整的；  
    　如果2i<=N，则其左儿子（即左子树的根结点）的编号为2i；若2i>N，则无左儿子；  
    　如果2i+1<=N，则其右儿子的结点编号为2i+1；若2i+1>N，则无右儿子。  
    　如果不明白，你可以画个完全二叉树，然后，对它的结点进行编号，你就明白了。

## 3、二叉树的存储结构 ##

**（1）顺序存储结构：**  
顺序存储结构其实就是在一个连续存储单元里，从根结点开始，像对完全二叉树编号的顺序一样，把我们的二叉树的内容存储在一个一维数组中，一般顺序存储结构是拿来存储完全二叉树的，但是也可以拿来存储一般的二叉树，只是要按照完全二叉树的规则来编号，如果没有的就存0，如下图所示：  
![这里写图片描述][SouthEast 2]

**（2）链式存储结构（比较常用一种存储结构）**

由二叉树的定义可知道，我们链式存储结构至少包含三个部分：数据域和两个指针域，一个指向左孩子，另一个指向右孩子，我们称这种链表为二叉链表，另外一种就是我们还可以添加一个指针域，指向其父亲结点，我们称为三叉链表，如下图所示：  
![这里写图片描述][SouthEast 3]

## 4、 遍历二叉树 ##

所谓的遍历其实就是按照某种搜索路径，遍历树中的每个结点。我们都知道二叉树由三个基本的单元组成：根结点、左子树、右子树，所以遍历整个二叉树就是遍历二叉树的三个基本单元，根据随机组合的原理，可以产生6中遍历方案：DLR、LDR、LRD、RDL、RLD、LRD,另外，遍历的时候，一般要求先左后右的，所以我们只会选择前三种遍历方案。

*  先序遍历（DRL）  
    （1）先访问根结点  
    （2）先序遍历左子树  
    （3）先序遍历右子树
 *  中序遍历（LDR）  
    （1）先中序遍历左子树  
    （2）访问根结点  
    （3）中序遍历右子树
 *  后序遍历（LRD）  
    （1）后序遍历左子树  
    （2）后序遍历右子树  
    （3）访问根结点

具体的例子如下：  
![这里写图片描述][SouthEast 4]  
“遍历”是二叉树的基本操作，可以在遍历过程中对结点进行各种操作，当然也包括在遍历过程中生成结点，而且我们一般是采用先序遍历的方式，来生成二叉树

具体的代码实现如下：

在实现算法前，我们先给定我们结点的结构，而且二叉树采用二叉链表形式表示：

//结点的结构
    struct Tree_Node
    {
        //每个结点的数据
        char data;
        //左子树
        Tree_Node * left;
        //右孩子
        Tree_Node * right;
    };

*  构造二叉树的代码

//按照先序遍历的方式，构建我们的二叉树,输入的时候，我们要按照完全二叉树的形式输入，结点为空的位置，输入“#”
    void createTree(Tree_Node * & t)
    {
        char str;
        cin>>str;
        if(str=='#')
        {
            t=NULL;
        }
        else
        {
            t=new Tree_Node; //为t开辟空间
            t->data=str;
            createTree(t->left); //生成左子树
            createTree(t->right); //生成右子树
        }
    }

*  先序遍历

//先序遍历，递归实现
    void PreorderTraverse(Tree_Node * T)
    {
        if(T){
            if(T->data!='#')
           cout<<T->data<<" ";   //访问根结点
           PreorderTraverse(T->left);  //访问左子树
           PreorderTraverse(T->right);  //访问右子树
        }
    }
    
    //非递归实现,思路：其实一般要想通过非递归的方式实现递归方式的算法，一般都是要使用栈。
    //首先我们的循环条件是：结点不为空或者栈不为空。然后是先把根结点加入桟中，然后，遍历左子树，当左子树遍历完后，栈顶元素为刚刚的根结点，然后，让根结点出栈，遍历右子树
    void PreorderTraverse_no_recursive(Tree_Node * T)   
    {
        stack<Tree_Node*> s;
        Tree_Node * p=T;
            //栈不为空或者T不为空时，循环继续
        while(p || !s.empty())
        {
            if(p!=NULL)  
            {
                s.push(p); //根结点入栈
                if(p->data!='#')//访问根结点
                cout<<p->data<<' ';
                p=p->left; //先遍历左子树
            }
            else
            {
                p=s.top(); //根结点出栈
                s.pop();   //
                p=p->right;//遍历右子树
            }
        }
    }

*  中序遍历

//递归实现中序遍历
    void InorderTraverse(Tree_Node * T)
    {
        if(T)
        {
            InorderTraverse(T->left); //中序遍历左孩子     
            if(T->data!='#')
            cout<<T->data<<" ";       //访问根结点
            InorderTraverse(T->right); //中序遍历右孩子
        }
    }
    
    //非递归实现中序遍历，思路：
    //思路：T是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。 
    //先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T->data，再中序遍历T的右子树。 
    void InorderTraverse_recursive(Tree_Node * T)
    {
        stack<Tree_Node*> s;
        Tree_Node * p=T;
            //栈不为空或者T不为空时，循环继续
        while(p || !s.empty())
        {
            if(p!=NULL)  
            {
                s.push(p); //根结点入栈
                p=p->left; //先遍历左子树
            }
            else
            {
                p=s.top(); //根结点出栈
                s.pop();   //
                if(p->data!='#')//访问根结点
                cout<<p->data<<' ';
                p=p->right;//遍历右子树
            }
        }
    }

*  后序遍历

//递归实现后序遍历
    void PostorderTraverse(Tree_Node * T)
    {
        if(T)
        {
            PostorderTraverse(T->left); //访问左子树
            PostorderTraverse(T->right); //访问右子树
            if(T->data!='#')
            cout<<T->data<<" "; //访问根结点
        }
    }
    
    //非递归实现后序遍历
    //思路：我们要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。 
    void PostorderTraverse_recursive(Tree_Node * T)
    {
        Tree_Node * pre; //前一个被访问的结点。
        pre=NULL;
        stack<Tree_Node*> s;
        Tree_Node * cur;  //记录栈顶的结点，
        s.push(T); //先把根结点入栈
        while(!s.empty())
        {
            cur=s.top(); //cur记录的是栈顶的结点
            if((cur->left==NULL && cur->right==NULL) || (pre!=NULL && (pre==cur->left || pre==cur->right)))
            {
                cout<<cur->data<<" "; //满足：不存在左孩子和右孩子；或者存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了
                s.pop();
                pre=cur; //更新pre的值
            }
            else
            {
                if(cur->right!=NULL) //一定是右子树先入栈的，因为这样才可以比左子树后被访问
                s.push(cur->right);
                if(cur->left!=NULL) //左子树入栈
                s.push(cur->left);   
            }
        }
    }

最后，在给个完整代码：

#include<iostream>
    #include<stack>
    using namespace std;
    
    //结点的结构
    struct Tree_Node
    {
        //每个结点的数据
        char data;
        //左子树
        Tree_Node * left;
        //右孩子
        Tree_Node * right;
    };
    
    
    //按照先序遍历的方式，构建我们的二叉树,输入的时候，我们要按照完全二叉树的形式输入，结点为空的位置，输入“#”
    void createTree(Tree_Node * & t)
    {
        char str;
        cin>>str;
        if(str=='#')
        {
            t=NULL;
        }
        else
        {
            t=new Tree_Node; //为t开辟空间
            t->data=str;
            createTree(t->left);
            createTree(t->right);
        }
    }
    
    //先序遍历，递归实现
    void PreorderTraverse(Tree_Node * T)
    {
        if(T){
            if(T->data!='#')
           cout<<T->data<<" ";   //访问根结点
           PreorderTraverse(T->left);  //访问左子树
           PreorderTraverse(T->right);  //访问右子树
        }
    }
    
    //非递归实现,思路：
    //首先我们的循环条件是：结点不为空或者栈不为空。然后是先把根结点加入桟中，然后，遍历左子树，当左子树遍历完后，栈顶元素为刚刚的根结点，然后，让根结点出栈，遍历右子树
    void PreorderTraverse_no_recursive(Tree_Node * T)   
    {
        stack<Tree_Node*> s;
        Tree_Node * p=T;
            //栈不为空或者T不为空时，循环继续
        while(p || !s.empty())
        {
            if(p!=NULL)  
            {
                s.push(p); //根结点入栈
                if(p->data!='#')//访问根结点
                cout<<p->data<<' ';
                p=p->left; //先遍历左子树
            }
            else
            {
                p=s.top(); //根结点出栈
                s.pop();   //
                p=p->right;//遍历右子树
            }
        }
    }
    
    //递归实现中序遍历
    void InorderTraverse(Tree_Node * T)
    {
        if(T)
        {
            InorderTraverse(T->left); //中序遍历左孩子     
            if(T->data!='#')
            cout<<T->data<<" ";       //访问根结点
            InorderTraverse(T->right); //中序遍历右孩子
        }
    }
    
    //非递归实现中序遍历，思路：
    //思路：T是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。 
    //先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T->data，再中序遍历T的右子树。 
    void InorderTraverse_recursive(Tree_Node * T)
    {
        stack<Tree_Node*> s;
        Tree_Node * p=T;
            //栈不为空或者T不为空时，循环继续
        while(p || !s.empty())
        {
            if(p!=NULL)  
            {
                s.push(p); //根结点入栈
                p=p->left; //先遍历左子树
            }
            else
            {
                p=s.top(); //根结点出栈
                s.pop();   //
                if(p->data!='#')//访问根结点
                cout<<p->data<<' ';
                p=p->right;//遍历右子树
            }
        }
    }       
    
    
    //递归实现后序遍历
    void PostorderTraverse(Tree_Node * T)
    {
        if(T)
        {
            PostorderTraverse(T->left); //访问左子树
            PostorderTraverse(T->right); //访问右子树
            if(T->data!='#')
            cout<<T->data<<" "; //访问根结点
        }
    }
    
    //非递归实现后序遍历
    //思路：我们要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；
    //或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，
    //则同样可以直接访问该结点。若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。 
    void PostorderTraverse_recursive(Tree_Node * T)
    {
        Tree_Node * pre; //前一个被访问的结点。
        pre=NULL;
        stack<Tree_Node*> s;
        Tree_Node * cur;  //记录栈顶的结点，
        s.push(T); //先把根结点入栈
        while(!s.empty())
        {
            cur=s.top(); //cur记录的是栈顶的结点
            if((cur->left==NULL && cur->right==NULL) || (pre!=NULL && (pre==cur->left || pre==cur->right)))
            {
                cout<<cur->data<<" "; //满足：不存在左孩子和右孩子；或者存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了
                s.pop();
                pre=cur; //更新pre的值
            }
            else
            {
                if(cur->right!=NULL) //一定是右子树先入栈的，因为这样才可以比左子树后被访问
                s.push(cur->right);
                if(cur->left!=NULL) //左子树入栈
                s.push(cur->left);   
            }
        }
    }
    
    int main()
    {
        Tree_Node * T;
        createTree(T);
        cout<<"先序遍历--递归实现"<<endl;
        PreorderTraverse(T);
        cout<<endl;
        cout<<"先序遍历--非递归实现"<<endl;
        PreorderTraverse_no_recursive(T);
        cout<<endl;
        cout<<"中序遍历--递归实现"<<endl;
        InorderTraverse(T);
        cout<<endl;
        cout<<"中序遍历--非递归实现"<<endl;
        InorderTraverse_recursive(T);
        cout<<endl;
        cout<<"后序遍历--递归实现"<<endl;
        PostorderTraverse(T);
        cout<<endl;
        cout<<"后序遍历--非递归实现"<<endl;
        PostorderTraverse_recursive(T);
        cout<<endl;
        return 0;
    
    }

输入数据：  
abd\#e\#\#fg\#\#\#c\#\#  
输出结果：  
![这里写图片描述][SouthEast 5]

## 5、线索二叉树 ##

在之前采用非递归方式进行二叉树的遍历的时候，我们需要声明一个栈来保存我们之后需要访问的结点等信息，然后，我们现在就想通过另外一种方式来代替我们的栈，它就是线索二叉树，  
**所谓的线索二叉树就是：即按照某种遍历方式对二叉树进行遍历，可以把二叉树中所有结点排序为一个线性序列。在该序列中，除第一个结点（某种遍历方式访问的第一个结点）外每个结点有且仅有一个直接前驱结点；除最后一个结点（某种遍历方式访问的最后一个结点）外每一个结点有且仅有一个直接后继结点。这些指向直接前驱结点和指向直接后续结点的指针被称为线索（Thread），加了线索的二叉树称为线索二叉树。**

OK，其实线索二叉树用一句话解释就是：我的每个结点都保存了该结点前一个访问的结点和后一个需要访问的结点。那么，我们要怎么记录那些信息了？最简单的方法就是为每个结点结构添加多两个结点域：pre和after，分别保存它的前驱和后继，但是这样必然会让结点的结构的存储密度减低。  
好了，现在有人发现其实我们在之前声明的结构中无论怎么样都会出现一大堆的空链域（指针的值为NULL），因为当我们有n个结点的时候，那么根据之前定义的结构，必有2\*n个指针域（left和right）,但是，除了根结点外，其他的每个结点都只有一个父亲结点（一个指针域指向它的意思），所以我们就只使用了(n-1)个指针域，最后一定还会有n+1个指针域为空的，那么其实我们就可以利用这些指针域来记录每个结点的前驱和后继。  
其中我们规定所有空的right都指向结点的后继：  
![这里写图片描述][SouthEast 6]

所有空的left都指向结点的前驱：  
![这里写图片描述][SouthEast 7]

所以我们提出一个线索链表的结构，如下图所示：  
![这里写图片描述][SouthEast 8]

因为，我们要记录当前的左孩子或者右孩子是否为空，所以需要在结构中添加多两个变量：ltag和rtag，只要左孩子或右孩子存在，就把对应的标志设置为0，否则设置为1.

下面，我们就以中序遍历为基础，建立中序线索二叉树，并且根据中序线索二叉树进行中序遍历。

另外，我们还打算引进一个头指针，这个头指针的lchild域指向根结点，rchild域指向中序遍历的最后一个结点，其中，中序遍历的最后一个结点和第一个结点都指向头结点，这样设置的好处是，我们可以顺前驱进行中序遍历，也可以顺后继往前进行遍历。

具体的代码实现：

#include<iostream>
    using namespace std;
    
    //结点的结构
    struct Tree_Node
    {
        //每个结点的数据
        char data;
        //左子树
        Tree_Node * left;
        //左标志
        int ltag;
        //右孩子
        Tree_Node * right;
        //右标志
        int rtag;
    };
    
    //按照先序遍历的方式，构建我们的二叉树,输入的时候，我们要按照完全二叉树的形式输入，结点为空的位置，输入“#”
    void createTree(Tree_Node * & t)
    {
        char str;
        cin >> str;
        if (str == '#')
        {
            t = NULL;
        }
        else
        {
            t = new Tree_Node; //为t开辟空间
            t->data = str;
            createTree(t->left);
            createTree(t->right);
        }
    }
    
    对刚才创建的二叉树进行中序的线索化，其实就是为ltag和rtag赋值，并且也为那些空指针域赋值
    Tree_Node  * pre;     /* 全局变量，始终指向刚刚访问过的结点 */
    void InThreading(Tree_Node * p)
    {
    
        if (p)
        {
            InThreading(p->left); //左子树的线索化
            p->ltag = 0; //假设p的左右孩子都不为空
            p->rtag = 0;
            if (!p->left) 
            { 
                p->ltag = 1; 
                p->left = pre;
            }  //如果当前的结点没有左孩子，那么就让我们的左孩子指向pre，
            if (!pre->right) 
            { 
                pre->rtag = 1;
                pre->right = p;
            } //因为pre时p的前驱，那么p就是pre的后继，如果pre的右孩子不为空的话，那么我们就让它的指向p
            pre = p;       //更新pre的值，因为等下就要进行右子树的线索化了
            InThreading(p->right);  //右子树的线索化
        }
    }
    
    //同样时线索化的函数，这里主要时处理让头结点的左指针域指向根结点和最后一个结点的右孩子的指针域指向头结点
    void InorderThreading(Tree_Node * & T, Tree_Node * & Thead)
    {
    
        Thead = new Tree_Node;  //建立一个头结点
        Thead->ltag = 0;
        Thead->rtag = 1;
        Thead->right = Thead;    //右指针域回指自己，等找到了最后一个结点后，再修改
        if (!T) //当二叉树为空的时候
        {
            Thead->left = Thead;
            return;
        }
    
        Thead->left = T;  //头结点的左指针指向根结点
        pre = Thead;      //让头结点为pre
        InThreading(T);  /* 中序遍历进行中序线索化，pre指向中序遍历的最后一个结点 */
        pre->right = Thead; /* 最后一个结点的右指针指向头结点 */
        pre->rtag = 1; /* 最后一个结点的右标志为线索 */
        Thead->right = pre; /* 头结点的右指针指向中序遍历的最后一个结点 */
    }
    
    void InorderThreading_recurcise(Tree_Node * Thead)
    {
        Tree_Node * p = Thead->left; /* p指向根结点 */
        while (p != Thead) /* 空树或遍历结束时，p==T */
        {
            while (p->ltag == 0) /* 由根结点一直找到二叉树的最左结点 */
                p = p->left;
    
            if (p->data != '#')  /* 访问此结点 */
                cout << p->data << " ";
    
            while (p->rtag == 1 && p->right != Thead)  /* p->rchild是线索(后继)，且不是遍历的最后一个结点 */
            {
                p = p->right;
                if (p->data != '#')
                    cout << p->data << " ";
            }
            p = p->right;   /* 若p->rchild不是线索(是右孩子)，p指向右孩子，返回循环，*/
        }
    }
    
    
    int main()
    {
        Tree_Node * T;
        createTree(T);
        Tree_Node * Thead;
        //线索化
        InorderThreading(T, Thead);
        cout << "中序遍历--非递归实现" << endl;
        InorderThreading_recurcise(Thead);
        cout << endl;
    
        return 0;
    }

输入：  
ABC\#\#DE\#G\#\#F\#\#\#

输出结果：  
![这里写图片描述][SouthEast 9]

## 6、最优二叉树（哈夫曼树） ##

（1）叶子结点的路径长度：从根结点到该叶子结点所经过的边的条数  
（2）树的带权路径长度：为树的所有的叶子结点的路径长度乘以该叶子结点之和。通常记作：WPL，具体可以见下图：  
![这里写图片描述][SouthEast 10]

然后，当我们给定每个叶子结点的权值，我们去构造不同的二叉树，当该二叉树的WPL值最小时，我们称该二叉树为最优二叉树或哈夫曼树

那么，我们该如何构造这个最优的二叉树了？哈夫曼最早提出了一个算法用于构造哈夫曼树，我们称之为哈夫曼算法，算法描述如下：  
![这里写图片描述][SouthEast 11]

下面，我们就拿一个具体的例子来说明如上的算法：  
![这里写图片描述][SouthEast 12]

根据刚才的算法描述，我们可以写出

首先是我们要定义每个结点的结构：

struct Tree_Node
    {
        char data; //数值 
        int weight; //权重 
        int parent; //父亲结点的下标 
        int left; //左孩子下标 
        int right; //右孩子下标 
    };

然后，需要一个函数选出权重最小的两个结点的下标

//在前i-1个结点中，找出最小的两个结点
    void select_two_min(Tree_Node * tree,int i, int s1, int s2)
    {
        int j = 0;
        int min = INT_MAX;
        int min2 = INT_MAX;
        for (j = 0; j <= i; j++)
        {
            //先找出s1
            if (tree[i].parent == 0 && tree[i].weight < min)
            {
                //更新m2的值为之前的m1，因为m1是之前最小的，现在变第二小了
                min2 = min; 
                //更新min
                min = tree[i].weight;
                //s2也是同样的道理，所以要更新
                s2 = s1;
                //s1也一样
                s1 = i;
    
            }//
            //如果还有比min2小，但是比min大的，那么只要更新min2和s2
            else if (tree[i].parent == 0 && tree[i].weight < min2) {
                min2 = tree[i].weight;
                s2 = i;
            }
        }
    
    }

最后，就是构造Huffman树的代码：

void Build_Huffman_Tree(Tree_Node * & tree, int * weight, int n, char * data)
    {
        if (n <= 1) return; //如果叶子结点只有一个，那么就可以直接返回了 
        int m = 2 * n - 1;
        //开辟2*n-1个空间，用于存放各个结点的信息，
        //因为我们知道如果有n个结点，除了根结点，我们最多需要记录的结点信息为：2*n-1个。 
        tree = new Tree_Node[m];
        int i = 0;
        Tree_Node * p = tree;
        for (i = 0; i < n; ++i, ++p, ++data, ++weight)//先初始化前n个结点，这些结点的基本信息已知
        {
            *p = { *data,*weight,0,0,0 };
        }
        for (; i < m; ++i, ++p)//初始化余下的结点
        {
            *p = { ' ',0,0,0,0 };
        }
        for (i = n; i < m; i++)
        {
            int s1 = 0;
            int s2 = 0;
            select_two_min(tree, i - 1, s1, s2);
            tree[i].left = s1;  //更新当前结点的左右孩子的下标
            tree[i].right = s2;
            tree[s1].parent = tree[s2].parent = i; //更新左右孩子的父亲下标
            tree[i].weight = tree[s1].weight + tree[s2].weight; //更新当前结点的权重为左右孩子的权重之和
    
        }
    }

通过上述的代码，我们就可以构造出一个Huffman树，而且这个Huffman树是用一个顺序结构存储的，各个结点之间使用数组的下标来联系的。

## 最优二叉树的应用（哈夫曼编码） ##

哈夫曼树最早就是被应用在编码压缩领域，比如我们现在有一组数据他们分别是：7个a，8个b，2个c，4个e，我们需要对刚才的那组数据进行编码，00代表a，01代表b，10代表c，11代表d，那么我们总用需要：7\*2+8\*2+2\*2+4\*2=42位来保存刚才的那组数据，好，如果我们另外一种编码，就是让权重大（数量多）的数据编码长度变小，让权重小的数据编码长度变长，这就是哈夫曼编码的原理。具体操作：

*  根据各个数据的数量，建立一个哈夫曼树
 *  根据建立的哈夫曼树，对原始数据进行编码，记录往左孩子去为0，往右孩子去的编码为1，如下图：  
    ![这里写图片描述][SouthEast 13]
 *  最后，就是根据哈夫曼树进行解码，0为往左子树遍历，1为往右子树遍历，直到叶子结点，就可以输出数据。

具体的代码实现如下：

#include<iostream>
    #include<string>
    using namespace std;
    
    
    struct Tree_Node
    {
        char data; //数值 
        int weight; //权重 
        int parent; //父亲结点的下标 
        int left; //左孩子下标 
        int right; //右孩子下标 
    };
    
    //在前i-1个结点中，找出最小的两个结点
    void select_two_min(Tree_Node * tree,int k, int & s1, int & s2)
    {
        int i = 0;
        int min = INT_MAX;
        int min2 = INT_MAX;
        for (i = 0; i <= k; i++)
        {
            //先找出s1
            if (tree[i].parent == 0 && tree[i].weight < min)
            {
                //更新m2的值为之前的m1，因为m1是之前最小的，现在变第二小了
                min2 = min; 
                //更新min
                min = tree[i].weight;
                //s2也是同样的道理，所以要更新
                s2 = s1;
                //s1也一样
                s1 = i;
    
            }//
            //如果还有比min2小，但是比min大的，那么只要更新min2和s2
            else if (tree[i].parent == 0 && tree[i].weight < min2) {
                min2 = tree[i].weight;
                s2 = i;
            }
        }
    
    }
    void Build_Huffman_Tree(Tree_Node * & tree, int * weight, int n, char * data)
    {
        if (n <= 1) return; //如果叶子结点只有一个，那么就可以直接返回了 
        int m = 2 * n - 1;
        //开辟2*n-1个空间，用于存放各个结点的信息，
        //因为我们知道如果有n个结点，除了根结点，我们最多需要记录的结点信息为：2*n-1个。 
        tree = new Tree_Node[m];
        int i = 0;
        Tree_Node * p = tree;
        for (i = 0; i < n; ++i)//先初始化前n个结点，这些结点的基本信息已知
        {
            tree[i].data = data[i];
            tree[i].left = tree[i].right = tree[i].parent = 0;
            tree[i].weight = weight[i];
        }
        for (; i < m; ++i)//初始化余下的结点
        {
    
            tree[i].left = tree[i].right = tree[i].parent = 0;
            tree[i].weight = 0;
        }
        for (i = n; i < m; i++)
        {
            int s1 = 0;
            int s2 = 0;
            select_two_min(tree, i - 1, s1, s2);
            tree[i].left = s1;  //更新当前结点的左右孩子的下标
            tree[i].right = s2;
            tree[s1].parent = tree[s2].parent = i; //更新左右孩子的父亲下标
            tree[i].weight = tree[s1].weight + tree[s2].weight; //更新当前结点的权重为左右孩子的权重之和
    
        }
    }
    
    
    
    void code(char * str,int n,int * weight,char ** & huffmancode)
    {
        Tree_Node * tree;
        Build_Huffman_Tree(tree, weight, n, str);
        huffmancode = new char*[n+1];
        char * c = new char[n];
        c[n - 1] = '\0';
        int i;
        int start;
        int child;
        int f;
        for (i = 0; i < n; i++)
        {
            start = n - 1;
    
            for (child = i, f = tree[i].parent; f != 0; child = f, f = tree[f].parent)
            {
                if (tree[f].left == child) {
                    c[--start] = '0'; 
                }
                else {
                    c[--start] = '1'; 
                }
            }
            huffmancode[i] = new char[n - start-1];
            int p = start;
            for (int k = 0; p < n; k++,p++)
            {
                huffmancode[i][k] = c[p];
            }
        }
    
    }
    
    int main()
    {
        char *str;
    
        int n;
        int * weight;
        char ** huffmancode;
        cout << "输入字符种类：" << endl;
        cin >> n;
        str = new char[n];
        weight = new int[n];
        cout << "输入每个字符和对应的权重" << endl;
        int i;
        for (i = 0; i < n; i++)
        {
            cin >> str[i];
            cin >> weight[i];
        }
    
        code(str, n, weight, huffmancode);
        cout << "每个字符编码后的值" << endl;
        for (i = 0; i < n; i++)
        {
            cout << str[i]<<" : "<<huffmancode[i] << endl;
        }
        cout << endl;
        return 0;
    }

输入：  
7  
D 17  
B 24  
E 34  
G 13  
C 7  
F 5  
A 5  
输出：  
![这里写图片描述][SouthEast 14]

[SouthEast]: /images/20220715/48c1336ab6b74d408739a37f99f821c8.png
[SouthEast 1]: /images/20220715/a84638f10bfb4f5f9af0cd181957c0f0.png
[SouthEast 2]: /images/20220715/0611803348f3404a8036f4eb1945a5d9.png
[SouthEast 3]: /images/20220715/c0994b275a204c60a45763f6c4c967d7.png
[SouthEast 4]: /images/20220715/8ade4309ab35459f9168d852e1abb0d8.png
[SouthEast 5]: /images/20220715/ed53e77e5ecc49aa967b65c4c6df9751.png
[SouthEast 6]: /images/20220715/d264dc8271b84d27849559b2e960646d.png
[SouthEast 7]: /images/20220715/51674bb0f3e54e9088d53b2f817b60a8.png
[SouthEast 8]: /images/20220715/e871ac8919ea48e79ce1335123cf09eb.png
[SouthEast 9]: /images/20220715/0b7bb56c68654d408a0df7f21675d116.png
[SouthEast 10]: /images/20220715/e640d0432fd6459fbdc12e7bdafc51cb.png
[SouthEast 11]: /images/20220715/d4c046703eb540f8b3af74216e85d7c4.png
[SouthEast 12]: /images/20220715/33e379832bc846edba51491804cdc7b9.png
[SouthEast 13]: /images/20220715/6314da3e4378429292c761c5a86f35d9.png
[SouthEast 14]: /images/20220715/9ca210dea0d84a21bf2c17bd44035eb1.png