数据结构与算法-树

树是一种非线性结构，有一个前驱，可能有多个后继（1:n）的数据结构

树的基本知识

树的定义

树的定义
由一个或多个(n≥0)结点组成的有限集合T，有且仅有一个结点称为根（root），当n>1时，其余的结点分为m(m≥0)个互不相交的有限集合T1,T2，···，Tm。每个集合本身又是棵树，被称作这个根的子树

若干术语

  • 根：即根结点(没有前驱)
  • 叶子：即终端结点(没有后继)
  • 森林：指m棵不相交的树的集合(例如删除A后的子树个数)
  • 有序树：结点各子树从左至右有序，不能互换（左为第一）
  • 无序树：结点各子树可互换位置
  • 双亲：即上层的那个结点(直接前驱) parent
  • 孩子：即下层结点的子树 (直接后继) child
  • 兄弟：同一双亲下的同层结点（孩子之间互称兄弟）sibling
  • 堂兄弟：即双亲位于同一层的结点（但并非同一双亲）cousin
  • 祖先：即从根到该结点所经分支的所有结点
  • 子孙：即该结点下层子树中的任一结点
  • 结点：即树的数据元素
  • 结点的度：结点挂接的子树数（有几个直接后继就是几度，亦称“次数”）
  • 结点的层次：从根到该结点的层数（根结点算第一层）
  • 终端结点：即度为0的结点，即叶子
  • 分支结点：除树根以外的结点（也称为内部结点）
  • 树的度：所有结点度中的最大值（Max{各结点的度}）
  • 树的深度(或高度)：指所有结点中最大的层数（Max{各结点的层次}）

树的表示法有几种

  • 图形表示法
  • 嵌套集合表示法
  • 广义表表示法
    ( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) )
    根作为由子树森林组成的表的名字写在表的左边
  • 目录表示法
  • 左孩子－右兄弟表示法

逻辑结构

(特点)：一对多（1:n），有多个直接后继（如家谱树、目录树等等），但只有一个根结点，且子树之间互不相交

存储结构

  • 树是非线性结构，该怎样存储？
    仍然有顺序存储、链式存储等方式

  • 树的顺序存储方案应该怎样制定？
    可规定为：从上至下、从左至右将树的结点依次存入内存
    重大缺陷：复原困难（不能唯一复原就没有实用价值）

  • 树的链式存储方案应该怎样制定？
    可用多重链表：一个前趋指针，n个后继指针。
    细节问题：树中结点的结构类型样式该如何设计？即应该设计成“等长”还是“不等长”？
    缺点：等长结构太浪费（每个结点的度不一定相同）;不等长结构太复杂（要定义好多种结构类型）

  • 计算机如何实现各种不同进制的运算？
    实现思路：先研究最简单、最有规律的二进制运算规律，然后设法把各种不同进制的运算转化二进制运算

  • 树的存储可否借鉴这种思路呢？
    解决思路：先研究最简单、最有规律的树，然后设法把一般的树转化为这种简单的树

树的运算

  1. 普通树（即多叉树）若不转化为二叉树，则运算很难实现
  2. 二叉树的运算仍然是插入、删除、修改、查找、排序等，但这些操作必须建立在对树结点能够“遍历”的基础上

二叉树

二叉树的结构最简单，规律性最强
可以证明，所有树都能转为唯一对应的二叉树，不失一般性（利用左孩子－右兄弟表示法）

二叉树的定义

定义：是n（n≥0）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成

逻辑结构： 一对二（1：2）

基本特征:

  • 每个结点最多只有两棵子树（不存在度大于2的结点）
  • 左子树和右子树次序不能颠倒（有序树）

二叉树的性质

  • 性质1: 在二叉树的第i层上至多有2i-1个结点（i>0）
  • 性质2：深度为k的二叉树至多有2k-1个结点（k>0）
  • 性质3：对于任何一棵二叉树，若2度的结点数有n2个，则叶子数（n0）必定为n2＋1 （即n0=n2+1）
  • 满二叉树：一棵深度为k 且有2k-1个结点的二叉树。（特点：每层都“充满”了结点）
  • 完全二叉树：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应(完全二叉树的特点就是，只有最后一层叶子不满，且全部集中在左边。这其实是顺序二叉树的含义)
  • 满二叉树和完全二叉树在顺序存储方式下可以复原
  • 性质4：具有n个结点的完全二叉树的深度必为log2n＋1
  • 对完全二叉树，若从上至下、从左至右编号，则编号为i的结点，其左孩子编号必为2i，其右孩子编号必为2i＋1；其双亲的编号必为i/2（i＝1 时为根,除外）

二叉树的存储结构

顺序存储结构：
按二叉树的结点“自上而下、从左至右”编号，用一组连续的存储单元存储

链式存储结构：
一般从根结点开始存储。（相应地，访问树中结点时也只能从根开始）
二叉树结点数据类型定义：

typedef struct node *tree_pointer;
typedef struct node {
    int data;
    tree_pointer left_child, right_child;
} node;

二叉链表

typedef struct BiNode
{
	int data;
	struct BiNode  *lchild, *rchild;
}BiNode, *BiTree;

三叉链表

typedef struct TriTNode 
{
	int data;
	struct TriTNode *lchild, *rchild;
	struct TriTNode *parent;
}TriTNode, *TriTree;

双亲链表

typedef struct BPTNode
{
	int data;
	int parentPosition; //指向双亲的指针 //数组下标
	char LRTag; //左右孩子标志域
}BPTNode;

typedef struct BPTree
{
	BPTNode nodes[100]; //因为节点之间是分散的，需要把节点存储到数组中
	int num_node;  //节点数目
	int root; //根结点的位置 //注意此域存储的是父亲节点在数组的下标
}BPTree;

定义一颗简单的树

void main()
{
	BPTree tree;

	BiNode t1, t2, t3, t4, t5;

	memset(&t1, 0, sizeof(BiNode));
	memset(&t2, 0, sizeof(BiNode));
	memset(&t3, 0, sizeof(BiNode));
	memset(&t4, 0, sizeof(BiNode));
	memset(&t5, 0, sizeof(BiNode));

	t1.data = 1;
	t2.data = 2;
	t3.data = 3;
	t4.data = 4;
	t5.data = 5;

	//建立树关系
	//t1的左孩子为t2
	t1.lchild = &t2;
	//t1的右孩子为t3
	t1.rchild = &t3;
	//t2的左孩子为t4
	t2.lchild = &t4;
	//t3的左孩子为t5
	t3.lchild = &t5;

	system("pause");
}

使用指针去定义树

void main()
{
	BiTree p1, p2, p3, p4, p5;

	p1 = (BiTree)malloc(sizeof(BiNode));
	p2 = (BiTree)malloc(sizeof(BiNode));
	p3 = (BiTree)malloc(sizeof(BiNode));
	p4 = (BiTree)malloc(sizeof(BiNode));
	p5 = (BiTree)malloc(sizeof(BiNode));

	memset(p1, 0, sizeof(BiNode));
	memset(p2, 0, sizeof(BiNode));
	memset(p3, 0, sizeof(BiNode));
	memset(p4, 0, sizeof(BiNode));
	memset(p5, 0, sizeof(BiNode));

	p1->data = 1;
	p2->data = 2;
	p3->data = 3;
	p4->data = 4;
	p5->data = 5;

	//建立树关系
	//t1的左孩子为t2
	p1->lchild = p2;
	//t1的右孩子为t3
	p1->rchild = p3;
	//t2的左孩子为t4
	p2->lchild = p4;
	//t3的左孩子为t5
	p3->lchild = p5;

	system("pause");
}

遍历二叉树和线索二叉树

遍历二叉树

遍历定义：指按某条搜索路线遍访每个结点且不重复（又称周游）
遍历用途：它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心
遍历方法：牢记一种约定，对每个结点的查看都是“先左后右”

遍历规则：
二叉树由根、左子树、右子树构成，定义为D、L、R
D、L、R的组合定义了六种可能的遍历方案：LDR, LRD, DLR, DRL, RDL, RLD

若限定先左后右，则有三种实现方案：

  • DLR 先(根)序遍历
  • LDR 中(根)序遍历
  • LRD 后(根)序遍历

DLR—先序遍历，即先根再左再右
LDR—中序遍历，即先左再根再右
LRD—后序遍历，即先左再右再根

e.g.
( A ( B ( D , E ), C ) )
先序遍历的结果是：A B D E C
中序遍历的结果是：D B E A C
后序遍历的结果是：D E B C A
( A ( B ( C ( D , E ) ) , F ( G ( H ) ) ) )
先序遍历：ABCDEFGH
中序遍历：BDCEAFHG
后序遍历：DECBHGFA

e.g.(用二叉树表示算术表达式)
二叉树与算术表达式
先序遍历 -> + * * / A B C D E -> 前缀表示法
中序遍历 -> A / B * C * D + E -> 中缀表示法
后序遍历 -> A B / C * D * E + -> 后缀表示法
层序遍历 -> + * E * D / C A B

遍历的算法实现：

//结点数据类型自定义
typedef struct node{
   int  data; 
   struct node *lchild,*rchild；
} NODE;
NODE *root;

先序遍历算法

DLR(NODE *root )
{ 
    if (root) //非空二叉树
    {
        printf(“%d”,root->data); //访问D
        DLR(root->lchild); //递归遍历左子树
        DLR(root->rchild); //递归遍历右子树
    }
}

中序遍历算法

LDR(NODE *root)
{
    if(root !=NULL)
    {
        LDR(root->lchild);
        printf(“%d”,root->data);
        LDR(root->rchild);
    }
}

后序遍历算法

LRD (NODE *root)
{
    if(root !=NULL)
    {
        LRD(root->lchild);
        LRD(root->rchild);
        printf(“%d”,root->data);
    }
}

除去打印条件，其结构是一样的
这里的差别在于：
先序遍历在第一次访问时候输出
中序遍历在第二次访问时候输出
后序遍历在第三次访问时候输出

e.g.(二叉树中叶子结点的数目)

//使用全局变量sum
DLR_CountLeafNum(NODE *root)
{
    if (root)  //非空二叉树条件，还可写成if(root!=NULL)
    {
        if(!root->lchild && !root->rchild)//是叶子结点则统计并打印，在先中后打印并无区别
        {
            sum++;
            printf("%d
",root->data);
        }
        DLR_CountLeafNum(root->lchild); //递归遍历左子树，直到叶子处；
        DLR_CountLeafNum(root->rchild);//递归遍历右子树，直到叶子处；
    }
    return 0;
}

DLR_CountLeafNum(NODE *root, int *num)
{
    if (root != NULL)
    {
        if(!root->lchild && !root->rchild)
        {
            sum++;
            printf("%d
",root->data);
        }
        DLR_CountLeafNum(root->lchild, num); //递归遍历左子树，直到叶子处；
        DLR_CountLeafNum(root->rchild, num);//递归遍历右子树，直到叶子处；
    }
    return 0;
}

e.g.(二叉树的深度)

int GetDepth(BiNode *root)
{
	int depthleft = 0, depthright = 0; 
	int depthVal = 0;
	int tmp = 0;

	if (root == NULL)
	{
		depthVal = 0;
		return depthVal;
	}
	//求左子树高度
	depthleft = GetDepth(root->lchild);
	//求右子树高度
	depthright = GetDepth(root->rchild);

	tmp = ((depthleft>depthright)? depthleft : depthright);
	depthVal = 1 + tmp; 

	return depthVal;
}

e.g.(树的拷贝)

BiNode *copyTree(BiNode *T)
{
	BiNode *newLptr = NULL, *newRptr = NULL;
	BiNode *newNode = NULL;

	if (T->lchild != NULL)
	{
		newLptr =copyTree(T->lchild);
	}
	else
	{
		newLptr = NULL;
	}

	if (T->rchild != NULL)
	{
		newRptr = copyTree(T->rchild);
	}
	else
	{
		newRptr = NULL; 
	}

	newNode = (BiNode *)malloc(sizeof(BiNode));
	if (newNode == NULL)
	{
		return NULL;
	}

	newNode->lchild = newLptr;
	newNode->rchild = newRptr;
	newNode->data = T->data;

	return newNode;
}

中序遍历非递归算法:

步骤1：结点的所有路径情况
如果结点有左子树，该结点入栈；
如果结点没有左子树，访问该结点；

如果结点有右子树，重复步骤1；

如果结点没有右子树（结点访问完毕），回退，让栈顶元素出栈，访问栈顶元素，并访问右子树，重复步骤1

如果栈为空，表示遍历结束。

注意：入栈的结点表示，本身没有被访问过，同时右子树也没有被访问过。

#include <iostream>
#include <stack>
using namespace std;

//二叉链表
typedef struct BiNode
{
	int data;
	struct BiNode  *lchild, *rchild;
}BiNode, *BiTree;

BiNode *GoFarLeft(BiNode *T, stack<BiNode *> &s)
{
	if (T == NULL)
	{
		return NULL;
	}
	while (T->lchild)
	{
		s.push(T);
		T = T->lchild;
	}
	return T;
}
void InOrder(BiNode *T)
{
	 stack<BiNode *> s;
	 //步骤1：一直往左走，找到中序遍历的起点
	 BiTree t = GoFarLeft(T, s);
	 while (t)
	 {
		 printf("%d ", t->data); //中序遍历打印
		 //如果t节点有右子树，那么重复步骤1
		 if (t->rchild != NULL)
		 {
			t =  GoFarLeft(t->rchild, s);
		 }
		 //如果t没有右子树，根据栈顶指示，访问栈顶元素
		 else if (!s.empty())
		 {
			 t = s.top();
			 s.pop();
		 }
		 //如果t没有右子树，并且栈为空 
		 else
		 {
			 t = NULL;
		 }
	 }
}
void main()
{
	BiNode t1, t2, t3, t4, t5;
	memset(&t1, 0, sizeof(BiNode));
	memset(&t2, 0, sizeof(BiNode));
	memset(&t3, 0, sizeof(BiNode));
	memset(&t4, 0, sizeof(BiNode));
	memset(&t5, 0, sizeof(BiNode));
	t1.data = 1;
	t2.data = 2;
	t3.data = 3;
	t4.data = 4;
	t5.data = 5;
	t1.lchild = &t2;
	t1.rchild = &t3;
	t2.lchild = &t4;
	t3.lchild = &t5;
	InOrder(&t1);
	system("pause");
}

二叉树内存释放

void BiTree_Free(BiTNode* T)
{
	BiTNode *tmp = NULL;
	if (T != NULL)
	{
		if (T->rchild != NULL)
        {
            BiTree_Free(T->rchild);
        }
		if (T->lchild != NULL)
        {
            BiTree_Free(T->lchild);
        }
		if (T != NULL)
		{
			free(T); 
			T = NULL;
		}
	}
}

先序遍历创建树，需要有占位符：124#35#

//按给定的先序序列建立二叉链表
BiTNode* BiTree_Creat()
{
	BiTNode *tmp = NULL;
	char ch;
	printf("
请输入字符: ");
	scanf("%c", &ch);
	if (ch == '#')
	{
		return NULL;
	}
	else
	{
		tmp = (BiTNode *)malloc(sizeof(BiTNode));
		if (tmp == NULL)
		{
			return NULL;
		}
		tmp->data = ch; //生成根结点
		tmp->lchild = BiTree_Creat();//构建左子树
		tmp->rchild = BiTree_Creat();//构建右子数
		return tmp;
	}
}

根据先序和中序遍历结果可以得到原树
e.g.
先序结果：ADEBCF
中序结果：DEACFB
分析方法：

  1. 先从先序遍历中找到根节点A，然后根据A在中序遍历中的位置，区分出A的左子树和A的右子树
  2. 在A的左（右）子树中，找到左（右）子树的根节点（在先序中），重复上述步骤

分析：

  1. 由于先序从根节点开始，故A为根节点，再根据中序结果，DE为左节点，CFB为右节点。
  2. 由于在先序和中序中，DE顺序一样，故D为E的父节点，E为D的右节点
  3. 由先序结果，右节点为B，而中序结果中B位于最后，故得到B没有右节点
  4. 由于在先序和中序中，DE顺序一样，则可得出C为B的左节点，F为C的右节点

线索二叉树

普通二叉树只能找到结点的左右孩子信息，而该结点的直接前驱和直接后继只能在遍历过程中获得
若可将遍历后对应的有关前驱和后继预存起来，则从第一个结点开始就能很快“顺藤摸瓜”而遍历整个树了

规定：

  • 若结点有左子树，则lchild指向其左孩子；否则， lchild指向其直接前驱(即线索)
  • 若结点有右子树，则rchild指向其右孩子；否则， rchild指向其直接后继(即线索)
lchildLTagdataRTagrchild

约定:

  • 当Tag域为0时,表示正常情况
  • 当Tag域为1时,表示线索情况

在线索化二叉树中，并不是每个结点都能直接找到其后继的，当标志为0时，则需要通过一定运算才能找到它的后继

线索链表：用上面结点结构所构成的二叉链表
线索：指向结点前驱和后继的指针
线索二叉树：加上线索的二叉树(图形式样)
线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程

二叉树线索化算法

void InTreading(BiThrTree p) 
//中序遍历进行中序线索化
{
    if (p)
    {
        InThreading(p->lchild); /*左子树线索化*/
        if (!p->lchild) /*前驱线索*/
        {
            p->ltag=1;
            p->lchild=pre;
        }
    	if (!pre->rchild) /*后继线索*/
        {
            pre->rtag=1;
            pre->rchild=p;
        }
        pre=p;
        InThreading(p->rchild); /*右子树线索化*/
    }
}

二叉树线索化遍历算法:(非递归，且不用栈)

p = T->lchild; //从头结点进入到根结点；
while(p != T)
{
    while(p->LTag == link)
        p = p->lchild; //先找到中序遍历起点
    if(!visit(p->data))
        return ERROR; //若起点值为空则出错告警
    while(p->RTag == Thread ……)
    {
        p = p->rchild;
        Visit(p->data);
    } //若有后继标志，则直接提取p->rchild中线索并访问后继结点；
    p = p->rchild; //当前结点右域不空或已经找好了后继，则一律从结点的右子树开始重复{  }的全部过程。
}
return OK;

线索化过程就是在遍历过程中修改空指针的过程：
将空的lchild改为结点的直接前驱；
将空的rchild改为结点的直接后继。
非空指针仍然指向孩子结点
e.g.

#include <string.h>
#include <stdio.h>  
#include <stdlib.h>   
#include <io.h>  
#include <math.h>  
#include <time.h>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXSIZE 100 /* 存储空间初始分配量 */

typedef int Status;	/* Status是函数的类型,其值是函数结果状态代码,如OK等 */
typedef char TElemType;
typedef enum {Link,Thread} PointerTag;	/* Link==0表示指向左右孩子指针, */
										/* Thread==1表示指向前驱或后继的线索 */
typedef  struct BiThrNode	/* 二叉线索存储结点结构 */
{
	TElemType data;	/* 结点数据 */
	struct BiThrNode *lchild, *rchild;	/* 左右孩子指针 */
	PointerTag LTag;
	PointerTag RTag;		/* 左右标志 */
} BiThrNode, *BiThrTree;

TElemType Nil='#'; /* 字符型以空格符为空 */

Status visit(TElemType e)
{
	printf("%c ",e);
	return OK;
}

/* 按前序输入二叉线索树中结点的值,构造二叉线索树T */
/* 0(整型)/空格(字符型)表示空结点 */
Status CreateBiThrTree(BiThrTree *T)
{ 
	TElemType h;
	scanf("%c",&h);

	if(h==Nil)
		*T=NULL;
	else
	{
		*T=(BiThrTree)malloc(sizeof(BiThrNode));
		if(!*T)
			exit(OVERFLOW);
		(*T)->data=h; /* 生成根结点(前序) */
		CreateBiThrTree(&(*T)->lchild); /* 递归构造左子树 */
		if((*T)->lchild) /* 有左孩子 */
			(*T)->LTag=Link;
		CreateBiThrTree(&(*T)->rchild); /* 递归构造右子树 */
		if((*T)->rchild) /* 有右孩子 */
			(*T)->RTag=Link;
	}
	return OK;
}

BiThrTree pre; /* 全局变量,始终指向刚刚访问过的结点 */
/* 中序遍历进行中序线索化 */
void InThreading(BiThrTree p)
{ 
	if(p)
	{
		InThreading(p->lchild); /* 递归左子树线索化 */
		if(!p->lchild) /* 没有左孩子 */
		{
			p->LTag=Thread; /* 前驱线索 */			p->lchild=pre; /* 左孩子指针指向前驱 */
		}
		if(!pre->rchild) /* 前驱没有右孩子 */
		{
			pre->RTag=Thread; /* 后继线索 */
			pre->rchild=p; /* 前驱右孩子指针指向后继(当前结点p) */
		}
		pre=p; /* 保持pre指向p的前驱 */
		InThreading(p->rchild); /* 递归右子树线索化 */
	}
}

/* 中序遍历二叉树T,并将其中序线索化,Thrt指向头结点 */
Status InOrderThreading(BiThrTree *Thrt,BiThrTree T)
{ 
	*Thrt=(BiThrTree)malloc(sizeof(BiThrNode));
	if(!*Thrt)
		exit(OVERFLOW);
	(*Thrt)->LTag=Link; /* 建头结点 */
	(*Thrt)->RTag=Thread;
	(*Thrt)->rchild=(*Thrt); /* 右指针回指 */
	if(!T) /* 若二叉树空,则左指针回指 */
		(*Thrt)->lchild=*Thrt;
	else
	{
		(*Thrt)->lchild=T;
		pre=(*Thrt);
		InThreading(T); /* 中序遍历进行中序线索化 */
		pre->rchild=*Thrt;
		pre->RTag=Thread; /* 最后一个结点线索化 */
		(*Thrt)->rchild=pre;
	}
	return OK;
}

/* 中序遍历二叉线索树T(头结点)的非递归算法 */
Status InOrderTraverse_Thr(BiThrTree T)
{ 
	BiThrTree p;
	p=T->lchild; /* p指向根结点 */
	while(p!=T)
	{ /* 空树或遍历结束时,p==T */
		while(p->LTag==Link)
			p=p->lchild;
		if(!visit(p->data)) /* 访问其左子树为空的结点 */
			return ERROR;
		while(p->RTag==Thread&&p->rchild!=T)
		{
			p=p->rchild;
			visit(p->data); /* 访问后继结点 */
		}
		p=p->rchild;
	}
	return OK;
}

int main()
{
	BiThrTree H,T;
	printf("请按前序输入二叉树(如:'ABDH##I##EJ###CF##G##')
");
 	CreateBiThrTree(&T); /* 按前序产生二叉树 */
	InOrderThreading(&H,T); /* 中序遍历,并中序线索化二叉树 */
	printf("中序遍历(输出)二叉线索树:
");
	InOrderTraverse_Thr(H); /* 中序遍历(输出)二叉线索树 */
	printf("
");
	system("pause");
	return 0;
}

树和森林

树和森林的存储方式

  • 双亲表示法
  • 孩子表示法
  • 孩子兄弟表示法

树和森林与二叉树的转换

  • 树如何转为二叉树
    方法：加线—擦线—旋转
    step1: 将树中同一结点的兄弟相连;
    step2: 保留结点的最左孩子连线，删除其它孩子连线；
    step3: 将同一孩子的连线绕左孩子旋转45度角

  • 二叉树怎样还原为树：
    把所有右孩子变为兄弟

  • 森林如何转为二叉树：

    • ①各森林先各自转为二叉树；
      ②依次连到前一个二叉树的右子树上
    • 森林直接变兄弟，再转为二叉树

  • 二叉树如何还原为森林
    即B={root, LB, RB} ==> F={T1, T2, …,Tm}
    把最右边的子树变为森林，其余右子树变为兄弟

一般树的遍历

  • 深度遍历(先序、中序、后序)
  • 广度遍历(层次)

先序遍历

  • 访问根结点；
  • 依次先序遍历根结点的每棵子树

后序遍历

  • 依次后序遍历根结点的每棵子树；
  • 访问根结点

树没有中序遍历(因子树不分左右)

霍夫曼树

对于文本”BADCADFEED”的传输而言，因为重复出现的只有
”ABCDEF”这6个字符，因此可以用下面的方式编码:
霍夫曼树起源
接收方可以根据每3个bit进行一次字符解码的方式还原文本信息。
这样的编码方式需要30个bit位才能表示10个字符
当需要传送的数据量很大时，采用新的编码方式
霍夫曼树形成
准则：任一字符的编码都不是另一个字符编码的前缀！

霍夫曼树

  1. 给定n个数值{ v1, v2, …, vn}
  2. 根据这n个数值构造二叉树集合F
    F = { T1, T2, …, Tn}
    Ti的数据域为vi，左右子树为空
  3. 在F中选取两棵根结点的值最小的树作为左右子树构造一棵新的二叉树，这棵二叉树的根结点中的值为左右子树根结点中的值之和
  4. 在F中删除这两棵子树，并将构造的新二叉树加入F中
  5. 重复3和4，直到F中只剩下一个树为止。这棵树即霍夫曼树

假设经过统计ABCDEF在需要传输的报文中出现的概率如下
霍夫曼树字母概率
霍夫曼树
霍夫曼树是一种特殊的二叉树
霍夫曼树应用于信息编码和数据压缩领域
霍夫曼树是现代压缩算法的基础

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/cj5785/p/10664704.html