树的定义：
树(Tree)是n(n>=0)个结点的有限集合T，它或者为空，或者满足以下条件：
（1）有且只有一个特定的称为根（root）的节点。
（2）其余结点分为m(m>=0)个互不相交的子集T1，T2，……，Tm，其中每个子集又是一个数，称其为根的子树。
树的度：
一个结点的子树个数称为该结点的度（degree）。一颗树的度是指改树中结点的最大度数。度为k的树也称为k叉树，它的每个结点最多有k个子树。
树的高度：
结点的层数（level）是从根开始算起的，根为第1层，其他结点的层数为其双亲结点的层数加1。树中结点的最大层数，称为树的高度（height）或者深度（depth）。
森林：
森林（forest）是m（m>=0)颗互不相交的树的集合。
二叉树：
二叉树（Binary Tree）是n（n>=0)个结点的集合，它或者为空（n=0),或者由一个根结点及两颗互不相交、分别称作该根的左子树和右子树的二叉树组成。
二叉树的性质：
性质1：二叉树第i层上的结点树最多为2i-1(i>=1)。
性质2：深度为k的二叉树至多有2k-1个结点（k>=1)。如果深度为k的二叉树有2k-1个结点，则称此二叉树为满二叉树（Full Binary Tree）。若一颗二叉树至多只有最下面两层上的结点的度可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，则称此二叉树为完全二叉树（Complete Binary Tree）。它相当于在满二叉树的最底层，从右向左连续去掉若干个结点后得到的二叉树。
性质3:二叉树中，度为0的结点数n0和度为2的结点数n2满足n0=n2+1。
性质4:具有n个结点的完全二叉树的深度为floor(log2n)+1或者ceiling(log2(n+1))。
性质5:在完全二叉树的层序编号中，对任一编号为i的结点x（1<=i<=n)，有：
(1）若i>1则x的双亲编号为floor(i/2);若i=1，则x是根，无双亲；
(2）若2i>n，则x无左孩子，否则其左孩子的编号为2i。完全二叉树没有左孩子必定也无右孩子，即为叶子，故编号为i>floor(n/2)的结点必定是叶子；
(3)如2i+1>n，则x无右孩子，否则其右孩子编号为2i+1；
二叉树的存储：二叉树通常有两类存储结构，即顺序存储结构和链式存储结构。其中常用的为链式存储结构，通常有关二叉树的算法也是基于链式存储结构的。二叉树链式存储的基本思想是，每个结点除了存放本身的数据外，还要根据需要设置指向双亲和左右孩子的指针，即通过指针来反映逻辑关系。二叉链表使用Java语言定义的形式为：
public class Node {
DataType data;
Node left;
Node right;
}
带双亲指针的形式为：
public class Node {
DataType data;
Node left;
Node right;
Node parent;
}
二叉树的遍历
二叉树的遍历是指沿某条搜索路径周游二叉树，对每个结点访问一次且仅访问一次。
递归遍历
递归遍历有三种：前序遍历，中序遍历，后序遍历。相应的代码为：
void preorder(Node node){ //前序
if(node == null){
return;
}
System.out.println(node.data);
preorder(node.left);
preorder(node.right);
}
void ineorder(Node node){//中序
if(node == null){
return;
}
inorder(node.left);
System.out.println(node.data);
inorder(node.right);
}
void postorder(Node node){//后序
if(node == null){
return;
}
postorder(node.left);
postorder(node.right);
System.out.println(node.data);
}
中序遍历具有的下列特点：
1.中序序列的第一个结点是二叉树最左下的结点。
2.中序序列的最后一个结点是二叉树最右下的结点。
层序遍历
层序遍历就是逐层地对结点进行访问，也可以将所有结点都访问到。借助队列可实现层序遍历，遍历算法为：每访问一个结点，就将它的孩子指针入队，下一个要访问的结点是队头；整个过程不断进行，直到队列为空。相应的Java代码为：
void levelorder(Node node){
if(node == null){
return;
}
Queue queue = new LinkedList<Node>();
queue.push(node);
while(!queue.isEmpty()){
Node t = queue.pop();
System.out.println(node.data);
if(node.left != null){
queue.push(node.left);
}
if(node.right != null){
queue.push(node.right);
}
}
二叉树的生成
这里二叉树的生成是指基于二叉树遍历序列生成相应的二叉树。
1.层序遍历序列
按完全二叉树的层次顺序，依次输入结点信息来建立二叉链表。这是因为完全二叉树的层序遍历序列中，结点间的序号关系可反映父子间的逻辑关系。对一般的二叉树，要补充若干个虚结点使其成为完全二叉树后，再按层次顺序输入，例如序例：A@B@@@C，其中@表示虚结点。
算法的基本思想是：依次输入结点信息，若输入的结点不是虚结点，则建立一个新结点；若新结点不是虚结点，则建立一个新结点；若新结点是第一个结点，则令其为根结点；否则作为孩子结点链接到它的双亲结点。如此重复，直到序列结束。
双亲与孩子的链接方法为：如当前输入的结点编号是偶数，则该结点作为左孩子与其双亲链接；否则作为右孩子与双亲链接；若双亲结点或孩子结点为虚结点，则无需链接。
具体算法为：
Node levelCreate(String string){
int len = string.length();
Node[] queue = new Node[len+1];
Node root,s;
int front = 0,rear = 0;
for(int i = 0;i < len;i ++){
char ch = string.charAt(i);
if(ch != '@'){
s = new Node();
s.data = ch;
s.left = s.right = null;
} else {
s = null;
}
rear ++;
queue[rear] = s;
if(rear == 1){
root = s;
front = 1;
} else {
if(s != null && queue[front] != null){
if(rear % 2 == 0){
queue[front].left = s;
} else {
queue[front].right = s;
}
}
if(rear % 2 == 1){
front ++;
}
}
}
return root;
}
2.先根、中跟或后跟遍历序列
先根遍历序列，具体算法如下：
Node preCreate(){
Node t;
char ch = read();
if(ch == '@') return null;
t = new Node();
t.data = ch;
t.left = preCreate();
t.right = preCreate();
return t;
}
后序只需将序例反过来执行如下算法：
Node postCreate(){
Node t;
char ch = read();
if(ch == '@') return null;
t = new Node();
t.data = ch;
t.right = postCreate();
t.left = postCreate();
return t;
}
中序遍历序列，因为不能确定谁是根，二叉树不唯一，无法生成二叉树
3.双遍历序列
遍历序列的特点有：
- 对于前序序列，序列的第一个结点就是整个二叉树的根；
- 对于后序序列，序列的最后一个结点就是整个二叉树的根；
- 对于中序序例，以根为界，序列的前一部分为根的左子树，后一部分为根的右子树。
若给定了前序序列和中序序列，反复利用上面的（1）和（3），就可获得完整的逻辑信息，即由前序序列找到根，由中序序列得到左右子树；再对每个子树由前序序列找到子树的根，由中序序列得到子树的左右子树，……，以此类推，每次得到一个结点（子树的根），从而逐渐分离出树的全部信息。相应的递归算法为：
Node create(char[] pre,int ps,int pe,char[] in,int is,int ie){
if(ps > pe){
return null;
}
Node t = new Node();
t.data = pre[ps];
int i = is;
while(in[i] != pre[ps]) i ++;
t.left = create(pre,ps + 1,ps + (i - is),in,is,i - 1);
t.right = create(pre,ps+(i-is)+1,pe,in,i+1,ie);
return t;
}
一般地，由中序与前序，中序与后序，中序与层序等都能唯一确定二叉树。而由前序和后序不能确定左右子树，一般就不能唯一确定二叉树。
参考资料：数据结构教程与题解