数据结构——哈夫曼树

哈夫曼树又被称为最优二叉树，是指一类带权路径长度最小的二叉树，
哈夫曼树的遍历不是唯一的，因为在构造树的时候左右子树的位置是不同的。
哈夫曼树的构造思想如下
1:在给定权值的结点集合中，每个结点都是一颗独立的二叉树，并且左右子树为空，且只有一个根结点。
2:在集合中找到俩个最小的结点，并且组成一个新的结点，这俩个最小的分别为这个新结点的左右子树。新的结点为这两个结点的根结点。并且删除这俩个最小的结点，将新组成的结点添加集合中。
3:直到集合中元素长度不为1的时候 重复2

例如：
{1,2,3,4}构成的哈夫曼树是什么？
[图片上传失败...(image-588d50-1543055316769)]

在这里用链表实现，因为经常要删除和添加，链表比较好。
流程图如下
[图片上传失败...(image-f1b818-1543055316770)]

代码如下：

//  main.cpp
//  hafuman
//
//  Created by 橘子和香蕉 on 2018/11/22.
//  Copyright © 2018 橘子和香蕉. All rights reserved.
//

#include <iostream>
using namespace std;
typedef struct node{
    int data;
    node * parent;
    node *lchild;
    node *rchild;
    node *next;
}node;

class Tree{
private:
    node* head;
    node *hufmTreeHead;
    int length;
#pragma 私有函数声明
    void inorderNode(node *p);//中序遍历
    void findMinNodeandDelete(node *&p);//找最小的结点并且删除掉
    void addNode(node *p1);//两个参数组成一个新的结点然后添加这个新的结点
public:
    Tree(){head = new node; head->lchild = head->rchild=head->parent=head->next =  NULL;hufmTreeHead = NULL; }
    void initTreeList();//创建一条链表
    void createHufmTree();//创建一个二叉树
    void inorderTree();//中序遍历
    void printNode();//输出所有链表中的结点
};
#pragma 私有函数的实现开始
void Tree::inorderNode(node *p){
    if(p ==  NULL) return;
    else{
        inorderNode(p->lchild);
        cout<<"data: "<<p->data<<"\n";
        inorderNode(p->rchild);
    }
}
void Tree::findMinNodeandDelete(node *&p){
    /*查找分为两步；
     1:遍历链表，找到最小值所在的结点的位置，记下这个位置
     2:遍历链表，找个这个结点。
     
     因为不能在第一遍遍历链表的时候同时删除这个最小值所在的单向链表。同时也不能删除这个结点，因为这个结点还是留下来联接。
     */
    node *h1 = head;
    node *h = h1->next;
    int min = INT_MAX;
    while ( h != NULL) {
        if(h->data < min){
            min = h->data;
            p = h;
        }
        h = h->next;
    }
    h = h1->next;
    while (h != NULL) {
        if(h == p){
            h1->next = h->next;
            break;
        }
        h1 = h;
        h = h->next;
    }
    length--;//删除一个结点length-1；
}
void Tree::addNode(node *p){
    
    //头插法添加结点每次添加的都是在结点的头部
    p->next = head->next;
    head->next = p;
    length++;//添加一个新的结点length++;
}

#pragma 私有函数实现结束


#pragma 公有函数实现开始
void Tree::initTreeList(){
    cout<<"input data length:\n";
    int length;
    cin>>length;
    this->length = length;//数据长度
    cout<<"begin  input node data:\n";
    int data = 0;
    node *h = head;
    node* p;
    for (int i = 0; i<length; i++) {
        cout<<"input data: \t";
        cin>>data;
        p = new node;
        p->data= data;
        p->lchild = p->rchild=p->parent=p->next =  NULL;
        h->next = p;
        h = p;
        
    }
    
}
void Tree::createHufmTree(){
    node *p1,*p2;//找到的新结点
    while (length > 1) {
        findMinNodeandDelete(p1);
        findMinNodeandDelete(p2);
        node *n  = new node;//通过p1和p2组成一个新的结点;
        n->data = p1->data+p2->data;
        n->lchild = p1;
        n->rchild = p2;
        n->next = NULL;
        p1->parent = p2->parent = n;
        addNode(n);
    }
    hufmTreeHead = head->next;
    cout<<"hufmanHead:"<<hufmTreeHead->data<<endl;
}

void Tree::inorderTree(){
    cout<<"inorderTree-------------------------------------------\n";
    node *p = hufmTreeHead;
    inorderNode(p);
    cout<<endl;
    cout<<"inorderTree___________________________________________\n";
}

void Tree::printNode(){
    cout<<endl;
    cout<<"printNode begin---------------------------\n";
    node *h = head->next;
    cout<<"length"<<length<<";";
    while (h !=  NULL) {
        cout<<"h->data:"<<h->data<<endl;
        h = h->next;
    }
    cout<<"printNode finish_____________________\n";
}

#pragma 公有函数的实现的结束
int main(){
    Tree t;
    t.initTreeList();
    t.printNode();
    t.createHufmTree();
    t.inorderTree();
    return 1;
}