摘要 树是数据结构中非常重要的内容,是典型的非线性结构,并具有明显层次关系,非常类似于自然界的树。二叉树又是树形结构的代表,许多实际问题抽象出来的数据结构往往都是二叉树的形式,即使是一般的树也能转换为二叉树,而且二叉树的存储结构和算法都较为简单,因此二叉树显得尤为重要,本章为大家讲述二叉树的存储结构,创建,遍历等操作,以及线索二叉树的创建和最优二叉树赫夫曼树的定义和构造,另外还包含赫夫曼编码的输出等内容。

树的定义与相关术语

树的定义

树的递归定义如下:

树是n(n>=0)个结点的有限集T,T为空时称之为空树,否则,它满足以下两个条件:

  • 有且仅有一个特定的称之为根的结点;
  • 其余的结点可分为m(m>=0)个互不相交的子集T1,T2,…Tm,其中每个子集本身又是一棵树,并称其为根的子树。

树的相关术语

  • 结点的度:树中一个结点拥有的子树的数目,称之为该结点的度。
  • 树的度:树中结点的最大度数。
  • 双亲和孩子:树中某个结点的子树的根称之为该结点的孩子,相应地,该结点称为孩子的双亲。
  • 祖先和子孙:若树中存在一个结点序列k1,k2,k3,…,kj,使得ki是ki+1(1<=i<=j)的双亲,则称该结点序列时从k1到kj的一条路径或通路。路径的长度是指路径经过的边的数目。若树中结点ki到kj存在一条路径,则称ki是kj的祖先,kj是ki的子孙,一个结点的祖先是从根节点到该条路径上所经过的所有结点,而一个结点的子孙则是以该结点为根的子树中的所有结点。
  • 结点的层数:结点的层数从根起算,根的层数为1,其余结点的层数等于其双亲结点的层数+1。
  • 树的高度:树中结点的最大层数。
  • 有序树和无序树:若将树中每个结点的子树看成是从左到右有次序的,则称之为有序树,否则为无序树。
  • 森林:是m棵互不相交的树的集合。

二叉树的定义和相关性质

二叉树的定义

二叉树的递归定义:

二叉树是n(n>=0)个结点的有限集,它或者是空集(n=0),或者是由一个根节点及两棵互不相交的,分别称之为根的左子树右子树的二叉树组成。

二叉树相关性质

  • 二叉树中第i层上的结点数目最多为$$$2^{i-1}$$$(i>=1) 。
  • 深度为k的二叉树最多包含 $$$2^k-1$$$ 个结点。
  • 在任意一棵二叉树中,若终端结点的个数为n0,度为2的结点个数为n2,则n0=n2+1。

满二叉树和完全二叉树是二叉树的两种特殊情形。

满二叉树的定义:一棵深度为k且有 $$$2^k-1$$$ 个结点的二叉树为满二叉树。

满二叉树的特点:

  • 每一层上结点数达到最大值,即对给定的高度,它是具有最多结点数的二叉树。
  • 满二叉树不存在度为1的结点,每个分支结点均有两棵高度相同的子树,且树叶都在最下一层。

完全二叉树的定义:若一棵二叉树至多只有最下面的两层上节点的度数可以小于2,并且最下一层上的结点都集中在该层最左边的若干位置上,则称之为完全二叉树。

完全二叉树的的特点:

  • 满二叉树是完全二叉树,完全二叉树不一定是满二叉树。
  • 在满二叉树的最下一层上,从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。
  • 完全二叉树中,若某个结点没有左孩子,则它一定没有右孩子,该结点必定是叶子结点。
  • 具有n个结点的完全二叉树的深度为$$$[lgn]+1$$$

二叉树的存储结构

二叉树的顺序存储结构

完全二叉树可以按照结点编号的方法进行顺序存储。

在一棵n个结点的完全二叉树中,从树根起,自上层到下层,每层从左到右,给所有结点从1开始顺序编号,能得到一个反映整个二叉树结构的线性序列。

结点编号的方法存储的完全二叉树有如下特点,对编号为i的结点:

  • 若i>1,则其双亲编号为[i/2];若i=1,则是根结点,无双亲。
  • 若2i<=n,则其左孩子编号一定是2i,否则无左孩子,必定是叶子。
  • 若2i+1<=n,则其右孩子编号一定是2i+1,否则无右孩子。

从编号法可以得到结论:完全二叉树中编号为[n/2,n]的结点必定是叶子结点。

一般二叉树也可以仿照完全二叉树的存储方法,在树中添加一些虚结点构成完全二叉树,再采用结点编号的方法顺序存储到向量中。

对完全二叉树而言,顺序存储结构既简单,又节省空间,一般二叉树若采用顺序存储方法,虽然简单,但容易造成存储空间的浪费。

二叉树的链式存储结构

链式存储结构适合任何二叉树,定义树中结点包含数据域,左孩子域和右孩子域。

二叉树只需要保存树根结点即可,二叉树的链式存储结构又可以称为二叉链表。

用java语言描述的结构定义如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class BiTree{
private class BiNode{
private char data;
private BiNode lChild;
private BiNode rChild;

public BiNode(){

}

public BiNode(char data, BiNode lChild, BiNode rChild){
this.data = data;
this.lChild = lChild;
this.rChild = rChild;
}

}

private BiNode root = null;

public BiTree(){

}
}

二叉树的运算

二叉树的创建

使用指定二叉树结构图,创建如下二叉树。

bitree
1
2
3
4
5
6
7
8
public void create(){
BiNode dNode = new BiNode('D',null,null);
BiNode eNode = new BiNode('E',null,null);
BiNode fNode = new BiNode('F',null,null);
BiNode cNode = new BiNode('C',null,fNode);
BiNode bNode = new BiNode('B',dNode,eNode);
root = new BiNode('A',bNode,cNode);
}

求二叉树的高度

1
2
3
4
5
public int height(BiNode root){
if(root == null)
return 0;
return 1+(height(root.lChild) > height(root.rChild) ? height(root.lChild) : height(root.rChild));
}

求二叉树结点总数

1
2
3
4
5
public int size(BiNode root){
if(root == null)
return 0;
return 1+size(root.lChild)+size(root.rChild);
}

二叉树的递归遍历

定义二叉树的遍历顺序有先序遍历,中序遍历和后序遍历,其中:

  • 先序遍历:根结点->左子树->右子树
  • 中序遍历:左子树->根结点->右子树
  • 后序遍历:左子树->右子树->根结点

对二叉树进行递归遍历,形式非常简单,且易于实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public void preOrder(BiNode root){
if(root != null){
System.out.print(root.data+"--->");
preOrder(root.lChild);
preOrder(root.rChild);
}
}

public void inOrder(BiNode root){
if(root != null){
inOrder(root.lChild);
System.out.print(root.data+"--->");
inOrder(root.rChild);
}
}

public void postOrder(BiNode root){
if(root != null){
postOrder(root.lChild);
postOrder(root.rChild);
System.out.print(root.data+"--->");
}
}

二叉树的非递归遍历

相比较二叉树的递归遍历,非递归遍历则显得相当麻烦,尤其是后序遍历,我们需要像递归那样,另外维护一个操作栈,来记录之前的结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public void nonRecPreOrder(){
Stack<BiNode> stack = new Stack<BiNode>();
while(root != null || stack.size() > 0){
while(root != null){
System.out.print(root.data+"--->");
stack.push(root);
root = root.lChild;
}
if(stack.size() > 0){
root = stack.pop();
root = root.rChild;
}
}
}

public void nonRecInOrder(){
Stack<BiNode> stack = new Stack<BiNode>();
while(root != null || stack.size() > 0){
while(root != null){
stack.push(root);
root = root.lChild;
}
if(stack.size() > 0){
root = stack.pop();
System.out.print(root.data+"--->");
root = root.rChild;
}
}
}

public void nonRecPostOrder(){
Stack<BiNode> stack = new Stack<BiNode>();
BiNode cur, pre = null;
stack.push(root);
while(stack.size() > 0){
cur = stack.peek();

if((cur.lChild == null && cur.rChild == null) || (pre != null && (pre == cur.lChild || pre == cur.rChild))){
System.out.print(cur.data+"--->");
stack.pop();
pre = cur;
}else{
if(cur.rChild != null)
stack.push(cur.rChild);
if(cur.lChild != null)
stack.push(cur.lChild);
}
}
}

线索二叉树

前言:n个结点的二叉链表有n-1个空指针域,利用二叉链表中的空指针域,存放指向结点在某种遍历次序下的前驱和后继结点的指针,这种附加的指针称之为线索。加上了线索的链表称之为线索链表,相应的二叉树为线索二叉树。

线索链表解决了二叉链表找左、右孩子容易,但无法直接找到该结点在某种遍历次序下的前驱和后继困难的问题。线索链表的结构定义如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
enum PointerTag{
Link,Thread;
}

class BiThreadTree{
private class BiThreadNode{
private char data;
private PointerTag lTag,rTag;
private BiThreadNode lChild,rChild;

public BiThreadNode(char data, BiThreadNode lChild, BiThreadNode rChild){
this.data = data;
this.lChild = lChild;
this.rChild = rChild;
}
}


private BiThreadNode root = null;

public BiThreadTree(){

}
}

从以上定义可以看出,线索链表与二叉链表的唯一区别在于,其结点,多了两个枚举变量,该枚举变量指示当前结点指针域是指针还是线索。枚举变量lTag=Link,表示当前lChild指针域是指向左孩子的指针,枚举变量lTag=Thread,表示当前lChild指针域是指向其前驱的线索,没有左孩子;对于枚举变量rTag也一样。

根据不同的遍历次序,可以构造不同的线索二叉树,以中序遍历为例,构造中序线索二叉树如下,需要设置pre指针指示当前访问结点的前一个结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private BiThreadNode pre = null;
public void inOrderThreading(BiThreadNode root){
if(root != null){
inOrderThreading(root.lChild);

root.lTag = (root.lChild != null) ? PointerTag.Link : PointerTag.Thread;
root.rTag = (root.rChild != null) ? PointerTag.Link : PointerTag.Thread;

if(pre != null){
if(pre.rTag == PointerTag.Thread)
pre.rChild = root;
if(root.lTag == PointerTag.Thread)
root.lChild = pre;
}
pre = root;

inOrderThreading(root.rChild);
}
}

赫夫曼树和赫夫曼编码

相关概念

  • 树的路径长度:是从树根到树中每一叶子结点的路径长度之和。在结点数目相同的二叉树中,完全二叉树的路径长度最短。
  • 树的带权路径长度:树中某一叶子结点的带权路径长度为结点到根的路径长度与该结点权值的乘积,树中所有叶子结点的带权路径长度之和。
  • 最优二叉树或赫夫曼树:在权值分别为 $w_1$ , $w_2$ ,…, $w_n$ 的n个叶子所构成的所有二叉树中,带权路径长度最小(代价最小)的二叉树称为最优二叉树或赫夫曼树。

赫夫曼树特点

  • 所有叶子的权值均相等时,完全二叉树就是最优二叉树(赫夫曼树)。
  • 最优二叉树中,权越大的叶子离根越近。
  • 最优二叉树形态不唯一,WPL最小。

构造赫夫曼树

赫夫曼树的构造过程,可以概括为以下内容:

  1. 根据给定的n个权值w1,w2,…,wn构成n棵二叉树的森林F={T1,T2,…Tn},其中每棵二叉树Ti中都只有一个权值为wi的根结点,其左右子树均为空。
  2. 在森林F中选出两棵根结点权值最小的树,将这两棵树合并成一颗新树,为了保证新树仍是二叉树,需要增加一个新结点作为新二叉树的根,并将所选两棵树的根分别作为该新二叉树根的左孩子和右孩子(谁左谁右,无关紧要),将这两个孩子的权值之和作为新树根的权值。
  3. 对新的森林F重复步骤2,直到森林F中只剩下一棵树为止。这棵树便是赫夫曼树。

构造赫夫曼树的注意点:

  • 初始森林中的n棵二叉树,每棵树只有一个结点,它们既是根也是叶子。
  • n个叶子的赫夫曼树要经过n-1次合并,产生n-1个新结点,最终求得的赫夫曼树一共有2n-1个结点。
  • 赫夫曼树是严格的二叉树,树中没有度为1的结点。

根据以下相关内容,可以知道赫夫曼树是一种顺序存储结构,最后的赫夫曼树包含2n-1个结点,存储在向量中,结点需要包含权值信息,双亲,左孩子和右孩子。下面是赫夫曼树及其结点的类型定义:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class HuffmanTree{
private class HuffmaNode{
private int weight;
private int lChild, rChild, parent;

public HuffmaNode(){
this.weight = 0;
this.lChild = -1;
this.rChild = -1;
this.parent = -1;
}
}

private int leafNodeNum = 0;
private int nodeNum = 0;

private HuffmaNode[] data = null;

public HuffmanTree(int[] inputData){

this.leafNodeNum = inputData.length;
this.nodeNum = this.leafNodeNum*2-1;

this.data = new HuffmaNode[nodeNum];
}
}

构造赫夫曼树的过程,包括初始化森林F,即根据输入权值序列,初始化前n个叶子结点,构成森林,然后依次从前面的结点中选出根节点权值最小的2个,并生成新结点,共重复n-1次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void create(int[] input){
int i = 0;
for(; i<leafNodeNum; i++){
data[i] = new HuffmaNode();
data[i].weight = input[i];
}

for(; i<nodeNum; i++){
int select[] = selectMin2(data, i);
data[i] = new HuffmaNode();
data[i].lChild = select[0];
data[i].rChild = select[1];
data[i].weight = data[select[0]].weight + data[select[1]].weight;
data[select[0]].parent = data[select[1]].parent = i;

}
}

其中从前i个结点选出根节点权值最小的两个结点序号如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public int[] selectMin2(HuffmaNode[] data, int n){
int select[] = new int[2];
int s1 = 0, s2 = 1;
int minWeight1 = MAX_WEIGHT;
int minWeight2 = MAX_WEIGHT;

for(int i=0; i<n; i++){
if(data[i].parent == -1){
if(data[i].weight < minWeight1){
minWeight1 = data[i].weight;
s1 = i;
}
}
}

for(int i=0; i<n; i++){
if(i != s1 && data[i].parent == -1){
if(data[i].weight < minWeight2){
minWeight2 = data[i].weight;
s2 = i;
}
}
}

select[0] = s1;
select[1] = s2;
return select;
}

经过以上步骤,输入n个结点权值的赫夫曼树构建完成,赫夫曼树的主要用途就是赫夫曼编码,接下来为大家介绍赫夫曼编码的相关知识。

赫夫曼编码

前言:数据压缩过程称为编码,数据解压过程称为解码。给定一个字符集,可能存在多种编码方案。

等长编码方案:给定字符集中每个字符包含相同长度的编码。
变长编码方案:将频度高的字符编码设置短,将频度低的字符编码设置较长。
前缀码方案:对字符集进行编码时,要求字符集中任一字符的编码都不是其它字符的编码的前缀。
最优前缀码:平均码长或文件总长最小的前缀编码称为最优前缀码,最优前缀码的压缩效果最佳

变长编码方案比等长编码方案,一定程度上节约了存储空间,但是可能会使解码产生二义性,产生该问题的原因是某些字符的编码可能与其它某些字符的编码开始部分(称为前缀)相同。例如假设A:00,B:01,C:0001,则解码时无法确定0001是C还是AB。因此引出前缀码方案。

利用赫夫曼树很容易求出给定字符集及其概率分布的最优前缀码,赫夫曼编码是一种应用广泛且非常有效的数据压缩技术。赫夫曼编码是最优前缀码的原因:

  • 每个叶子字符ci的码长恰为从根到该叶子的路径长度li,平均码长(或是文件总长)又是二叉树的带权路径长度WPL,而赫夫曼树是WPL最小的二叉树,因此编码的平均码长或文件总长最小。
  • 赫夫曼树中没有一片叶子是另一叶子的祖先,每片叶子对应的编码就不可能是其它叶子编码的前缀,即上述编码是前缀编码。

赫夫曼编码类型定义为除了包含叶子字符属性,还包含该字符对应的编码。

1
2
3
4
5
6
private class HuffmaNode{
private char ch;
private String code;
}

private HuffmaNode[] encode;

求赫夫曼编码的思想:依次以叶子T[i](0<=i<=n)为出发点,向上回溯至根为止,上溯时,走左分支则生成代码0,走右分支则生成代码1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void huffmanEncoding(char[] inputCode){
for(int i=0; i<leafNodeNum; i++){
encode[i] = new HuffmaNode();
encode[i].ch = inputCode[i];

int p, c = i;
char cd[] = new char[leafNodeNum];
int start = leafNodeNum-1;

while((p = data[c].parent) != -1){
cd[start--] = (c == data[p].lChild) ? '0' : '1';
c = p;
}

encode[i].code = new String(cd).substring(start+1);
}
}