嵌入式学习一阶段——C语言：数据结构(6)_若干棵树的森林转换的二叉树,坚持左孩子右兄弟原则,结点左指针指向第一个孩

树和森林

常用的数据结构

双亲表示法

这种存储方式采用一组连续的空间来存储每个结点，同时每一个结点中又设置了一个伪指针，指示其双亲结点在数组中的位置！！  规定根节点下标为0 ， 伪指针为-1；
如图：

孩子表示法

孩子表示法是将每一个基点的孩子结点都用单链表链接起来形成一个线性结构，此时n个结点就会有n个孩子链表（叶子结点的孩子链表为空）
这个存储方式，找儿子贼方便
如图：

孩子兄弟表示法

孩子兄弟表示法又称之为二叉树表示法！即以二叉链表作为树的存储结构。孩子兄弟表示法使每一个结点包括三部分： 1、节点值 2、指向结点第一个孩子结点的指针 3、以及指向结点下一个兄弟结点的指针（根据这个指针就可以找到该结点所有兄弟） 如图：

树转换成二叉树

树转换成二叉树的规则：每一个结点左指针指向它第一个孩子，右指针指向它在树中的相邻右兄弟，这个规则：“左孩子右兄弟法”

森林转换成二叉树

森林是由若干棵树组成，所有我们可以完全理解为，森林中每一颗树都是兄弟！可以按照兄弟的处理方式来操作，操作如下：
    1、把每颗树先转换成二叉树
    2、第一颗树不动，从第二棵二叉树开始，依次把后一棵二叉树的根节点作为前一棵树的根节点右孩子，用线连起来。
        当所有的二叉树连接起来后得到由森林转换而来的二叉树！！

二叉树转成树

如图：

平衡二叉树

单向右旋

单向左旋

先右旋再左旋

#include<stdio.h>
#include<stdlib.h>
#include"avltree.h"
 
#define Max(a,b) ((a)>(b)?(a):(b))
//单向右旋
Binode* Single_right(Binode* k2)
{
    Binode* k1=k2->lchild;
    k2->lchild=k1->rchild;
    k1->rchild=k2;
    k2->h=Max(Height(k2->lchild),Height(k2->rchild))+1;
    k1->h=Max(Height(k1->lchild),Height(k1->rchild))+1;
    return k1;
}
 
//单向左旋
Binode* Single_left(Binode* k2)
{
    Binode* k1=k2->rchild;
    k2->rchild=k1->lchild;
    k1->lchild=k2;
  
    k2->h=Max(Height(k2->lchild),Height(k2->rchild))+1;
    k1->h=Max(Height(k1->lchild),Height(k1->rchild))+1;
   
    return k1;
}
//先右旋再左旋
Binode* Single_rightleft(Binode* k2)
{
    k2->rchild=Single_right(k2->rchild);
    return Single_left(k2);
}
 
//先左旋再右旋
Binode* Single_leftright(Binode* k2)
{
    k2->lchild=Single_left(k2->lchild);
    return Single_right(k2);
}
 
//返回高度
int Height(Binode* root)
{
    if(root==NULL)
    return 0;
    else
    return root->h;
}
//创建平衡二叉树
Binode* create_avltree(void)
{
    Binode* root=NULL; 
    int d;
    while(1)
    {
        scanf("%d",&d);
        if(d==0)
        {
            break;
        }
        Binode* p=(Binode*)malloc(sizeof(Binode));
        p->data=d;
        p->lchild=NULL;
        p->rchild=NULL;
        p->h=1;
        root=insert(root,p);
    }
    return root;
}
//插入
Binode* insert(Binode* root,Binode* p)
{
   
    if(root==NULL)
    {
        return p;
    }
 
    if(p->data < root->data)
    {
        root->lchild=insert(root->lchild,p);
        root->h=Max(Height(root->lchild),Height(root->rchild))+1;
        if(abs(Height(root->lchild)-Height(root->rchild))>1)
        {
            if(p->data<root->lchild->data)//左边的左边添加，导致不平衡
            {
                //右旋
                root=Single_right(root);
            }
            else//左边的右边添加，导致不平衡 
            {
                //先左旋再右旋
                root=Single_leftright(root);
            }
        }
    }
    else 
    {
        root->rchild=insert(root->rchild,p);
        root->h=Max(Height(root->lchild),Height(root->rchild))+1;
        if(abs(Height(root->lchild)-Height(root->rchild))>1)
        {
            if(p->data>root->rchild->data)//在右边的右边添加，导致不平衡
            {
                //左旋
                root=Single_left(root);
            }
            else//在右边的左边添加，导致不平衡 
            {
                //先右旋再左旋
                root=Single_rightleft(root);
            }
        }
    }
        return root;
}
 
/**
 * @description:  先序遍历
 * @param {Binode} *root
 * @return {*}
 */
void pre_print(Binode *root)
{
    if(root==NULL)
    {
        return;
    }
    printf("%d ",root->data);
    pre_print(root->lchild);
    pre_print(root->rchild);
}

哈夫曼树

哈夫曼树

在许多的应用中，树中的结点常常被赋予一个标识某种意义的数值，称为这个结点的权。从树的根到任意结点的路径长度（经过边数）与该节点上权值的乘积，称为该结点的带权路径长度。树种的所有的叶子结点的带权路径之和称为该树的带权路径长度，记为WPL。
​
在含有 n 个带权叶子结点的二叉树中，其中带权路径长度（wpl）最小的二叉树称为 哈夫曼树，也称之为最优二叉树 

经过验证，C就是哈夫曼树

如何构造一棵哈夫曼树

从上看出哈夫曼树的特点 （1）、每一个初始节点最终会变成叶子节点，并且权值越小的节点到根节点的路径长度越大 （2）、构造的过程中共创建n-1个新节点（双分支节点），因此哈夫曼树的节点总数2n-1 （3）、每次构造的时候都选择了两颗树作为新节点孩子，所以哈弗满树没有度为1 的节点！！

哈夫曼编码

在电报通信中，电文是以二进制0/1序列传送的，每个字符对应一个二进制编码。
为了缩短电文的总长度，采用不等长编码方式，把使用频率较高的字符用短编码，
使用频率低的用长编码。
​
我们把使用频率作为权值，每个字符作为叶子结点来构建哈夫曼树，然后每个分支结点
的左右分支分别用0和1编码，这样就得到了每个叶子结点的二进制编码。
​
因为使用的是叶子结点的编码，所以每个字符的编码都不可能是其他字符编码的前缀。

哈夫曼树的伪代码

struct Hnode { char data; struct Hnode *lchild; struct Hnode *rchild; int weight; };

//假设结点数不超过30 (只用5棵树) struct Hnode * h[30] , root;

for(i = 0 ; i< 30 ; i++) { h[i] = malloc(sizeof(struct Hnode)); }

char ch[] = {'A','B','C','D','E'}; int weight[] = {2,9,5,7,8};

//为每单根树进行初始化 for(i = 0 ; i< 5 ; i++) { h[i]->data = ch[i]; h[i]->weight = weight[i]; h[i]->lchild = NULL; h[i]->rchild = NULL; }

while(n>1) { //排序,从大到小 sort(h,n); struct Hnode *s = malloc(sizeof(struct Hnode *)); s->data = ''; s->lchild = h[n-1];//小的 s->rchild = h[n-2];//大的 s->weight = h[n-1]->weight + h[n-2]->weight; h[n-2] = s; n--; }

#include "HuffmanTree.h"
#include "PriorityQueue.h"
#include <stdlib.h>
#include <stdio.h>
 
/*根据键盘输入，创建一棵哈夫曼树*/
HTNode *create_Huffman()
{
	HTNode *r=NULL;      //哈夫曼树的根结点
	PriorityQueue * pq = InitQueue();  //pq 队列
 
	/*step1: 构建森林*/
	while(1)
	{
		int d;
		scanf("%d",&d);
		if(d == -1)
			break;
		HTNode *pnew = malloc(sizeof(*pnew));
		pnew->weight = d;
		pnew->left = NULL;
		pnew->right = NULL;
		EnQueue( pq, pnew);//把创建的树入队
	}
 
	
	struct node *p= pq->front;
	while(p)
	{
		printf("%d ",p->data->weight);
		p = p->next;
	}
	putchar('\n');
	
	while(QueueLen(pq) >= 2)
	{
		/*step2: 从优先队列取出两个结点，并创建父节点*/
		HTNode *p1 = DeQueue(pq);
		HTNode *p2 = DeQueue(pq);
		printf("p1->%d\n",p1->weight);
		printf("p1->%d\n",p2->weight);
		HTNode *parent = malloc(sizeof(*parent));
		parent->left = p1;
		parent->right = p2;
		parent->weight = p1->weight + p2->weight;
		/*step3: 把父节点入队*/
		EnQueue(pq, parent);	
	}
 
	r = DeQueue(pq);//最后出队，把该结点作为根结点
	DestroyQueue(pq);
	return r;
}
 
 
void first_order(HTNode *r)
{
	if(r == NULL)
		return;
	/*step1: 访问根结点*/
	printf("%d ",r->weight);
	/*step2: 用先序遍历的规则访问左子树*/
	first_order(r->left);
	/*step3: 用先序遍历的规则访问右子树*/
	first_order(r->right);
}
 
void middle_order(HTNode *r)
{
	if(r == NULL)
		return;
	/*step1: 用中序遍历的规则访问左子树*/
	middle_order(r->left);
	/*step2: 访问根结点*/
	printf("%d ",r->weight);
	/*step3: 用中序遍历的规则访问右子树*/
	middle_order(r->right);
}
 
void last_order(HTNode *r)
{
	if(r == NULL)
		return;
	/*step1: 用后序遍历的规则访问左子树*/
	last_order(r->left);
	/*step2: 用后序遍历的规则访问右子树*/
	last_order(r->right);
	/*step3: 访问根结点*/
	printf("%d ",r->weight);
	
}
 
 
void HuffmanCoding(HTNode *r, int len)
{
	static int Coding[1024];
	if(r == NULL)
		return;
	if(r->left==NULL && r->right==NULL)//r就是叶子结点
	{
		printf("%d Coding: ",r->weight);
		for(int i=0;i<len;i++)
		{
			printf("%d",Coding[i]);
		}
		putchar('\n');
	}
	else
	{
		Coding[len] = 0;
		HuffmanCoding(r->left, len+1);
		Coding[len] = 1;
		HuffmanCoding(r->right, len+1);
	}
}