基本知識：
一、樹的定義
樹是一種資料結構，它是由n（n>=1）個有限結點組成一個具有層次關系的集合。
樹具有的特點有：
（1）每個結點有零個或多個子結點
（2）沒有父節點的結點稱為根節點
（3）每一個非根結點有且隻有一個父節點
（4）除了根結點外，每個子結點可以分為多個不相交的子樹。
樹的基本術語有：
若一個結點有子樹，那麼該結點稱為子樹根的“雙親”，子樹的根稱為該結點的“孩子”。有相同雙親的結點互為“兄弟”。一個結點的所有子樹上的任何結點都是該結點的後裔。從根結點到某個結點的路徑上的所有結點都是該結點的祖先。
結點的度：結點擁有的子樹的數目
葉子結點：度為0的結點
分支結點：度不為0的結點
樹的度：樹中結點的最大的度
層次：根結點的層次為1，其餘結點的層次等于該結點的雙親結點的層次加1
樹的高度：樹中結點的最大層次
森林：0個或多個不相交的樹組成。對森林加上一個根，森林即成為樹；删去根，樹即成為森林。
二、二叉樹
1、二叉樹的定義
二叉樹是每個結點最多有兩個子樹的樹結構。它有五種基本形态：二叉樹可以是空集；根可以有空的左子樹或右子樹；或者左、右子樹皆為空。
2、二叉樹的性質
性質1：二叉樹第i層上的結點數目最多為2i-1(i>=1)
性質2：深度為k的二叉樹至多有2k-1個結點（k>=1）
性質3：包含n個結點的二叉樹的高度至少為(log2n)+1
性質4：在任意一棵二叉樹中，若終端結點的個數為n0，度為2的結點數為n2，則n0=n2+1
3、性質4的證明
證明：因為二叉樹中所有結點的度數均不大于2，不妨設n0表示度為0的結點個數，n1表示度為1的結點個數，n2表示度為2的結點個數。三類結點加起來為總結點個數，于是便可得到：n=n0+n1+n2 (1)
由度之間的關系可得第二個等式：n=n0*0+n1*1+n2*2+1即n=n1+2n2+1 (2)
将（1）（2）組合在一起可得到n0=n2+1
三、滿二叉樹、完全二叉樹和二叉查找樹
1、滿二叉樹
定義：高度為h，并且由2h-1個結點組成的二叉樹，稱為滿二叉樹
2、完全二叉樹
定義：一棵二叉樹中，隻有最下面兩層結點的度可以小于2，并且最下層的葉結點集中在靠左的若幹位置上，這樣的二叉樹稱為完全二叉樹。
特點：葉子結點隻能出現在最下層和次下層，且最下層的葉子結點集中在樹的左部。顯然，一棵滿二叉樹必定是一棵完全二叉樹，而完全二叉樹未必是滿二叉樹。
面試題：如果一個完全二叉樹的結點總數為768個，求葉子結點的個數。
由二叉樹的性質知：n0=n2+1，将之帶入768=n0+n1+n2中得：768=n1+2n2+1，因為完全二叉樹度為1的結點個數要麼為0，要麼為1，那麼就把n1=0或者1都代入公式中，很容易發現n1=1才符合條件。是以算出來n2=383，是以葉子結點個數n0=n2+1=384。
總結規律：如果一棵完全二叉樹的結點總數為n，那麼葉子結點等于n/2（當n為偶數時）或者(n+1)/2（當n為奇數時）
3、二叉查找樹
定義：二叉查找樹又被稱為二叉搜尋樹。設x為二叉查找樹中的一個結點，x結點包含關鍵字key，結點x的key值計為key[x]。如果y是x的左子樹中的一個結點，則key[y]<=key[x]；如果y是x的右子樹的一個結點，則key[y]>=key[x]
在二叉查找樹種：
（1）若任意結點的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值。
（2）任意結點的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值。
（3）任意結點的左、右子樹也分别為二叉查找樹。
（4）沒有鍵值相等的結點。
import java.util.ArrayList;
import java.util.List;
public class bintree {
public bintree left;
public bintree right;
public bintree root;
// 資料域
private Object data;
// 存節點
public List<bintree> datas;
public bintree(bintree left, bintree right, Object data){
this.left=left;
this.right=right;
this.data=data;
}
// 将初始的左右孩子值為空
public bintree(Object data){
this(null,null,data);
}
public bintree() {
}
public void creat(Object[] objs){
datas=new ArrayList<bintree>();
// 将一個數組的值依次轉換為Node節點
for(Object o:objs){
datas.add(new bintree(o));
}
// 第一個數為根節點
root=datas.get(0);
// 建立二叉樹
for (int i = 0; i <objs.length/2; i++) {
// 左孩子
datas.get(i).left=datas.get(i*2+1);
// 右孩子
if(i*2+2<datas.size()){//避免偶數的時候 下标越界
datas.get(i).right=datas.get(i*2+2);
}
}
}
//先序周遊
public void preorder(bintree root){
if(root!=null){
System.out.println(root.data);
preorder(root.left);
preorder(root.right);
}
}
//中序周遊
public void inorder(bintree root){
if(root!=null){
inorder(root.left);
System.out.println(root.data);
inorder(root.right);
}
}
// 後序周遊
public void afterorder(bintree root){
if(root!=null){
System.out.println(root.data);
afterorder(root.left);
afterorder(root.right);
}
}
public static void main(String[] args) {
bintree bintree=new bintree();
Object []a={2,4,5,7,1,6,12,32,51,22};
bintree.creat(a);
bintree.preorder(bintree.root);
}
}
要求：從鍵盤輸入數，存為二叉樹結構并列印。 要求：從鍵盤輸入數，存為二叉樹結構并列印。
import java.util.Scanner;
public class btree {
private btree left,right;
private char data;
public btree creat(String des){
Scanner scanner=new Scanner(System.in);
System.out.println("des:"+des);
String str=scanner.next();
if(str.charAt(0)<'a')return null;
btree root=new btree();
root.data=str.charAt(0);
root.left=creat(str.charAt(0)+"左子樹");
root.right=creat(str.charAt(0)+"右子樹");
return root;
}
public void midprint(btree btree){
// 中序周遊
if(btree!=null){
midprint(btree.left);
System.out.print(btree.data+" ");
midprint(btree.right);
}
}
public void firprint(btree btree){
// 先序周遊
if(btree!=null){
System.out.print(btree.data+" ");
firprint(btree.left);
firprint(btree.right);
}
}
public void lastprint(btree btree){
// 後序周遊
if(btree!=null){
lastprint(btree.left);
lastprint(btree.right);
System.out.print(btree.data+" ");
}
}
public static void main(String[] args) {
btree tree = new btree();
btree newtree=tree.creat("根節點");
tree.firprint(newtree);
System.out.println();
tree.midprint(newtree);
System.out.println();
tree.lastprint(newtree);
}
} 輸出結果：
des:根節點
a
des:a左子樹
e
des:e左子樹
c
des:c左子樹
1
des:c右子樹
des:e右子樹
b
des:b左子樹
des:b右子樹
des:a右子樹
d
des:d左子樹
f
des:f左子樹
des:f右子樹
des:d右子樹
a e c b d f 先序
c e b a f d 中序
c b e f d a 後序
二叉樹的周遊次序：
前序順序是根節點排最先，然後同級先左後右；中序順序是先左後根最後右；後序順序是先左後右最後根。
例如：
比如上圖二叉樹周遊結果
前序周遊：ABCDEFGHK
中序周遊：BDCAEHGKF
後序周遊：DCBHKGFEA
分析中序周遊如下圖，中序比較重要（java很多樹排序是基于中序，後面講解分析）
我是一條，一個在網際網路摸爬滾打的程式員。