通過前面的學習，我們知道，有序數組可以利用二分查找法快速的查找特定的值，時間復雜度為O(log2N)，但是插入數據時很慢，時間復雜度為O(N)；鏈表的插入和刪除速度都很快，時間復雜度為O(1)，但是查找特定值很慢，時間復雜度為O(N)。
那麼，有沒有一種數據結構既能像有序數組那樣快速的查找數據，又能像鏈表那樣快速的插入數據呢？樹就能滿足這種要求。不過依然是以算法的復雜度為代價
在編程的世界裡，有一個真理叫“復雜度守恆定律”（當然，這是我杜撰的），一個程序當它降低了一個方面的復雜度，必然會在其他方面增加復雜度。這就跟談戀愛一樣，也沒有無緣無故的愛，沒有無緣無故的恨，當你跟程序談戀愛時，沒有無緣無故的易用性，也沒有無緣無故的復雜度
樹的相關概念
我們先從廣義上來討論一下樹的概念
樹其實是范疇更廣的圖的特例
下面是一個普通的非二叉樹
在程序中，節點一般用來表示實體，也就是數據結構裡存儲的那些數據項，在java這樣的面向對象的編程語言中，常用節點來表示對象
節點間的邊表示關聯節點間的路徑，沿著路徑，從一個節點到另一個節點很容易，也很快，在樹中，從一個節點到另一個節點的唯一方法就是順著邊前進。java語言中，常用引用來表示邊（C/C++中一般使用指針）
樹的頂層總是只有一個節點，它通過邊連接到第二層的多個節點，然後第二層也可以通過邊連接到第三層，以此類推。所以樹的頂部小，底部大，呈倒金字塔型，這和現實世界中的樹是相反的
如果樹的每個節點最多有兩個子節點，則稱為二叉樹。如果節點的子節點可以多余兩個，稱為多路樹
有很多關於樹的術語，在這裡不做過多的文字解釋，下面給出一個圖例，通過它可以直觀地理解樹的路徑、根、父節點、子節點、葉節點、子樹、層等概念
需要注意的是，從樹的根到任意節點有且只有一條路徑可以到達，下圖所示就不是一棵樹，它違背了這一原則
二叉搜索樹
我們從一種特殊的、使用很廣泛的二叉樹入手：二叉搜索樹。
二叉搜索樹的特點是，一個節點的左子節點的關鍵字值小於這個節點，右子節點的關鍵字值大於或等於這個父節點。下圖就是一個二叉搜索樹的示例：
關於樹，還有一個平衡樹與非平衡樹的概念。非平衡就是說樹的大部分節點在根的一邊，如下圖所示：
樹的不平衡是由數據項插入的順序造成的。如果關鍵字是隨機插入的，樹會更趨向於平衡，如果插入順序是升序或者降序，則所有的值都是右子節點或左子節點，這樣生成的樹就會不平衡了。非平衡樹的效率會嚴重退化
接下來我們就用java語言實現一個二叉搜索樹，並給出查找、插入、遍歷、刪除節點的方法
首先要有一個封裝節點的類，這個類包含節點的數據以及它的左子節點和右子節點的引用
//樹節點的封裝類
public class Node {
int age;
String name;
Node leftChild; //左子節點的引用
Node rightChild; //右子節點的引用
public Node(int age,String name){
this.age = age;
this.name = name;
}
//打印該節點的信息
public void displayNode(){
System.out.println("name:"+name+",age:"+age);
}
}
以上age，name兩個屬性用來代表該節點存儲的信息，更好的方法是將這些屬性封裝成一個對象，例如：
Person{
private int age;
private String name;
public void setAge(int age){
this.age = age;
}
public int getAge(){
return this.age;
}
public void setName(String name){
this.name = name;
}
public String getName(){
return this.name;
}
}
這樣做才更符合“面向對象”的編程思想。不過現在我們的重點是數據結構而非編程思想，所以在程序中簡化了
由於樹的結構和算法相對復雜，我們先逐步分析一下查找、插入等操作的思路，然後再寫出整個的java類
查找
我們已經知道，二叉搜索樹的特點是左子節點小於父節點，右子節點大於或等於父節點。查找某個節點時，先從根節點入手，如果該元素值小於根節點，則轉向左子節點，否則轉向右子節點，以此類推，直到找到該節點，或者到最後一個葉子節點依然沒有找到，則證明樹中沒有該節點
比如我們要在樹中查找57，執行的搜索路線如下圖所示：
插入
插入一個新節點首先要確定插入的位置，這個過程類似於查找一個不存在的節點。如下圖所示：
找到要插入的位置之後，將父節點的左子節點或者右子節點指向新節點即可
遍歷
遍歷的意思是根據一種特定順序訪問樹的每一個節點
有三種簡單的方法遍歷樹：前序遍歷、中序遍歷、後序遍歷。二叉搜索樹最常用的方法是中序遍歷，中序遍歷二叉搜索樹會使所有的節點按關鍵字升序被訪問到
遍歷樹最簡單的方法是遞歸。用該方法時，只需要做三件事（初始化時這個節點是根）：
1、調用自身來遍歷節點的左子樹
2、訪問這個節點
3、調用自身來遍歷節點的右子樹
遍歷可以應用於任何二叉樹，而不只是二叉搜索樹。遍歷的節點並不關心節點的關鍵字值，它只看這個節點是否有子節點
下圖展示了中序遍歷的過程：
對於每個節點來說，都是先訪問它的左子節點，然後訪問自己，然後在訪問右子節點
如果是前序遍歷呢？就是先訪問父節點，然後左子節點，最後右子節點；同理，後序遍歷就是先訪問左子節點，在訪問右子節點，最後訪問父節點。所謂的前序、中序、後序是針對父節點的訪問順序而言的
查找最值
在二叉搜索樹中，查找最大值、最小是是很容易實現的，從根循環訪問左子節點，直到該節點沒有左子節點為止，該節點就是最小值；從根循環訪問右子節點，直到該節點沒有右子節點為止，該節點就是最大值
下圖就展示了查找最小值的過程：
<喎?/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHAgY2xhc3M9"MsoNormal">刪除節點
樹的刪除節點操作是最復雜的一項操作。該操作需要考慮三種情況考慮：
1、該節點沒有子節點
2、該節點有一個子節點
3、該節點有兩個子節點
第一種沒有子節點的情況很簡單，只需將父節點指向它的引用設置為null即可：
第二種情況也不是很難，這個節點有兩個連接需要處理：父節點指向它的引用和它指向子節點的引用。無論要刪除的節點下面有多復雜的子樹，只需要將它的子樹上移：
還有一種特殊情況需要考慮，就是要刪除的是根節點，這時就需要把它唯一的子節點設置成根節點
下面來看最復雜的第三種情況：要刪除的節點由連個子節點。顯然，這時候不能簡單地將子節點上移，因為該節點有兩個節點，右子節點上移之後，該右子節點的左子節點和右子節點又怎麼安排呢？
這是應該想起，二叉搜索樹是按照關鍵升序排列，對每一個關鍵字來說，比它關鍵字值高的節點是它的中序後繼，簡稱後繼。刪除有兩個子節點的節點，應該用它的中序後繼來替代該節點
上圖中，我們先列出中序遍歷的順序：
5 15 20 25 30 35 40
可以看到，25的後繼是35，所以應該用30來替代25的位置。實際上就是找到比欲刪除節點的關鍵字值大的集合中的最小值。從樹的結構上來說，就是從欲刪除節點的右子節點開始，依次跳到下一層的左子節點，直到該左子節點沒有左子節點為止。下圖就是找後繼節點的示例：
從上圖中可以看到，後集結點有兩種情況：一種是欲刪除節點的右子節點沒有左子節點，那麼它本身就是後繼節點，此時，只需要將以此後繼節點為根的子樹移到欲刪除節點的位置：
另一種情況是欲刪除節點的右子節點有左子節點，這種情況就比較復雜，下面來逐步分析。首先應該意識到，後繼節點是肯定沒有左子節點的，但是可能會有右子節點
上圖中，75為欲刪除節點，77為它的後繼節點，樹變化的步驟如下：
1、把87的左子節點設置為79；
2、把77的右子節點設為以87為根的子樹；
3、把50的右子節點設置為以77為根的子樹；
4、把77的左子節點設置為62
到此為止，刪除操作終於分析完畢，包含了所有可能出現的情況。可見，二叉樹的刪除是一件非常棘手的工作，那麼我們就該反思了，刪除是必須要做的任務嗎？有沒有一種方法避開這種煩人的操作？有困難要上，沒有困難創造困難也要上的二貨精神是不能提倡的
在刪除操作不是很多的情況下，可以在節點類中增加一個布爾字段，來作為該節點是否已刪除的標志。在進行其他操作，比如查找時，之前對該節點是否已刪除進行判斷。這種思路有點逃避責任，但是在很多時候還是很管用的。本例中為了更好的深入理解二叉樹，會采用原始的、復雜的刪除方法
下面我們就根據上面的分析，寫出一個完整的二叉搜索樹類，該類中，如果有重復值，插入到右子節點，查找時也只返回第一個找到的節點
import java.util.ArrayList;
import java.util.List;
//二叉搜索樹的封裝類
public class BinaryTree {
private Node root; //根節點
public BinaryTree(){
root = null;
}
//按關鍵字查找節點
public Node find(int key){
Node cur = root; //從根節點開始查找
if(cur == null){ //如果樹為空，直接返回null
return null;
}
while(cur.age != key){
if(cur.age < key){
cur = cur.leftChild; //如果關鍵字比當前節點小，轉向左子節點
}else{
cur = cur.leftChild; //如果關鍵字比當前節點大，轉向右子節點
}
if(cur == null){ //沒有找到結果，搜索結束
return null;
}
}
return cur;
}
//插入新節點
public void insert(Node node){
if(root == null){
root = node; //如果樹為空，則新插入的節點為根節點
}else{
Node cur = root;
while(true){
if(node.age < cur.age){
if(cur.leftChild == null){ //找到了要插入節點的父節點
cur.leftChild = node;
return;
}
cur = cur.leftChild;
}else{
if(cur.rightChild == null){ //找到了要插入節點的父節點
cur.rightChild = node;
return;
}
cur = cur.rightChild;
}
}
}
}
//刪除指定節點
public boolean delete(Node node){
if(root == null){
return false; //如果為空樹，直接返回false
}
boolean isLeftChild = true; //記錄目標節點是否為父節點的左子節點
Node cur= root; //要刪除的節點
Node parent = null; //要刪除節點的父節點
while(cur.age != node.age){ //確定要刪除節點和它的父節點
parent = cur;
if(node.age < cur.age){ //目標節點小於當前節點，跳轉左子節點
cur = cur.leftChild;
}else{//目標節點大於當前節點，跳轉右子節點
isLeftChild = false;
cur = cur.rightChild;
}
if(cur == null){
return false; //沒有找到要刪除的節點
}
}
if(cur.leftChild == null && cur.rightChild == null){ //目標節點為葉子節點（無子節點）
if(cur == root){ //要刪除的為根節點
root = null;
}else if(isLeftChild){
//要刪除的不是根節點，則該節點肯定有父節點，該節點刪除後，需要將父節點指向它的引用置空
parent.leftChild = null;
}else{
parent.rightChild = null;
}
}else if(cur.leftChild == null){ //只有一個右子節點
if(cur == root){
root = cur.rightChild;
}else if(isLeftChild){
parent.leftChild = cur.rightChild;
}else{
parent.rightChild = cur.rightChild;
}
}else if(cur.rightChild == null){ //只有一個左子節點
if(cur == root){
root = cur.leftChild;
}else if(isLeftChild){
parent.leftChild = cur.leftChild;
}else{
parent.rightChild = cur.leftChild;
}
}else{ //有兩個子節點
//第一步要找到欲刪除節點的後繼節點
Node successor = cur.rightChild;
Node successorParent = null;
while(successor.leftChild != null){
successorParent = successor;
successor = successor.leftChild;
}
//欲刪除節點的右子節點就是它的後繼，證明該後繼無左子節點，則將以後繼節點為根的子樹上移即可
if(successorParent == null){
if(cur == root){ //要刪除的為根節點，則將後繼設置為根，且根的左子節點設置為欲刪除節點的做左子節點
root = successor;
root.leftChild = cur.leftChild;
}else if(isLeftChild){
parent.leftChild = successor;
successor.leftChild = cur.leftChild;
}else{
parent.rightChild = successor;
successor.leftChild = cur.leftChild;
}
}else{ //欲刪除節點的後繼不是它的右子節點
successorParent.leftChild = successor.rightChild;
successor.rightChild = cur.rightChild;
if(cur == root){
root = successor;
root.leftChild = cur.leftChild;
}else if(isLeftChild){
parent.leftChild = successor;
successor.leftChild = cur.leftChild;
}else{
parent.rightChild = successor;
successor.leftChild = cur.leftChild;
}
}
}
return true;
}
public static final int PREORDER = 1; //前序遍歷
public static final int INORDER = 2; //中序遍歷
public static final int POSTORDER = 3; //中序遍歷
//遍歷
public void traverse(int type){
switch(type){
case 1:
System.out.print("前序遍歷：\t");
preorder(root);
System.out.println();
break;
case 2:
System.out.print("中序遍歷：\t");
inorder(root);
System.out.println();
break;
case 3:
System.out.print("後序遍歷：\t");
postorder(root);
System.out.println();
break;
}
}
//前序遍歷
public void preorder(Node currentRoot){
if(currentRoot != null){
System.out.print(currentRoot.age+"\t");
preorder(currentRoot.leftChild);
preorder(currentRoot.rightChild);
}
}
//中序遍歷，這三種遍歷都用了迭代的思想
public void inorder(Node currentRoot){
if(currentRoot != null){
inorder(currentRoot.leftChild); //先對當前節點的左子樹對進行中序遍歷
System.out.print(currentRoot.age+"\t"); //然後訪問當前節點
inorder(currentRoot.rightChild); //最後對當前節點的右子樹對進行中序遍歷
}
}
//後序遍歷
public void postorder(Node currentRoot){
if(currentRoot != null){
postorder(currentRoot.leftChild);
postorder(currentRoot.rightChild);
System.out.print(currentRoot.age+"\t");
}
}
//私有方法，用迭代方法來獲取左子樹和右子樹的最大深度，返回兩者最大值
private int getDepth(Node currentNode,int initDeep){
int deep = initDeep; //當前節點已到達的深度
int leftDeep = initDeep;
int rightDeep = initDeep;
if(currentNode.leftChild != null){ //計算當前節點左子樹的最大深度
leftDeep = getDepth(currentNode.leftChild, deep+1);
}
if(currentNode.rightChild != null){ //計算當前節點右子樹的最大深度
rightDeep = getDepth(currentNode.rightChild, deep+1);
}
return Math.max(leftDeep, rightDeep);
}
//獲取樹的深度
public int getTreeDepth(){
if(root == null){
return 0;
}
return getDepth(root,1);
}
//返回關鍵值最大的節點
public Node getMax(){
if(isEmpty()){
return null;
}
Node cur = root;
while(cur.rightChild != null){
cur = cur.rightChild;
}
return cur;
}
//返回關鍵值最小的節點
public Node getMin(){
if(isEmpty()){
return null;
}
Node cur = root;
while(cur.leftChild != null){
cur = cur.leftChild;
}
return cur;
}
//以樹的形式打印出該樹
public void displayTree(){
int depth = getTreeDepth();
ArrayList currentLayerNodes = new ArrayList ();
currentLayerNodes.add(root); //存儲該層所有節點
int layerIndex = 1;
while(layerIndex <= depth){
int NodeBlankNum = (int)Math.pow(2, depth-layerIndex)-1; //在節點之前和之後應該打印幾個空位
for(int i = 0;i();
Node parentNode;
for(int i=0;i
displayTree方法按照樹的形狀打印該樹。對一顆深度為3的二叉樹的打印效果如下圖所示：
