一. 二叉樹的編碼實(shí)現(xiàn)

接下來小編就帶大家，通過代碼來進(jìn)行二叉樹的編碼實(shí)現(xiàn)。

1. 定義二叉樹的結(jié)點(diǎn)

對于樹型數(shù)據(jù)結(jié)構(gòu)中的結(jié)點(diǎn)，最多可以包含三部分：結(jié)點(diǎn)數(shù)據(jù)、左孩子子樹、右孩子子樹。我們使用Java對結(jié)點(diǎn)結(jié)構(gòu)可以進(jìn)行如下定義：

public class Node {
    //結(jié)點(diǎn)中存儲的數(shù)據(jù)
    Object data;
    //結(jié)點(diǎn)的左子樹
    Node left;
    //結(jié)點(diǎn)的右子樹
    Node right;
    //結(jié)點(diǎn)的高度
    int height;
    //構(gòu)造方法
    Node(Object data){
        this.data = data;
    }
    Node(Object data,Node left,Node right){
        this.data = data;
        this.left = left;
        this.right = right;
        this.height = 0;
    }
}

2. 二叉樹的遍歷實(shí)現(xiàn)

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

2.1 前序遍歷

public void prevOrderTraversal(Node root){
    //若根節(jié)點(diǎn)為null，直接返回
    if(root == null){
        return;
    }
    //先序遍歷，表示先訪問根節(jié)點(diǎn)，故先輸出傳入的結(jié)點(diǎn)中的數(shù)據(jù)
    System.out.printf("%s",root.data);
    //遍歷當(dāng)前結(jié)點(diǎn)的左孩子結(jié)點(diǎn)
    prevOrderTraversal(root.left);
    //遍歷當(dāng)前結(jié)點(diǎn)的右孩子結(jié)點(diǎn)
    prevOrderTraversal(root.right);
}

根據(jù)上述代碼，若要執(zhí)行前序遍歷，只需要調(diào)用prevOrderTraversal時將A結(jié)點(diǎn)作為參數(shù)傳入，即可得到打印的二叉樹的前序遍歷的結(jié)果：A B D C E G F H J。

2.2 中序遍歷

public void inOrderTraversal(Node root){
    if(root == null){
        return;
    }
    //1、首先遍歷當(dāng)前root結(jié)點(diǎn)的左子樹
    inOrderTraversal(root.left);
    //2、遍歷當(dāng)前結(jié)點(diǎn)root中的數(shù)據(jù)，并進(jìn)行輸出
    System.out.printf("%s ",root.data);
    //3、遍歷當(dāng)前結(jié)點(diǎn)root的右子樹
    inOrderTraversal(root.right);
}

中序遍歷的代碼編程如上，先遍歷當(dāng)前結(jié)點(diǎn)root的左子樹，接著將當(dāng)前結(jié)點(diǎn)root中元素輸出，最后遍歷當(dāng)前結(jié)點(diǎn)root的右子樹。調(diào)用上述inOrderTraversal函數(shù)，將A結(jié)點(diǎn)作為參數(shù)傳入?？梢缘玫街行蚨鏄渲行虮闅v的結(jié)果為：B D A G E C H F I。

2.3 后序遍歷

public void postOrderTraversal(Node root){
    if(root == null){
        return;
    }
    //1、先遍歷當(dāng)前結(jié)點(diǎn)的左子樹
    postOrderTraversal(root.left);
    //2、先遍歷當(dāng)前結(jié)點(diǎn)的右子樹
    postOrderTraversal(root.right);
    //3、最后當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)data
    System.out.printf("%s ",root.data);
}

如上所示的后序遍歷操作，在調(diào)用postOrderTraversal函數(shù)時，將樹的根結(jié)點(diǎn)A作為參數(shù)傳入?？梢缘玫胶笮虮闅v的序列為：D B G E H I F C A。

2.4 層序遍歷(廣度遍歷)

前面三種遍歷方式前序、中序、后序均屬于深度遍歷，前文我們曾經(jīng)提到，層序遍歷又稱廣度遍歷。主要是按層對樹進(jìn)行結(jié)點(diǎn)的遍歷。在編程實(shí)現(xiàn)上，層序遍歷與深度遍歷的操作稍有不同，具體實(shí)現(xiàn)如下：

public void levelOrderTraversal(Node root){
    if(root == null){
        return;
    }
	Queue<Node> queue = new LinkedList<Node>();
	//首先訪問第1層的根節(jié)點(diǎn)
	queue.add(root);
	while(!queue.isEmpty()){
        //從隊(duì)列中取出一個結(jié)點(diǎn)，并輸出該結(jié)點(diǎn)，意味著已經(jīng)訪問過該結(jié)點(diǎn)
        Node node = queue.poll();
        System.out.printf("%s ", node.data);
        //判斷并將該結(jié)點(diǎn)的左子樹存入到隊(duì)列中
        if(node.left != null){
            queue.add(node.left);
        }
        //判斷并將該結(jié)點(diǎn)的右子樹存入到隊(duì)列中
        if(node.right != null){
            queue.add(node.right);
        }
    }
}

如上述代碼所示，在進(jìn)行層序遍歷(廣度遍歷)時，我們借用了前面已經(jīng)學(xué)習(xí)過的數(shù)據(jù)結(jié)構(gòu)隊(duì)列Queue，將每次訪問的結(jié)點(diǎn)輸出后，同時將結(jié)點(diǎn)的左右子樹存入到隊(duì)列中。因?yàn)槲覀冎狸?duì)列的特點(diǎn)是，元素輸入的順序與輸出的順序會保持一致，因此在每次取數(shù)據(jù)時，總是先取出之前存入的數(shù)據(jù)；同時，又會把下一層數(shù)據(jù)(左右子樹)存入隊(duì)列中。最終，上述代碼對樹的層序遍歷結(jié)果是：A B C D E F G H I。

二. 二叉查找樹

1. 二叉查找樹概念

二叉查找樹，全稱為Binary Search Tree，簡稱BST。從名字中我們?nèi)菀桌斫?，二叉查找樹是在二叉樹的基礎(chǔ)上，同時具備了某些特性的一種特殊的二叉樹型結(jié)構(gòu)。二叉查找樹相較于二叉樹，額外滿足以下幾個條件：

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

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

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

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

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

如上圖所示，就是一棵二叉查找樹：在此二叉查找樹中，任意的子樹都滿足左子樹結(jié)點(diǎn)數(shù)值 < 父結(jié)點(diǎn)數(shù)值 < 右子樹結(jié)點(diǎn)數(shù)值的規(guī)律。

2. 二叉查找樹的操作

二叉查找樹最簡單的操作是結(jié)點(diǎn)查找，其次，因?yàn)檎麄€二叉查找樹都滿足從左至右是有序的，因此如果二叉查找樹的結(jié)點(diǎn)數(shù)量發(fā)生變化，就會引起二叉查找樹需要重新調(diào)整的操作，所以，我們此處還會討論二叉查找樹新增結(jié)點(diǎn)和刪除結(jié)點(diǎn)的操作，最后二叉查找樹與普通二叉樹一樣，都可以進(jìn)行最基本的遍歷操作。

接下來，我們依次討論：結(jié)點(diǎn)查找、新增結(jié)點(diǎn)、刪除結(jié)點(diǎn)、遍歷二叉查找樹。

2.1 結(jié)點(diǎn)查找

我們通過示例進(jìn)行說明結(jié)點(diǎn)查找的邏輯，如下所示：

上圖中是一個二叉查找樹，現(xiàn)在我們希望查找數(shù)值5所在的結(jié)點(diǎn)。其具體的步驟如下：

①. 訪問根節(jié)點(diǎn)，根結(jié)點(diǎn)數(shù)值位7；

②. 要查找的數(shù)值5 < 7，因此訪問結(jié)點(diǎn)7的左子樹結(jié)點(diǎn)，并獲得左子樹結(jié)點(diǎn)數(shù)值4；

③. 要查找的數(shù)值5 > 4，因此訪問結(jié)點(diǎn)4的右子樹結(jié)點(diǎn)，并獲得右子樹結(jié)點(diǎn)數(shù)值6；

④. 要查找的數(shù)值5 < 6，因此訪問結(jié)點(diǎn)6的左子樹結(jié)點(diǎn)，并獲得左子樹結(jié)點(diǎn)數(shù)值5；

⑤. 要查找的數(shù)值5 == 5，因此表示找到了目標(biāo)數(shù)值5所在的結(jié)點(diǎn)。

時間復(fù)雜度分析：假設(shè)一課二叉查找樹結(jié)點(diǎn)的個數(shù)為n，我們會發(fā)現(xiàn)在進(jìn)行查找時，總是會先判斷要查找的數(shù)值和當(dāng)前結(jié)點(diǎn)的數(shù)值的大小，然后根據(jù)判斷結(jié)果，選擇其中一側(cè)進(jìn)行繼續(xù)查找；而不符合條件的另外一側(cè)子樹，可以直接放棄，因?yàn)槲覀冎蓝娌檎覙鋸淖笾劣铱偸怯行虻摹＿@種從左至右有序的二叉查找樹，在進(jìn)行查找時，可以極大的節(jié)省時間。實(shí)際上，使用二叉查找樹查找某個結(jié)點(diǎn)，所需要的時間復(fù)雜度為O(log 2 n) ，該時間復(fù)雜度與樹的深度O(log2n)是一樣的。

2.2 新增結(jié)點(diǎn)

依然以上述二叉查找樹為例，現(xiàn)在要插入數(shù)值為3的結(jié)點(diǎn)，示意圖如下：

如上圖，插入數(shù)值為3的結(jié)點(diǎn)的步驟如下：

①. 訪問根結(jié)點(diǎn)，獲得根結(jié)點(diǎn)數(shù)值7；

②. 要插入結(jié)點(diǎn)的數(shù)值3 < 7，因此訪問根結(jié)點(diǎn)的左子樹，并獲得左子樹結(jié)點(diǎn)的數(shù)值4；

③. 要插入結(jié)點(diǎn)的數(shù)值3 < 4，因此訪問根結(jié)點(diǎn)的左子樹，并獲得左子樹結(jié)點(diǎn)的數(shù)值2；

④. 要插入結(jié)點(diǎn)的數(shù)值3 > 2，因此訪問根結(jié)點(diǎn)的右子樹，但右子樹為空；

⑤. 右子樹為空，即意味著找到了要插入的位置，即將新增的數(shù)值位3的結(jié)點(diǎn)作為結(jié)點(diǎn)2的右子樹。

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

2.3 刪除結(jié)點(diǎn)

刪除結(jié)點(diǎn)的操作與前面的查找和增加操作不太一樣，刪除操作需要分不同的情況進(jìn)行討論，原因是刪除操作會使二叉查找樹的結(jié)點(diǎn)減少，刪除后需要讓剩余的結(jié)點(diǎn)繼續(xù)滿足二叉查找樹的規(guī)則和特點(diǎn)，就可能需要做出調(diào)整。

具體的，我們可以將刪除結(jié)點(diǎn)操作分為三種情況：刪除葉子結(jié)點(diǎn)、刪除結(jié)點(diǎn)有1個子樹、刪除結(jié)點(diǎn)有2個子樹。下面，我們詳細(xì)進(jìn)行討論：

2.3.1 刪除葉子結(jié)點(diǎn)

刪除葉子結(jié)點(diǎn)是最簡單的操作，因?yàn)槿~子結(jié)點(diǎn)是最底層的結(jié)點(diǎn)，因此不需要任何的調(diào)整，直接刪除即可。刪除葉子結(jié)點(diǎn)不會對二叉查找樹的性質(zhì)產(chǎn)生影響。

2.3.2 刪除結(jié)點(diǎn)有1個子樹

當(dāng)要刪除的結(jié)點(diǎn)有1個子樹時（可能是左子樹，也可能是右子樹）。我們需要將刪除結(jié)點(diǎn)的子樹結(jié)點(diǎn)，替換到刪除結(jié)點(diǎn)的位置。比如，以下圖為例：

如上圖所示，我們希望刪除數(shù)值位6的結(jié)點(diǎn)。由于結(jié)點(diǎn)6有一棵數(shù)值位5的左子樹。因此，在將結(jié)點(diǎn)6刪除后，將子結(jié)點(diǎn)5放在原來結(jié)點(diǎn)6的位置上，如上右圖所示。

通過上述案例操作我們可以總結(jié)：當(dāng)刪除結(jié)點(diǎn)有1個子樹結(jié)點(diǎn)時，直接將子結(jié)點(diǎn)放在刪除結(jié)點(diǎn)的位置。

2.3.3 刪除結(jié)點(diǎn)有2個子樹

當(dāng)刪除結(jié)點(diǎn)有2個子樹時，可以借助二叉樹的中序遍歷結(jié)果進(jìn)行操作。具體步驟為：

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

(2). 找到要刪除結(jié)點(diǎn)數(shù)值的前驅(qū)結(jié)點(diǎn)數(shù)值；

(3). 使用前驅(qū)結(jié)點(diǎn)數(shù)值替換刪除的結(jié)點(diǎn)。

以下圖為例：要刪除二叉查找樹的數(shù)值9所在的結(jié)點(diǎn)

如上圖所示，刪除步驟如下：

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

②. 確定要刪除數(shù)值9的結(jié)點(diǎn)；

③. 在中序遍歷結(jié)果序列中找到9的前驅(qū)8；

④. 使用數(shù)值8結(jié)點(diǎn)替換結(jié)點(diǎn)9，替換后入上右圖所示。

2.4 遍歷二叉查找樹

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

三. 結(jié)語

通過本篇內(nèi)容，就帶大家一起學(xué)習(xí)了二叉樹的Java編程實(shí)現(xiàn)，其實(shí)，前序遍歷、中序遍歷、后序遍歷的編程實(shí)現(xiàn)原理都是相同的，只是遍歷的順序不同而已。同時，在進(jìn)行編程實(shí)現(xiàn)時，我們發(fā)現(xiàn)，無論前序、中序還是后序遍歷，都出現(xiàn)了在函數(shù)內(nèi)部繼續(xù)調(diào)用函數(shù)本身的現(xiàn)象，在計(jì)算機(jī)編程中，我們把程序調(diào)用自己本身的折中操作稱之為遞歸。各位感興趣的讀者，可以自己查閱資料，了解遞歸的相關(guān)概念和特點(diǎn)。

以上就是學(xué)習(xí)Java之二叉樹的編碼實(shí)現(xiàn)過程詳解的詳細(xì)內(nèi)容，更多關(guān)于Java二叉樹實(shí)現(xiàn)的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論