数据结构-二叉树

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

树的定义与相关术语

树的定义

树的递归定义如下:

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

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

树的相关术语

二叉树的定义和相关性质

二叉树的定义

二叉树的递归定义:

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

二叉树相关性质

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

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

满二叉树的特点:

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

完全二叉树的的特点:

二叉树的存储结构

二叉树的顺序存储结构

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

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

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

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

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

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

二叉树的链式存储结构

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

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

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

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
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);
}

求二叉树的高度

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

求二叉树结点总数

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

二叉树的递归遍历

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

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

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+"--->");
	}
}

二叉树的非递归遍历

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

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个空指针域,利用二叉链表中的空指针域,存放指向结点在某种遍历次序下的前驱和后继结点的指针,这种附加的指针称之为线索。加上了线索的链表称之为线索链表,相应的二叉树为线索二叉树。

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

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指针指示当前访问结点的前一个结点。

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);
	}
}

赫夫曼树和赫夫曼编码

相关概念

赫夫曼树特点

构造赫夫曼树

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

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

构造赫夫曼树的注意点:

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

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次。

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个结点选出根节点权值最小的两个结点序号如下所示:

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。因此引出前缀码方案。

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

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

private class HuffmaNode{
	private char ch;
	private String code;
}

private HuffmaNode[] encode;

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

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);
	}
}