一. 树的定义
树是一种非线性的数据结构。它是n个结点的有限集合，一棵非空树具有以下的特点：
（1）有且只有一个称为根(root)的结点。
（2）当n>1时，其余n-1个结点可以划分为m个有限集合T1、T2......Tm，且这m个有限集合不相交，我们称其中的Ti为根的子树。
当n=0时，称为空树；当n>0时，称为非空树。树的逻辑结构如图所示：
在介绍树之前，需要先了解一些有关树的概念：
树的节点：指包含一个数据元素以及指向其他结点的分支信息。
结点的度：结点子树的个数称为结点的度。例如图中B有2棵子树，则B的度数为2；F的子树为0，它的度数就是0。
树的度：树中各结点度的最大值就是树的度。
孩子与双亲：结点的子树的根称为孩子，而该结点称为双亲。
兄弟：同一个双亲的孩子之间称为兄弟。
树的层次：从根结点起，根结点为第1层，根结点的孩子结点为第2层，以此类推。
数的深度：树中所有结点的层次最大值称为树的深度。
有序树与无序树：如果树中各棵子树之间是有先后次序的称为有序树，反之则称为无序树。
森林：m棵互不相交的树构成一个森林。
二. 二叉树的相关概念
1.二叉树的定义
二叉树是由n个结点构成的另一种树结构。它的特点是每个结点最多只有两棵子树，并且二叉树是有左右之分的（左孩子和右孩子），次序不能颠倒。
在二叉树中，任何一个结点的度只可能是0、1或2。
下面介绍两种特殊的二叉树：
1.满二叉树
每层结点都是满的二叉树称为满二叉树，即在满二叉树中每一层的结点都具有最大的结点个数。在满二叉树中每个结点的度只能为0或2，不会出现度为1的结点。
2.完全二叉树
对满二叉树的结点进行连续编号，约定从根结点开始，自上而下，从左到右进行编号。在一棵具有m个结点的二叉树中，若每个结点都与满二叉树的编号从1到m一一对应时，则称为完全二叉树。
2. 二叉树的性质
二叉树具有以下重要的性质：
性质一：二叉树的第k层上至多有2^(k-1)个结点。
性质二：深度为k的二叉树最多有2^k-1个结点。
性质三：对于任何一棵二叉树T，如果度为0结点数为n0，度为2的结点数为n2，则有n0=n2+1。
性质四：具有n个结点的完全二叉树的深度为[log2( n)]+1（[x]表示不大于x的最大整数）。
3. 二叉树的存储表示与实现
二叉树具有顺序存储和链式存储两种存储方式，其中链式存储是其最常用的方式。
1. 二叉树的顺序存储
若对一棵二叉树按照层次从上到下，从左到右进行编号，则对于完全二叉树来说每个结点的编号可以通过二叉树的性质计算得到，因此完全二叉树中的结点可以依次存放在一维数组中。
按照同样的方法，若将非完全二叉树的结点也按照同样的方式进行编号存放在一维数组中。为了能够正确反映二叉树结点之间的逻辑关系，还需要在一维数组中空出二叉树中不存在的结点位置（我这里用^来表示）。
可以看出如果采用顺序存储的方法，则对于许多的非完全二叉树来说构造数组是很浪费存储空间的。
2. 二叉树的链式存储
根据二叉树的定义，我们可以使用链表的方式来存储二叉树，即每个结点包括指向左孩子的指针域、数据域和指向右孩子的指针域。
其中，data域存放某结点的数据信息；lchild与rchild分别存放指向左孩子和右孩子的指针，当左孩子或右孩子不存在时，相应指针域值为空（用符号∧或NULL表示）。利用这样的结点结构表示的二叉树的链式存储结构被称为二叉链表。
二叉树的链式存储的结点结构类型：
public class Node<T>{
public Node<T> lchild;
public T data;
public Node<T> rchild;
public Node(){
lchild = null;
data = null;
rchild = null;
}
public Node(T x){
lchild = null;
data = x;
rchild = null;
}
}
3. 二叉树的基本操作的实现
class BinaryTree<T>{
private Node<T> root;
public BinaryTree(){} //构造二叉树
public BinaryTree(T x){}
public boolean insertLeft(T x,Node<T> parent){} //插入左结点
public boolean insertRight(Node<T> parent){} //插入右结点
public boolean deleteLeft(Node<T> parent){} //删除左结点
public boolean deleteRight(Node<T> parent){} //删除右结点
public boolean search(T x){} //在二叉树中查找数据
public void traversal(int i){} //按照某种方式遍历二叉树
public int getHeight(Node<T> parent){} //求当前二叉树的高度
}
（1）构造二叉树
public BinaryTree(){
root = new Node<T>();
}
public BinaryTree(T x){
this.root = new Node<T>(x);
}
（2）插入左结点
public boolean insertLeft(T x,Node<T> parent){
if(parent == null){
return false;
}
Node<T> p = new Node<T>(x);
if(parent.lchild == null){
parent.lchild = p;
return true;
}
return false;
}
（3）插入右结点
public boolean insertRight(Node<T> parent){
if(parent == null){
return false;
}
Node<T> p = new Node<T>(x);
if(parent.rchild == null){
parent.rchild = p;
return true;
}
return false;
}
（4）删除左结点
public boolean deleteLeft(Node<T> parent){
if(parent == null){
return false;
}
parent.lchild = null;
return true;
}
（5）删除右结点
public boolean deleteRight(Node<T> parent){
if(parent == null){
return false;
}
parent.rchild = null;
return true;
}
**（6）求二叉树的高度
public int getHeight(Node<T> parent){
int lh,rh,max;
if(parent != null){
lh = getHeight(parent.lchild);
rh = getHeight(parent.rchild);
max = lh > rh ? lh : rh;
return max+1;
}
esle{
return 0;
}
}
3. 遍历二叉树
遍历二叉树是指按照某种规律对二叉树的每个结点进行访问，使得每个结点仅被访问一次的操作。二叉树的遍历不同于线性表的遍历，对于二叉树来说，每个结点有两棵子树，因而需要一种规律，使得二叉树的结点能够排列在一个线性队列上，从而便于遍历。如果用D、L、R遍历根结点，遍历左子树和遍历右子树，如果限定先左后右的次序，就会有3中遍历方案:DLR（先序遍历）、LDR（中序遍历）和LRD（后序遍历）。
下面来分别介绍这3种遍历方式。
1. 先序遍历二叉树
先序遍历的递归定义是：如果二叉树为空，则不执行操作。反之则先访问根结点，然后先序遍历左子树，最后先序遍历右子树。
先序遍历二叉树的递归算法如下：
public void preorder(Node<T> node){
if(node == null){
return;
}
System.out.println(node.data);
preorder(node.lchild);
preorder(node.rchild);
}
2. 中序遍历二叉树
中序遍历的递归定义是：如果二叉树为空，则不执行操作。反之则先中序遍历左子树，然后访问根结点，最后中序遍历右子树。
中序遍历二叉树的递归算法如下：
public void inorder(Node<T> node){
if(node == null){
return ;
}
inorder(node.lchild);
System.out.println(node.data);
inorder(node.rchild);
}
3. 后序遍历二叉树
后序遍历的递归定义是：如果二叉树为空，则不执行操作。反之则先后序遍历左子树，然后后序遍历右子，最后树访问根结点。
后序遍历二叉树的递归算法如下：
public void postorder(Node<T> node){
if(node == null){
return ;
}
postorder(node.lchild);
postorder(node.rchild);
System.out.println(node.data);
}
4.层次遍历二叉树
层次遍历输出二叉树的结点可以利用队列来实现，即先定义一个队列queue用来存放结点的信息。从根结点出发，依次把每一层的结点入队，当一层结点入队完毕之后，将队头元素出队，输出该结点，然后判断结点是否存在左右孩子，如果存在，则将左右孩子入队。重复执行以上操作直到队空为止。
层次遍历输出二叉树的算法如下：
public void levelorder(){
Node<T>[] queue = (Node<T>)new Node[maxSize];
int front,rear;
front = -1;
rear = 0;
queue[rear] = root;
if(this.root == null){
return;
}
while(front != rear){
front++;
System.out.println(queue[front].data);
if(queue[front].lchild != null){
rear++;
queue[rear] = queue[front].lchild;
}
if(queue[front].rchild != null){
rear++;
queue[rear] = queue[front].rchild;
}
}
}
四.线索二叉树
一个具有n个结点的二叉树如果采用二叉链表存储结构，在2n个指针域中只有n-1个指针域用来存储结点孩子的引用，而另外n+1个指针域存放的都是null。因此，可以利用某结点空的左指针域指出该结点在某种遍历序列中直接前驱结点的存储地址，利用结点空的右指针域指出该结点爱某种遍历序列中直接后继结点的存储地址。而对于那些非空的指针域，则仍然存放指向结点左、右孩子的指针。这样，就得到一颗线索二叉树。
序列可以由不同的遍历方法得到，因此，线索树有先序线索二叉树、中序线索二叉树和后序线索二叉树，把二叉树改造成线索二叉树的过程称为线索化。
关于如何区别某结点的指针域存放的是指针还是线索，一般通过为每个结点增设两个标志位ltag和rtag来进行实现。
线索二叉树存储结构如下：
| itag | lchild | data | rchild | rtag
最优二叉树——哈夫曼树
1.哈夫曼树的定义
在介绍哈夫曼树之前，先介绍几个与哈弗曼树有关的定义。
（1）路径与路径长度：路径是指在树中，从一个结点到另一个结点所走过的路程。路径长度是一个结点到另一个结点的分支数目。树的路径长度是指从树的树根到每一个结点的路径长度的和。
（2）树的带权路径长度：在一棵树中，如果其结点上附带有一个权值，通常把该结点的路径长度与该结点上的权值之积称为该结点的带权路径长度。关于权的定义可以看这里。我们用WPL来表示带权路径长度。
哈弗曼树就是带权路径长度最小的树，也称为最优二叉树。
