二叉搜索樹的Java實現

為了更加深入了解二叉搜索樹，本人用Java寫了個二叉搜索樹，有興趣的同學可以一起探討探討。

　　首先，二叉搜索樹是啥？它有什麼用呢？

　　二叉搜索樹， 也稱二叉排序樹，它的每個節點的數據結構為1個父節點指針，1個左孩子指針，1個有孩子指針，還有就是自己的數據部分了，因為只有左右兩孩子，所以才叫二叉樹，在此基礎上，該二叉樹還滿足另外一個條件：每個結點的左孩子都不大於該結點&&每個結點的右孩子都大於該結點。這樣，我們隊這棵樹進行中序遍歷，就能把key從小到大排序了……

　　那麼問題來了，我都有線性表有鏈表了，我還要它干啥？兩個字！效率！

　　相比線性表，你要搜索一個key，就要執行一次線性時間，算法復雜度為O(n)；而用二叉搜索樹，算法效率是O(lgn)！這是很誘人的數字。下面我用Java實現以下二叉搜索樹，你自然就明白為什麼算法復雜度是O(lgn)了。

　　其次，寫一個數據結構，自然而然也要實現對這個數據結構的增、刪、查、改了。

　　下面是我的思路：

1. 創建樹：我是通過一個一個結點的插入來建立一棵二叉搜索樹。
2. 搜索結點：從根節點開始，進行key的比較，小了就往左走，大了就往右走，最後到了葉子結點都還沒有的話，那麼該樹就不存在要搜索的結點了。
3. 修改結點：修改其實就是查詢，在查詢之後把結點的數據部分給改了而已，這裡我就不重復去實現了。
4. 刪除結點：這個應該就是最難的了，所以我有必要詳細講，先上圖（不好意思，懶得用軟件畫圖了，將就將就下哈）：

當我們要刪除一個結點時，分如下幾種情況：

• 此結點是葉子結點，這個最簡單啦，直接把結點給釋放掉就行了。（如圖刪除9）
• 此結點只有左孩子，這個也簡單啦，直接把左子樹替換過來就行了。（如圖刪除3）
• 此結點只有右孩子，同上。（如圖刪除8）
• 此結點有左右孩子，當出現這種情況時（如圖刪除7），我們就要找出該結點的後繼結點（因為右子樹肯定存在，所以找肯定在右子樹中），然後把這個後繼結點替換到要刪除的結點中，然後繼續執行對這個後繼結點的刪除操作（遞歸刪除操作就行了）。

　　發現沒？現在我的解題思路是自頂向下去分析……自頂向下，逐級求精是一個很偉大的思想！ 　　現在問題來了！後繼結點怎麼求？我們來分析一下，當求一個結點的後繼結點時，分為以下兩種情況：

• 當該結點有右孩子時，後繼結點就在右子樹中，就是該右子樹的最小結點
• 當該結點沒有右孩子時，那後繼結點就滿足這個條件：該後繼結點是該結點的祖先&&該結點位於該結點的左子樹中（如圖中的9的後繼結點是12）

　　哎呀呀！問題又來了！最小結點咋辦！很簡單！ 　　當求一棵樹的最小結點時，那麼就要從這顆樹的根節點開始，一直往左子樹走，就能找到它的最小結點了！ 　　好了，現在問題逐步解決了！刪除結點的功能也就完成了！ 　　最後，沒代碼說個錘子，咱上代碼！ 首先，寫個測試類：

public class Test {
public static void main(String[] args) {
int[] datas={12,4,5,7,4,8,3,2,6,9};
BinTree tree=new BinTree(datas);
tree.preOrderTraverse();//先序遍歷
tree.midOrderTraverse();//中序遍歷
tree.postOrderTraverse();//後序遍歷
tree.insert(15); //插入結點
tree.search(7); //查詢結點
tree.search(100); //查詢一個不存在的結點
tree.getMax(); //獲取最大值
tree.getMin(); //獲取最小值
tree.getPre(7); //前驅結點
tree.getPre(2); //最前的前驅結點
tree.getPost(7); //後繼結點
tree.getPost(15); //最後的後繼結點
tree.delete(5); //刪除結點
tree.delete(0); //刪除一個不存在的結點
}
}

然後，二叉搜索樹：

public class BinTree {
Node root=null;
private class Node{
Node parent=null;
Node leftChild=null;
Node rightChild=null;
int key;
public Node(int data) {
this.key=data;
}
}
public BinTree(int[] datas) {
buildTree(datas);
}
private void buildTree(int[] datas) {
for (int i = 0; i < datas.length; i++) {
Node node=new Node(datas[i]);
insertNode(node);
}
}
private void insertNode(Node node) { //插入結點
Node next=this.root;
Node cur=null; //用來保存當前結點
while(next!=null){ //當到達葉子結點時，確認位置！
cur=next;
if(node.key>=cur.key){
next=next.rightChild;
}else{
next=next.leftChild;
}
}
node.parent=cur; //插入該結點！
if(cur==null){
this.root=node; //該樹為空樹，所以這個是根節點
}else if(node.key>=cur.key){
cur.rightChild=node;
}else{
cur.leftChild=node;
}
}
/*
* 插入一個數
*/
public void insert(int data){
Node node=new Node(data);
System.out.println("插入結點："+data);
insertNode(node);
this.midOrderTraverse();
}

/*
* 先序遍歷
*/
public void preOrderTraverse(){
System.out.println("先序遍歷：");
preOrderTraverse(root);
System.out.println();
}
private void preOrderTraverse(Node node){ //先序遍歷
if(node!=null){
System.out.print("-"+node.key+"-");
preOrderTraverse(node.leftChild);
preOrderTraverse(node.rightChild);
}
}
/*
* 中序遍歷
*/
public void midOrderTraverse(){
System.out.println("中序遍歷：");
midOrderTraverse(root);
System.out.println();
}
private void midOrderTraverse(Node node){ //中序遍歷
if(node!=null){
midOrderTraverse(node.leftChild);
System.out.print("-"+node.key+"-");
midOrderTraverse(node.rightChild);
}

}

/*
* 後序遍歷
*/
public void postOrderTraverse(){
System.out.println("後序遍歷：");
postOrderTraverse(root);
System.out.println();
}
private void postOrderTraverse(Node node){ //後序遍歷
if(node!=null){
System.out.print("-"+node.key+"-");
postOrderTraverse(node.leftChild);
postOrderTraverse(node.rightChild);
}
}

/*
* 搜索結點
*/
public void search(int data){
System.out.println("您要查找的是："+data);
Node node;
if((node=searchNode(new Node(data)))==null){
System.out.println("樹中沒有該結點！");
}else{
System.out.println("查找"+node.key+"成功！");
}
}

private Node searchNode(Node node){ //private供內部調用，��索結點
if(node==null){
System.out.println("輸入為空，查找失敗！");
}else{
if(root==null){
System.out.println("該樹為空樹！");
}else{ //開始查找
boolean isFound=false;
Node x=root;
Node y=null;
while(!isFound&&x!=null){ //當查到或者到了葉子節點還沒查到時，終結！
y=x;
if(node.key==x.key){
isFound=true;
}else{ //通過比較大小往下面查找
if(node.key>x.key){
x=x.rightChild;
}else{
x=x.leftChild;
}
}
}
if(isFound){ //沒找到的話，在最後返回null
return y;
}
}
}
return null;
}

/*
* 獲取最大值
*/
public void getMax(){
Node node;
if((node=getMaxNode(root))==null){
System.out.println("該樹為空！");
}else{
System.out.println("最大的結點是："+node.key);
}

}

private Node getMaxNode(Node node){ //獲取最大值
if(node!=null){
Node x=node;
Node y=null;
while(x!=null){ //一直往右遍歷直到底就是最大值了！
y=x;
x=x.rightChild;
}
return y;
}
return null;
}

/*
* 獲取最小值
*/
public void getMin(){
Node node;
if((node=getMinNode(root))==null){
System.out.println("該樹為空！");
}else{
System.out.println("最小的結點是："+node.key);
}
}
private Node getMinNode(Node node){ //獲取最小值
if(node!=null){
Node x=node;
Node y=null;
while(x!=null){ //一直往左遍歷直到底就是最小值了！
y=x;
x=x.leftChild;
}
return y;
}
return null;
}

/*
* 獲取前驅結點
*/
public void getPre(int data){
Node node=null;
System.out.println(data+"的前驅結點：");
if((node=getPreNode(searchNode(new Node(data))))==null){
System.out.println("該結點不存在或無前驅結點！");
}else{
System.out.println(data+"的前驅結點為："+node.key);
}
}

private Node getPreNode(Node node){ //獲取前驅結點
if(node==null){
return null;
}
if(node.leftChild!=null){ //當有左孩子時，前驅結點就是左子樹的最大值
return getMaxNode(node.leftChild);
}else{//當不存在左孩子時，前驅結點就是——它的祖先，而且，它在這個祖先的右子樹中。這句話自己畫圖就能理解了
Node x=node;
Node y=node.parent;
while(y!=null&&x==y.leftChild){
x=y;
y=y.parent;
}
return y;
}
}

/*
* 獲取後繼結點
*/
public void getPost(int data){
Node node=null;
System.out.println(data+"的後繼結點：");
if((node=getPostNode(searchNode(new Node(data))))==null){
System.out.println("該結點不存在或無後繼結點！");
}else{
System.out.println(data+"的後繼結點為："+node.key);
}
}

private Node getPostNode(Node node){ //獲取後繼結點
if(node==null){
return null;
}
if(node.rightChild!=null){ //當有右孩子時，前驅結點就是右子樹的最小值
return getMinNode(node.rightChild);
}else{//當不存在右孩子時，後繼結點就是——它的祖先，而且，它在這個祖先的左子樹中。這句話自己畫圖就能理解了
Node x=node;
Node y=node.parent;
while(y!=null&&x==y.rightChild){
x=y;
y=y.parent;
}
return y;
}
}


/*
* 刪除結點
*/
public void delete(int data){
Node node;
if((node=searchNode(new Node(data)))==null){//注意！這裡不能new結點！你必須從樹中找該結點！new就是初始化了
System.out.println("二叉樹中不存在此結點！");
return;
}
deleteNode(node);
System.out.println("刪除結點"+data+"後：");
this.midOrderTraverse();
}


private void deleteNode(Node node){
if(node==null){
System.out.println("刪除結點不能為空！");
return;
}
replacedNode(node);
}

private void replacedNode(Node node) { //替換結點
if(node.leftChild!=null
&&node.rightChild!=null){ //當有左右孩子時，用後繼結點替換
replacedNodeOfPost(node);
}
else
{
if(node.leftChild!=null){ //當只有左孩子時，直接用左子樹替換
node=node.leftChild;
}else if(node.rightChild!=null){ //只有右孩子時，直接有子樹替換
node=node.rightChild;
}else{ //當沒有左右孩子時，就直接釋放了這個結點
freeNode(node);
}
}
}


private void freeNode(Node node) { //釋放該結點，斷掉其與父結點的鏈接
if(node==node.parent.leftChild){
node.parent.leftChild=null;
}else{
node.parent.rightChild=null;
}
}

private void replacedNodeOfPost(Node node) {
Node y=this.getPostNode(node); //找後繼結點
node.key=y.key;
replacedNode(y); //替換了key之後，再一次遞歸把現在這個結點給替換了！
}

}

最後是測試結果：

------------------分割線-------------------------

先序遍歷：
-12--4--3--2--5--4--7--6--8--9-
中序遍歷：
-2--3--4--4--5--6--7--8--9--12-
後序遍歷：
-12--4--3--2--5--4--7--6--8--9-
插入結點：15
中序遍歷：
-2--3--4--4--5--6--7--8--9--12--15-
您要查找的是：7
查找7成功！
您要查找的是：100
樹中沒有該結點！
最大的結點是：15
最小的結點是：2
7的前驅結點：
7的前驅結點為：6
2的前驅結點：
該結點不存在或無前驅結點！
7的後繼結點：
7的後繼結點為：8
15的後繼結點：
該結點不存在或無後繼結點！
刪除結點5後：
中序遍歷：
-2--3--4--4--6--7--8--9--12--15-
二叉樹中不存在此結點！

二叉樹的常見問題及其解決程序 http://www.linuxidc.com/Linux/2013-04/83661.htm

【遞歸】二叉樹的先序建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75608.htm

在JAVA中實現的二叉樹結構 http://www.linuxidc.com/Linux/2008-12/17690.htm

【非遞歸】二叉樹的建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75607.htm

二叉樹遞歸實現與二重指針 http://www.linuxidc.com/Linux/2013-07/87373.htm

二叉樹先序中序非遞歸算法 http://www.linuxidc.com/Linux/2014-06/102935.htm

輕松搞定面試中的二叉樹題目 http://www.linuxidc.com/linux/2014-07/104857.htm