前言

在上一篇文章中，帶大家一起學習認識了樹型資料結構的定義和特點，并特別介紹了二叉樹的遍歷操作，分別有：前序遍歷、中序遍歷、后序遍歷，前中后的核心區別是根據根節點在遍歷程序中的位置決定的，即：根節點在最前面的稱之為中序遍歷，根節點在中間的稱之為中序遍歷，根節點在最后的稱之為后序遍歷，需要大家掌握根據樹形結構寫出對應的遍歷序列結果的能力，

全文大約【3700】 字，不說廢話，只講可以讓你學到技術、明白原理的純干貨！本文帶有豐富的案例及配圖視頻，讓你更好地理解和運用文中的技術概念，并可以給你帶來具有足夠啟迪的思考...

一. 二叉樹的編碼實作

接下來=就帶大家，通過代碼來進行二叉樹的編碼實作，

1. 定義二叉樹的結點

對于樹型資料結構中的結點，最多可以包含三部分：結點資料、左孩子子樹、右孩子子樹，我們使用Java對結點結構可以進行如下定義：

public class Node {
    //結點中存盤的資料
    Object data;
    //結點的左子樹
    Node left;
    //結點的右子樹
    Node right;
    //結點的高度
    int height;
	
    //構造方法
    Node(Object data){
        this.data = https://www.cnblogs.com/qian-fen/p/data;
    }

    Node(Object data,Node left,Node right){
        this.data = data;
        this.left = left;
        this.right = right;
        this.height = 0;
    }
    
}

2. 二叉樹的遍歷實作

如上圖所示，二叉樹的根節點為A，向下第二層為B結點、C結點，依次類推，根據上圖，我們很容易知道，若我們要對二叉樹進行遍歷，只需要從A結點出發，按照對應的前、中、后等不同的邏輯順序進行遍歷即可，因此，我們需要明確：在遍歷二叉樹時，只需要知道二叉樹根節點即可，

2.1 前序遍歷

public void prevOrderTraversal(Node root){
    //若根節點為null，直接回傳
    if(root == null){
        return;
    }
	//先序遍歷，表示先訪問根節點，故先輸出傳入的結點中的資料
	System.out.printf("%s",root.data);

	//遍歷當前結點的左孩子結點
	prevOrderTraversal(root.left);
	//遍歷當前結點的右孩子結點
	prevOrderTraversal(root.right);
}

根據上述代碼，若要執行前序遍歷，只需要呼叫prevOrderTraversal時將A結點作為引數傳入，即可得到列印的二叉樹的前序遍歷的結果：A B D C E G F H J，

2.2 中序遍歷

public void inOrderTraversal(Node root){
    if(root == null){
        return;
    }
	//1、首先遍歷當前root結點的左子樹
	inOrderTraversal(root.left);

	//2、遍歷當前結點root中的資料，并進行輸出
	System.out.printf("%s ",root.data);

	//3、遍歷當前結點root的右子樹
	inOrderTraversal(root.right);
}

中序遍歷的代碼編程如上，先遍歷當前結點root的左子樹，接著將當前結點root中元素輸出，最后遍歷當前結點root的右子樹，呼叫上述inOrderTraversal函式，將A結點作為引數傳入，可以得到中序二叉樹中序遍歷的結果為：B D A G E C H F I，

2.3 后序遍歷

public void postOrderTraversal(Node root){
    if(root == null){
        return;
    }
	//1、先遍歷當前結點的左子樹
	postOrderTraversal(root.left);
	//2、先遍歷當前結點的右子樹
	postOrderTraversal(root.right);
	//3、最后當前結點的資料data
	System.out.printf("%s ",root.data);
}

如上所示的后序遍歷操作，在呼叫postOrderTraversal函式時，將樹的根結點A作為引數傳入，可以得到后序遍歷的序列為：D B G E H I F C A，

2.4 層序遍歷(廣度遍歷)

前面三種遍歷方式前序、中序、后序均屬于深度遍歷，前文我們曾經提到，層序遍歷又稱廣度遍歷，主要是按層對樹進行結點的遍歷，在編程實作上，層序遍歷與深度遍歷的操作稍有不同，具體實作如下：

public void levelOrderTraversal(Node root){
    if(root == null){
        return;
    }

	Queue<Node> queue = new LinkedList<Node>();
	//首先訪問第1層的根節點
	queue.add(root);

	while(!queue.isEmpty()){
        //從佇列中取出一個結點，并輸出該結點，意味著已經訪問過該結點
        Node node = queue.poll();
        System.out.printf("%s ", node.data);

        //判斷并將該結點的左子樹存入到佇列中
        if(node.left != null){
            queue.add(node.left);
        }

        //判斷并將該結點的右子樹存入到佇列中
        if(node.right != null){
            queue.add(node.right);
        }
    }
}

如上述代碼所示，在進行層序遍歷(廣度遍歷)時，我們借用了前面已經學習過的資料結構佇列Queue，將每次訪問的結點輸出后，同時將結點的左右子樹存入到佇列中，因為我們知道佇列的特點是，元素輸入的順序與輸出的順序會保持一致，因此在每次取資料時，總是先取出之前存入的資料；同時，又會把下一層資料(左右子樹)存入佇列中，最終，上述代碼對樹的層序遍歷結果是：A B C D E F G H I，

二. 二叉查找樹

1. 二叉查找樹概念

二叉查找樹，全稱為Binary Search Tree，簡稱BST，從名字中我們容易理解，二叉查找樹是在二叉樹的基礎上，同時具備了某些特性的一種特殊的二叉樹型結構，二叉查找樹相較于二叉樹，額外滿足以下幾個條件：

(1). 若左子樹不為空，則左子樹上的所有結點的值均小于根結點位置上的值；

(2). 若右子樹不為空，則右子樹上的所有結點的值均大于根結點位置上的值；

(3). 左、右子樹也都是二叉查找樹，

總結上述幾個條件的，我們可以用一居話概括二叉查找樹的特點，左子樹的數值小于根結點點數值，根結點數值小于右子樹結點數值，整個二叉樹結點的數值從左至右是有序的，

基于以上所總結的二叉查找樹的特點，有的資料和教材也把查找樹稱之為二叉搜索樹，以及二叉排序樹(Binary Sort Tree，簡稱BST)，因此，大家要記住以下結論特征：左子樹結點數值 < 根結點數值 < 右子樹結點數值，

如上圖所示，就是一棵二叉查找樹：在此二叉查找樹中，任意的子樹都滿足左子樹結點數值 < 父結點數值 < 右子樹結點數值的規律，

2. 二叉查找樹的操作

二叉查找樹最簡單的操作是結點查找，其次，因為整個二叉查找樹都滿足從左至右是有序的，因此如果二叉查找樹的結點數量發生變化，就會引起二叉查找樹需要重新調整的操作，所以，我們此處還會討論二叉查找樹新增結點和洗掉結點的操作，最后二叉查找樹與普通二叉樹一樣，都可以進行最基本的遍歷操作，

接下來，我們依次討論：結點查找、新增結點、洗掉結點、遍歷二叉查找樹，

2.1 結點查找

我們通過示例進行說明結點查找的邏輯，如下所示：

上圖中是一個二叉查找樹，現在我們希望查找數值5所在的結點，其具體的步驟如下：

①. 訪問根節點，根結點數值位7；

②. 要查找的數值5 < 7，因此訪問結點7的左子樹結點，并獲得左子樹結點數值4；

③. 要查找的數值5 > 4，因此訪問結點4的右子樹結點，并獲得右子樹結點數值6；

④. 要查找的數值5 < 6，因此訪問結點6的左子樹結點，并獲得左子樹結點數值5；

⑤. 要查找的數值5 == 5，因此表示找到了目標數值5所在的結點，

時間復雜度分析：假設一課二叉查找樹結點的個數為n，我們會發現在進行查找時，總是會先判斷要查找的數值和當前結點的數值的大小，然后根據判斷結果，選擇其中一側進行繼續查找；而不符合條件的另外一側子樹，可以直接放棄，因為我們知道二叉查找樹從左至右總是有序的，這種從左至右有序的二叉查找樹，在進行查找時，可以極大的節省時間，實際上，使用二叉查找樹查找某個結點，所需要的時間復雜度為O(log 2 n) ，該時間復雜度與樹的深度O(log2n)是一樣的，

2.2 新增結點

依然以上述二叉查找樹為例，現在要插入數值為3的結點，示意圖如下：

如上圖，插入數值為3的結點的步驟如下：

①. 訪問根結點，獲得根結點數值7；

②. 要插入結點的數值3 < 7，因此訪問根結點的左子樹，并獲得左子樹結點的數值4；

③. 要插入結點的數值3 < 4，因此訪問根結點的左子樹，并獲得左子樹結點的數值2；

④. 要插入結點的數值3 > 2，因此訪問根結點的右子樹，但右子樹為空；

⑤. 右子樹為空，即意味著找到了要插入的位置，即將新增的數值位3的結點作為結點2的右子樹，

時間復雜度分析：根據插入的步驟，我們可以非常容易的理解插入結點的操作時間復雜度也為O(log2n)，與查找結點時間復雜度相同，

2.3 洗掉結點

洗掉結點的操作與前面的查找和增加操作不太一樣，洗掉操作需要分不同的情況進行討論，原因是洗掉操作會使二叉查找樹的結點減少，洗掉后需要讓剩余的結點繼續滿足二叉查找樹的規則和特點，就可能需要做出調整，

具體的，我們可以將洗掉結點操作分為三種情況：洗掉葉子結點、洗掉結點有1個子樹、洗掉結點有2個子樹，下面，我們詳細進行討論：

2.3.1 洗掉葉子結點

洗掉葉子結點是最簡單的操作，因為葉子結點是最底層的結點，因此不需要任何的調整，直接洗掉即可，洗掉葉子結點不會對二叉查找樹的性質產生影響，

2.3.2 洗掉結點有1個子樹

當要洗掉的結點有1個子樹時（可能是左子樹，也可能是右子樹），我們需要將洗掉結點的子樹結點，替換到洗掉結點的位置，比如，以下圖為例：

如上圖所示，我們希望洗掉數值位6的結點，由于結點6有一棵數值位5的左子樹，因此，在將結點6洗掉后，將子結點5放在原來結點6的位置上，如上右圖所示，

通過上述案例操作我們可以總結：當洗掉結點有1個子樹結點時，直接將子結點放在洗掉結點的位置，

2.3.3 洗掉結點有2個子樹

當洗掉結點有2個子樹時，可以借助二叉樹的中序遍歷結果進行操作，具體步驟為：

(1). 找出二叉查找樹的中序遍歷序列；

(2). 找到要洗掉結點數值的前驅結點數值；

(3). 使用前驅結點數值替換洗掉的結點，

以下圖為例：要洗掉二叉查找樹的數值9所在的結點

如上圖所示，洗掉步驟如下：

①. 根據圖示的二叉查找樹，得到中序遍歷結果：1 2 4 5 6 7 8 9 10 12；

②. 確定要洗掉數值9的結點；

③. 在中序遍歷結果序列中找到9的前驅8；

④. 使用數值8結點替換結點9，替換后入上右圖所示，

2.4 遍歷二叉查找樹

我們已經知道二叉查找樹是具有特殊性質的二叉樹，因此二叉查找樹的遍歷與二叉樹的遍歷規則完全一致，此處我們就不再贅述，

四. 結語

通過本篇內容，就帶大家一起學習了二叉樹的Java編程實作，其實，前序遍歷、中序遍歷、后序遍歷的編程實作原理都是相同的，只是遍歷的順序不同而已， 同時，在進行編程實作時，我們發現，無論前序、中序還是后序遍歷，都出現了在函式內部繼續呼叫函式本身的現象，在計算機編程中，我們把程式呼叫自己本身的折中操作稱之為遞回，各位感興趣的讀者，可以自己查閱資料，了解遞回的相關概念和特點，

以上就是我們本篇的全部內容啦，大家get了嗎~

沒太明白的可以仔細看我們的視頻講解：零基礎學Java快速入門

更多干貨知識、學習路線圖，掃描文末二維碼可得↓↓↓

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/555980.html

標籤：Java

上一篇：SpringMVC

下一篇：返回列表

圖文示例二叉樹的編碼實作程序

前言