4.数据结构-树和二叉树

4.1树和二叉树的定义

4.1.1树的定义

树是$n(n\ge 0)$个结点的有限集，它或为空树$(n=0)$；或为非空树。对于非空树$T$：

1.有且仅有一个称为根的结点
2.除根节点以外的其余节点可分为$m(m>0)$个互不相交的有限集$T_1,T_2...,T_m$，其中每一个集合本身又是一棵树，并且称为根的子树。

树的结构定义是一个递归的定义，即在树的定义中又用到树的定义，它道出了树的固有特性。

4.1.2树的基本术语

结点：树中独立的一个单元。
结点的度：结点拥有的子树数称为结点的度。
树的度：树的度是树内各节点度的最大值。
叶子：度为0的结点称为叶子或终端结点。
非终端结点：度不为0的结点称为非终端结点或分支结点。除根节点以外，非终端结点也成为内部节点。
双亲和孩子：结点的子树的根称为该结点的孩子，相应地，该节点称为孩子的双亲。
兄弟：同一个双亲的孩子之间互称为兄弟
祖先：从根节点到该节点所经历分支上所有的结点。
子孙：以某节点为根的子树中的任一结点都称为该节点的子孙。
层次：结点的层次从根开始定义起，根为第一层，根的孩子为第二层。
堂兄弟：双亲在同一层次的结点互为堂兄弟。
树的深度：树中结点的最大层次称为树的深度或告诉。
有序树和无序树：如果将树中的结点各子树看成从左至右是有次序的，则称该树为有序树，否则称为无序树。
森林：是$m(m\ge 0)$棵互补相交的树的集合。对树中的每个结点而言，其子树的集合即为森林。

4.1.3二叉树的定义

二叉树是$n(n\ge 0)$个结点所构成的集合，它或为空树$(n=0)$；或为非空树。对于非空树$T$：

1.有且仅有一个称为根的结点
2.除根节点以外的其余结点分为两个互不相交的子集$T_1,T_2$，分别称为$T$的左子树和右子树，且$T_1,T_2$本身又都是二叉树。

4.2二叉树的性质和存储结构

4.2.1二叉树的性质

性质1：在二叉树的第i层上至多又$2^{i-1}$个结点$(i\ge 1)$。
性质2：深度为$k$的二叉树至多有$2^k-1$个结点$(k\ge 1)$。
性质3：对任何一颗二叉树$T$，如果其终端结点数为$n_0$，度为2的结点数为$n_2$，则$n_0=n_2+1$。
满二叉树：深度为$k$且含有$2^k-1$个结点的二叉树。

满二叉树的特点是：

每一层上的结点数都是最大结点数，即每一层$i$的结点数都具有最大值$2^{i-1}$。

完全二叉树：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至$n$一一对应时，称之为完全二叉树。

完全二叉树的特点：

1.叶子结点只可能在层次最大的两层上出现；
2.对任一结点，若其右分支下的子孙的最大层次为l，则其左分支下的子孙的最大层次必为$l或l+1$。（因为计数是从左至右的顺序）

性质4：具有n个结点的完全二叉树的深度为$k=\lfloor lo{g}_{2}n\rfloor +1$
这一条性质记住：对于一个深度为$k$的完全二叉树，它的前$k-1$层一定是一个满二叉树。
所以：
$$2^{k-1}-1<n\le 2^k-1$$
因为k为整数，由此得出$k=\lfloor lo{g}_{2}n\rfloor +1$。
性质5：如果对一颗有$n$个结点的完全二叉树(其深度为$\lfloor lo{g}_{2}n\rfloor +1$)的结点按层序编号(从第1层到第$\lfloor lo{g}_{2}n\rfloor +1$层，每层从左到右)，则对任一结点$i(1\le i\le n)$，有：

1.如果$i=1$， 则结点$i$是二叉树的根，无双亲；如果$i>1$，则其双亲$PARENT(i)$是结点$\lfloor \frac{i}{2}\rfloor$。
2.如果$2i>n$，则结点$i$无左孩子（结点$i$为叶子结点）；否则其左孩子$LCHILD(i)$是结点$2i$。
3.如果$2i+1>n$，则结点$i$无右孩子；否则其右孩子$RCHILD(i)$是结点$2i+1$。
(对于一个结点i来说若他有左孩子，那么其编号为$2i$，若有右孩子，则其编号为$2i+1$)

4.2.1二叉树的存储结构

顺序存储

类似线性表，二叉树的存储结构也可采用顺序存储和链式存储两种方式。
顺序存储结构使用一组地址连续的存储单元来存储数据元素，为了能够在存储结构中反应出结点之间的逻辑关系，必须将二叉树中的结点依照一定的规律安排在这组单元中。

#define MAXSIZE 100
#define TElemType int
#define Status intusing namespace std; typedef TElemType SqBiTree[MAXSIZE];
SqBiTree bt;

对于完全二叉树，只要从根起按层序存储即可，依次自上而下，自左至右存储结点元素，即：

对于一般二叉树，则将其每一个结点与完全二叉树的结点相对照，存储在一维数组的相应分量中，以’0‘表示不存在此点。

由此可见，这种顺序存储结构仅适用于完全二叉树。因为，在最坏的情况下：

一个深度为$k$且只有k个结点的单支树就需要长度为$2^k-1$的一维数组。造成了极大的浪费。

链式存储

二叉树的链表中的结点至少包含3个域：数据域和左、右指针域。

typedef struct BiTNode{TElemType data;struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

4.3遍历二叉树和线索二叉树

4.3.1遍历二叉树

遍历二叉树：是指按某条搜索路径巡防树种每个结点，使得每个结点均被访问一次，而且仅被访问一次。
先序遍历：

1.访问根结点
2.先序遍历左子树
3.先序遍历右子树

中序遍历

1.中序遍历左子树
2.访问根节点
3.中序遍历右子树

后序遍历

1.后序遍历左子树
2.后续遍历右子树
3.访问根节点

先序遍历结果：
$$-+a\ast b-cd/ef$$

中序遍历结果：
$$a+b\ast c-d-e/f$$

后序遍历结果：
$$abcd-\ast +ef/-$$

#include <iostream>
#include <fstream>
#include <cstring>#define MAXSIZE 100
#define TElemType int
#define Status intusing namespace std; typedef struct BiTNode {TElemType data;struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;// 递归创建二叉树
void CreateBiTree(BiTree &T) {int value;cout << "请输入节点值（输入 -1 表示空节点）：";cin >> value;if (value == -1) { // -1 代表空节点T = NULL;} else {T = new BiTNode; // 创建新节点T->data = value;cout << "输入 " << value << " 的左子节点：" << endl;CreateBiTree(T->lchild); // 递归创建左子树cout << "输入 " << value << " 的右子节点：" << endl;CreateBiTree(T->rchild); // 递归创建右子树}
}// 先序遍历（根 → 左 → 右）
void PreOrderTraversal(BiTree T) {if (T) {cout << T->data << " ";PreOrderTraversal(T->lchild);PreOrderTraversal(T->rchild);}
}// 中序遍历（左 → 根 → 右）
void InOrderTraversal(BiTree T) {if (T) {InOrderTraversal(T->lchild);cout << T->data << " ";InOrderTraversal(T->rchild);}
}// 后序遍历（左 → 右 → 根）
void PostOrderTraversal(BiTree T) {if (T) {PostOrderTraversal(T->lchild);PostOrderTraversal(T->rchild);cout << T->data << " ";}
}int main() {BiTree T;cout << "开始创建二叉树：" << endl;CreateBiTree(T);cout << "\n二叉树的先序遍历：" << endl;PreOrderTraversal(T);cout << "\n二叉树的中序遍历：" << endl;InOrderTraversal(T);cout << "\n二叉树的后序遍历：" << endl;PostOrderTraversal(T);return 0;
}

根据遍历序确定二叉树

由二叉树的先序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一颗二叉树。

由定义，二叉树的先序遍历是由先访问根结点，其次再按先序遍历方式遍历根结点的左子树，最后按先序遍历根结点的右子树。也就是说，先续遍历的第一个结点一定是二叉树的根节点。另一方面，中序遍历是先遍历左子树，然后访问根结点，最后再遍历右子树。这样，根节点在中序序列中必然分割成两个子序列，前一个子序列是根结点的左子树的中序序列，而后一个子序列是根结点的右子树的中序序列。根据这两个子序列，在先序序列中找到对应的左子序列和右子序列。在先序序列中，左子序列的第一个结点是左子树的根结点，右子序列的第一个结点是右子树的根结点。这样，就确定了二叉树的三个结点。同时，左子树和右子树的根节点又可以分别把左子序列和右子序列的划分成两个子序列，如此递归下去，当取尽先序序列中的结点时，便可以得到一颗二叉树。

同理，由二叉树的后序序列和中序序列也可以唯一确定一棵二叉树。因为，依据后序遍历和中序便利的定义，后续遍历的最后一个结点，就如同先序序列的第一个结点一样，可将中序序列分成两个子序列，分别未这个结点左子树的中序序列和右子树的中序序列，再拿出后序序列的倒数第二个结点，并继续分割中序序列，如此递归下去，当倒着取尽后序序列中的结点时，便可以得到一棵二叉树。

但是由一颗二叉树的先序序列和后序序列不能唯一确定一颗二叉树

先序序列创建二叉链表

// 递归创建二叉树
void CreateBiTree(BiTree &T) {int value;cout << "请输入节点值（输入 -1 表示空节点）：";cin >> value;if (value == -1) { // -1 代表空节点T = NULL;} else {T = new BiTNode; // 创建新节点T->data = value;cout << "输入 " << value << " 的左子节点：" << endl;CreateBiTree(T->lchild); // 递归创建左子树cout << "输入 " << value << " 的右子节点：" << endl;CreateBiTree(T->rchild); // 递归创建右子树}
}

复制二叉树

与先序序列创建二叉树类似的想法。

//复制二叉树
void Copy(BiTree &T, BiTree &NewT){if(T == NULL){NewT == NULL;return;}else{NewT = new BiTNode;NewT->data = T->data;Copy(T->lchild, NewT->lchild);Copy(T->rchild, NewT->rchild);}
} 

计算二叉树的深度

//统计二叉树中结点个数
int NodeCount(BiTree T){if(T == NULL) return 0;else return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
} 

4.3.2线索二叉树

遍历二叉树的实质是对一个非线性结构进行线性化操作，使每个结点在这些线性序列中有且仅有一个直接前驱和直接后驱。

但是，当以二叉链表作为存储结构时，只能找到结点的左、右孩子信息，而不能直接得到结点在任一序列中的前去和后继信息，这种信息这有遍历的动态过程中才能得到，为此引入线索二叉树来保存这些在动态过程中得到的有关前驱后继的信息。

试作如下规定：若结点有左子树，则其lchild域指示其左孩子，否则令lchilid域指示其前驱；若结点有右子树，则其rchild域指示其右孩子，否则令rchild域指示其后继。为了避免混淆，尚需改变结点结构，增加两个标志域，其结点形式如下：

$$LTag=\{\begin{array}{c}0lchild域指示结点的左孩子\\ 1lchild域指示结点的前驱\end{array}$$

$$RTag=\{\begin{array}{c}0lchild域指示结点的左孩子\\ 1lchild域指示结点的后继\end{array}$$
线索链表的定义：

typedef struct BiThrNode {TElemType data;struct BiThrNode *lchild, *rchild;int LTag, RTag;
} BiThrNode, *BiThrTree;

其中指向结点前驱和后继的指针，叫做线索。加上线索的二叉树称之为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。

因为中序遍历的结果为：
$$a+b\ast c-d-e/f$$
按照中序遍历的结果在独照上图就一目了然了。

*线索化

#include <iostream>
using namespace std;// 线索二叉树结点结构
typedef struct BiThrNode {char data;                  // 结点数据struct BiThrNode *lchild, *rchild; // 左右孩子指针int LTag, RTag;             // 线索标记：0=孩子，1=线索
} BiThrNode, *BiThrTree;// 全局变量：用于记录遍历过程中的前驱结点
BiThrTree pre = NULL;// 创建普通二叉树（先序输入，'#' 表示空结点）
void CreateBiTree(BiThrTree &T) {char ch;cin >> ch;if (ch == '#') {T = NULL;} else {T = new BiThrNode;T->data = ch;T->LTag = T->RTag = 0;  // 初始化标记，表示普通孩子指针CreateBiTree(T->lchild);CreateBiTree(T->rchild);}
}// 中序线索化以结点p为根
void InThreading(BiThrTree p) {if (p) {InThreading(p->lchild); // 递归左子树// 处理左线索if (!p->lchild) {p->LTag = 1;p->lchild = pre;} else {p->LTag = 0;}// 处理右线索if (pre && !pre->rchild) {pre->RTag = 1;pre->rchild = p;} else if (pre) {pre->RTag = 0;}pre = p; // 更新前驱指针，pre最后会变成中序遍历的最后一个值InThreading(p->rchild); // 递归右子树}
}// 带头结点线索化二叉树（包装函数）
void InOrderThreading(BiThrTree &Thrt, BiThrTree T) {Thrt = new BiThrNode; // 生成头结点Thrt->LTag = 0; //树没空左孩子为树根Thrt->RTag = 1; //右孩子指针为右线索Thrt->rchild = Thrt; // 头结点右指针回指if (!T) {Thrt->lchild = Thrt; //树为空做指针也指向自己} else {Thrt->lchild = T;  //头结点左孩子指向根pre = Thrt; // 头结点作为前驱InThreading(T);//在InThreading中pre最后会变成中序遍历的最后一个值pre->rchild = Thrt; pre->RTag = 1;Thrt->rchild = pre; // 头结点的右孩子指向最后一个结点，// 最后结点的后继指向头结点，所以形成了循环链表}
}// 中序遍历（非递归，利用线索）
void InOrderTraverse_Thr(BiThrTree T) {BiThrTree p = T->lchild; // 从根节点开始while (p != T) {while (p->LTag == 0) p = p->lchild; // 找到最左结点cout << p->data << " ";while (p->RTag == 1 && p->rchild != T) {p = p->rchild;cout << p->data << " ";}p = p->rchild;}
}// 主函数
int main() {BiThrTree T, Thrt;cout << "请输入二叉树的先序序列（用 # 代表空）：";CreateBiTree(T);// 线索化InOrderThreading(Thrt, T);cout << "中序遍历（线索二叉树）结果：";InOrderTraverse_Thr(Thrt);cout << endl;return 0;
}

头结点在线索化二叉树中的主要作用是：

1.作为树的边界节点，指示树的开始和结束。
2.简化树的遍历过程，特别是中序遍历。
3.提高遍历效率，避免使用栈或递归。
4.形成循环链表，使得树的遍历变得更加灵活。
5.统一树的操作，简化了插入、删除和查找等操作。
因此，虽然头结点本身不存储数据，它在组织和优化树的结构方面起到了至关重要的作用。好好看代码注释！

遍历线索二叉树

*在中序线索二叉树中查找结点的前驱和后继

1.查找p指针所指结点的前驱：

若p->LTag=1，则p的左链指示前驱；
若p->LTag=0，则说明p有左子树，结点的前驱是遍历左子树时最后访问的一个结点。

中序遍历的结果是42513，2和1都有左子树，1的前驱是他遍历左子树最后一个结点也就是5，2的前驱就是遍历其左子树最后一个结点也就是4。

2.查找p指针所指结点的后驱：

若p->RTag=1，则p的右链指示前驱
若p->RTag=0，则说明p有右子树，根据中序遍历的规律可知，结点的后继应是遍历其右子树时访问的第一个结点。

在先序线索二叉树中查找结点的前驱和后继

1.查找p指针所指结点的前驱：

若p->LTag=1，则p的左链指示前驱；
若p->LTag=0，则说明p有左子树，结点的前驱有两种情况：若*p是其双亲的左孩子，则其双亲为他的前驱；否则前驱是其双亲的左子树先序遍历最后访问的一个结点。

2.查找p指针所指结点的后驱：

若p->RTag=1，则p的左右指示前驱
若p->RTag=0，则说明p有右子树，根据先序遍历的规律可知，结点的后继应是遍历其左子树（存在）或右子树根

在后序线索二叉树中查找结点的前驱和后继

1.查找p指针所指结点的前驱：

若p->LTag=1，则p的左链指示前驱；
若p->LTag=0，当p->RTag=0，则p的右链指示其前驱；若p->LTag=0，当p->RTag=1，则p的左链指示其前驱

2.查找p指针所指结点的后驱：

若* p是二叉树的根，则其后继为空；
若 * p是其双亲的右孩子，则其后继为双亲结点；
若p是其双亲的左孩子，且 * p没有右兄弟，则其后继为双亲结点；
若p是其双亲的左孩子，且 * p有右兄弟，则其后继为双亲的右子树上按后续遍历出的第一个结点。

遍历中序线索二叉树

void InOrderTraverse_Thr(BiThrTree T) {BiThrTree p = T->lchild; // 从根节点开始while (p != T) {while (p->LTag == 0) p = p->lchild; // 找到最左结点cout << p->data << " ";while (p->RTag == 1 && p->rchild != T) {p = p->rchild;cout << p->data << " ";}p = p->rchild;}
}

前提是构建好了中序线索树

4.4树和森林

4.4.1树的存储结构

双亲表示法

这种表示法中，以一组连续的存储单元存储树的结点，每个结点除了数据与data外，还附设一个parent域用以指示其双亲结点的位置。

这种存储结构利用了每个结点（除根结点以外）只有唯一双亲的性质。这种存储结构，求结点的双亲十分方便。

孩子表示法

由于树种每个结点可能有多个子树，则可用多重链表，即每个结点有多个指针域，其中每个指针指向一颗子树的根结点，此时链表中的结点可以有如下两种结点格式：

若采用第一种结点格式，则多重链表中的结点是同构的，其中d为树的度。由于树中很多结点的度小于d，所以链表中有很多空链域，空间较浪费，不难推出，在一棵有n个结点度为k的树中必有n(k-1)+1个空链域。

若采用第一种结点格式，则多重链表中的结点是同构的，其中d为树的度。由于树中很多结点的度小于d，所以链表中有很多空链域，空间较浪费，不难推出，在一棵有n个结点度为k的树中必有n(k-1)+1个空链域。

*孩子兄弟法

又称二叉树表示法，或二叉链表表示法，即以二叉链表做树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子节点和下一个兄弟结点。

typedef struct CSNode {ElemType data;struct CSNode *firstchild, *nextsibling
} CSNode, *CSTree;

这种存储结构的优点是它和二叉树的二叉链表表示完全一样，便于将一般的树结构转换为二叉树进行处理，利用二叉树的算法实现对树的操作。

#include <iostream>
#define ElemType intusing namespace std;typedef struct CSNode {ElemType data;struct CSNode *firstchild, *nextsibling;
} CSNode, *CSTree;CSNode* CreateNode(ElemType value) {CSNode* newNode = new CSNode;newNode->data = value;newNode->firstchild = NULL;newNode->nextsibling = NULL;return newNode;
}void CreateTree(CSTree &T) {ElemType value;cout << "请输入节点值（输入 -1 表示空节点）：";cin >> value;if (value == -1) {  // -1 代表空节点T = NULL;} else {T = CreateNode(value);  // 创建新节点cout << "输入 " << value << " 的第一个子节点：" << endl;CreateTree(T->firstchild);  // 递归创建第一个子节点if (T->firstchild != NULL) {cout << "输入 " << value << " 的下一个兄弟节点：" << endl;CreateTree(T->nextsibling); // 递归创建下一个兄弟节点}}
}int main() {return 0;
}

4.4.2森林与二叉树的转换

从树的二叉链表表示的定义可知，任何一颗和树对应的二叉树，其根结点的右子树必空。

主要是要理解孩子兄弟法。将树转成二叉树的结构存储，第一个兄弟结点，会成为该结点的右儿子。

森林（Forest） 是一种由 若干棵不相交的树 组成的集合。具体来说，森林是由多个树构成的图，每棵树的节点和边都不与其他树的节点和边相连。

若把森林中的第二棵树的根结点，看成是第一颗树的根结点的兄弟，则同样可导出森林和二叉树的对应关系。

森林转换成二叉树，就是把E看成A的兄弟，所以转换成了A的右儿子了。

二叉树转换成森林，主要看右子树。

将森林转换成二叉树c++代码

#include <iostream>
#include <vector>
#define ElemType intusing namespace std;// 树节点结构
typedef struct CSNode {ElemType data;struct CSNode *firstchild, *nextsibling;
} CSNode, *CSTree;// 创建树节点
CSNode* CreateNode(ElemType value) {CSNode* newNode = new CSNode;newNode->data = value;newNode->firstchild = NULL;newNode->nextsibling = NULL;return newNode;
}void CreateTree(CSTree &T) {ElemType value;cout << "请输入节点值（输入 -1 表示空节点）：";cin >> value;if (value == -1) {  // -1 代表空节点T = NULL;} else {T = CreateNode(value);  // 创建新节点cout << "输入 " << value << " 的第一个子节点：" << endl;CreateTree(T->firstchild);  // 递归创建第一个子节点cout << "输入 " << value << " 的下一个兄弟节点：" << endl;CreateTree(T->nextsibling); // 递归创建下一个兄弟节点}
}// 用户输入创建森林（多棵树）
void CreateForest(vector<CSTree> &forest) {int treeCount;cout << "请输入森林中树的数量：";cin >> treeCount;for (int i = 0; i < treeCount; i++) {cout << "创建第 " << i + 1 << " 棵树：" << endl;CSTree tree = NULL;CreateTree(tree);  // 创建一棵树forest.push_back(tree);  // 将树的根节点加入森林}
}// 将森林转换为二叉树
CSTree ForestToBinaryTree(vector<CSTree> &forest) {if (forest.empty()) {return NULL;}// 将森林中的每棵树的根节点通过兄弟指针连接起来for (size_t i = 0; i < forest.size() - 1; i++) {forest[i]->nextsibling = forest[i + 1];}// 返回第一棵树的根节点，作为二叉树的根节点return forest[0];
}// 打印二叉树（前序遍历）
void PrintBinaryTree(CSTree T) {if (T == NULL) {return;}cout << T->data << " ";  // 访问根节点PrintBinaryTree(T->firstchild);  // 递归访问左子树PrintBinaryTree(T->nextsibling); // 递归访问右子树
}int main() {vector<CSTree> forest;CreateForest(forest);  // 创建森林cout << "将森林转换为二叉树：" << endl;CSTree binaryTree = ForestToBinaryTree(forest);cout << "二叉树的前序遍历结果：" << endl;PrintBinaryTree(binaryTree);return 0;
}

4.5哈夫曼树及其应用

4.5.1哈夫曼树的基本概念

哈夫曼树 又称最优树，是一类带权路径长度最短的树，在实际中有广泛的用途。

路径 ：从树中一个结点到另一个结点之间的分支构成两个结点之间的路径。
路径长度：路径上的分支数目称作路径长度。
树的路径长度：从树根到每一个结点的路径长度之和。
权：赋予某个实体的一个量，是对实体的某个或某些属性的数值化描述。在数据结构中，实体有结点（元素）和边（关系）两大类，所对应有结点和权边。
结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积。
树的带权路径长度：树中所有叶子结点的带权路径长度之和，通常记作$WPL={\sum }_{k=1}^n{w}_k{l}_k$。
哈夫曼树：假设有m个权值$w_1,w_2,...,w_m$，可构造一颗含n个叶子结点的二叉树，每个叶子结点的权为$w_i$，则其中带权路径长度$WPL$最小的二叉树称作最优二叉树或哈夫曼树。

可以看出，在哈夫曼树中，权值越大的结点离根结点越近。

4.5.2哈夫曼树的构造算法

哈夫曼树的构造过程

1.根据给定的n个权值$w_1,w_2,...,w_n$，构造n棵只有根结点的二叉树，这n棵二叉树构成一个森林F。
2.在森林F中选取两棵根结点的权值最小的数作为左右子树构造出一颗新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。
3.在森林F中删除这两棵树，同时新得到的二叉树加入F中。
4.重复2、3，直到F只含一棵树为止。这棵树便是哈夫曼树。

哈夫曼算法的实现

哈夫曼树是一种二叉树，当然可以采用前面介绍过的通用存储方法，而由于哈夫曼树中没有度为1 的结点，则一棵有n个叶子结点的哈夫曼树共有$2n-1$个结点，可以存储在一个大小为$2n-1$的一维数组中。树中每个结点还要包括其双亲信息和结点信息。

typedef struct{int weight;int parent, lchild, rchild;
}HTNode, *HuffmanTree; 

哈夫曼树的各结点存储在由HuffmanTree定义的动态分配的数组中，为了实现方便，0号单元不使用，从1号开始，所以数组大小为2n。将叶子结点集中存储在前面部分1~n个位置，而后面的n-1个位置存储其余非叶子结点。

步骤：
1. 首先动态申请2n个单元；然后循环2n-1次，从一号单元开始，依次将1~2n-1所有单元中的双亲、左孩子、右孩子的下标初始化为0；再循环n次，输入前n个单元中叶子结点的权值。
2. 循环n-1次，通过n-1次选择、删除与合并来创建哈夫曼树。选择是从当前森林中选择双亲为0且权值最小的两个树根结点$s_1、s_2$；删除是指将结点$s_1、s_2$的双亲改为非0；合并就是将$s_1、s_2$的权值和作为一个新结点的权值依次存入到数组n+1之后的单元中，同时记录这个新结点的左孩子下标为$s_1$，右孩子的下标为$s_1$。

完整代码

#include <iostream>
#include <vector>
#define ElemType intusing namespace std;typedef struct{int weight;int parent, lchild, rchild;
}HTNode, *HuffmanTree; void Select(HuffmanTree HT, int end, int &s1, int &s2) {s1 = s2 = 0;int min1 = 100000, min2 = 100000;for (int i = 1; i <= end; i++) {if (HT[i].parent == 0) { // 只考虑尚未选中的结点if (HT[i].weight < min1) {min2 = min1;s2 = s1;min1 = HT[i].weight;s1 = i;} else if (HT[i].weight < min2) {min2 = HT[i].weight;s2 = i;}}}
}int CalculateWPL(HuffmanTree HT, int n) {int WPL = 0;for (int i = 1; i <= n; i++) { // 只计算叶子节点int depth = 0, current = i;while (HT[current].parent != 0) { // 追溯到根节点current = HT[current].parent;depth++;}WPL += HT[i].weight * depth; // 计算 WPL}return WPL;
}void CreatHuffmanTree(HuffmanTree &HT, int n){if(n <= 1) return;int m = 2*n-1;HT = new HTNode[m+1]; //HT[m]表示根结点for(int i = 1; i <= m; i ++){HT[i].parent = 0;HT[i].lchild = 0;HT[i].rchild = 0;} for(int i = 1; i <= n; i ++){cin >> HT[i].weight;}for(int i = n+1; i <= m; i ++){int s1 = 0, s2 = 0;Select(HT, i-1, s1, s2);//HT[k] 中选择两个其双亲域为0且权值最小的结点,并返回它们在HT中的序号s1和s2HT[s1].parent = i, HT[s2].parent = i;HT[i].lchild = s1;HT[i].rchild = s2;HT[i].weight = HT[s1].weight+HT[s2].weight;}
}int main() {HuffmanTree HT;int n = 8;CreatHuffmanTree(HT, n);cout << HT[2*n-1].weight << endl;cout << CalculateWPL(HT, n) << endl;return 0;
}

4.5.3哈夫曼编码

如图所示的哈夫曼树中，约定左分支标记为0，右分支标记为1，则根结点到每个叶子结点路径上的0、1序列即为相应字符编码。

前缀编码：如果在一个编码方案中，任一编码都不是其他任何编码的前缀（最左子串），则称编码是前缀编码。

哈夫曼编码：对一棵具有n个叶子的哈夫曼树，若对树中的每个左分支赋予0，右分支赋予1，则从根到每个叶子的路径上，各分支的赋值分别构成一个二进制串，该二进制串就成为哈夫曼编码。

哈夫曼编码满足以下性质：

性质1 ：哈夫曼编码是前缀编码。
性质2 ：哈夫曼编码是最优前缀编码。

哈夫曼编码的算法实现

主要思想是：依次以叶子为出发点，向上回溯至根结点为止。回溯时走左分支则生成代码0，走右分支则生成代码1；

#include <iostream>
#include <vector>
#include <cstring>
#define ElemType intusing namespace std;typedef struct{int weight;int parent, lchild, rchild;
}HTNode, *HuffmanTree; typedef char **HUffmanCode;void Select(HuffmanTree HT, int end, int &s1, int &s2) {s1 = s2 = 0;int min1 = 100000, min2 = 100000;for (int i = 1; i <= end; i++) {if (HT[i].parent == 0) { // 只考虑尚未选中的结点if (HT[i].weight < min1) {min2 = min1;s2 = s1;min1 = HT[i].weight;s1 = i;} else if (HT[i].weight < min2) {min2 = HT[i].weight;s2 = i;}}}
}int CalculateWPL(HuffmanTree HT, int n) {int WPL = 0;for (int i = 1; i <= n; i++) { // 只计算叶子节点int depth = 0, current = i;while (HT[current].parent != 0) { // 追溯到根节点current = HT[current].parent;depth++;}WPL += HT[i].weight * depth; // 计算 WPL}return WPL;
}void CreatHuffmanTree(HuffmanTree &HT, int n){if(n <= 1) return;int m = 2*n-1;HT = new HTNode[m+1]; //HT[m]表示根结点for(int i = 1; i <= m; i ++){HT[i].parent = 0;HT[i].lchild = 0;HT[i].rchild = 0;} for(int i = 1; i <= n; i ++){cin >> HT[i].weight;}for(int i = n+1; i <= m; i ++){int s1 = 0, s2 = 0;Select(HT, i-1, s1, s2);//HT[k] 中选择两个其双亲域为0且权值最小的结点,并返回它们在HT中的序号s1和s2HT[s1].parent = i, HT[s2].parent = i;HT[i].lchild = s1;HT[i].rchild = s2;HT[i].weight = HT[s1].weight+HT[s2].weight;}
}void CreatHuffmanCode(HuffmanTree HT, HUffmanCode &HC, int n){HC = new char*[n+1];char *cd = new char[n];cd[n-1] = '\0';for(int i = 1; i <= n; i ++){int start = n-1;int c = i;int f = HT[i].parent;while(f != 0){--start;if(HT[f].lchild == c) cd[start] = '0';else cd[start] = '1';c = f; f = HT[f].parent;} HC[i] = new char[n-start];strcpy(HC[i], &cd[start]);}delete cd;
}int main() {HuffmanTree HT;HUffmanCode HC;int n = 8;CreatHuffmanTree(HT, n);CreatHuffmanCode(HT, HC, n);cout << HT[2*n-1].weight << endl;cout << CalculateWPL(HT, n) << endl;for(int i = 1; i <= n; i ++)cout << HC[i] << endl;return 0;
}