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

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

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

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

public class Node {
    //結(jié)點(diǎn)中存儲(chǔ)的數(shù)據(jù)
    Object data;
    //結(jié)點(diǎn)的左子樹(shù)
    Node left;
    //結(jié)點(diǎn)的右子樹(shù)
    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ù)的遍歷實(shí)現(xiàn)

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

2.1 前序遍歷

public void prevOrderTraversal(Node root){
    //若根節(jié)點(diǎn)為null，直接返回
    if(root == null){
        return;
    }
    //先序遍歷，表示先訪問(wèn)根節(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時(shí)將A結(jié)點(diǎn)作為參數(shù)傳入，即可得到打印的二叉樹(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)的左子樹(shù)
    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的右子樹(shù)
    inOrderTraversal(root.right);
}

中序遍歷的代碼編程如上，先遍歷當(dāng)前結(jié)點(diǎn)root的左子樹(shù)，接著將當(dāng)前結(jié)點(diǎn)root中元素輸出，最后遍歷當(dāng)前結(jié)點(diǎn)root的右子樹(shù)。調(diào)用上述inOrderTraversal函數(shù)，將A結(jié)點(diǎn)作為參數(shù)傳入?？梢缘玫街行蚨鏄?shù)中序遍歷的結(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)的左子樹(shù)
    postOrderTraversal(root.left);
    //2、先遍歷當(dāng)前結(jié)點(diǎn)的右子樹(shù)
    postOrderTraversal(root.right);
    //3、最后當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)data
    System.out.printf("%s ",root.data);
}

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

2.4 層序遍歷(廣度遍歷)

前面三種遍歷方式前序、中序、后序均屬于深度遍歷，前文我們?cè)?jīng)提到，層序遍歷又稱(chēng)廣度遍歷。主要是按層對(duì)樹(shù)進(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>();
	//首先訪問(wèn)第1層的根節(jié)點(diǎn)
	queue.add(root);
	while(!queue.isEmpty()){
        //從隊(duì)列中取出一個(gè)結(jié)點(diǎn)，并輸出該結(jié)點(diǎn)，意味著已經(jīng)訪問(wèn)過(guò)該結(jié)點(diǎn)
        Node node = queue.poll();
        System.out.printf("%s ", node.data);
        //判斷并將該結(jié)點(diǎn)的左子樹(shù)存入到隊(duì)列中
        if(node.left != null){
            queue.add(node.left);
        }
        //判斷并將該結(jié)點(diǎn)的右子樹(shù)存入到隊(duì)列中
        if(node.right != null){
            queue.add(node.right);
        }
    }
}

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

二. 二叉查找樹(shù)

1. 二叉查找樹(shù)概念

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

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

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

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

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

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

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

2. 二叉查找樹(shù)的操作

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.4 遍歷二叉查找樹(shù)

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

三. 結(jié)語(yǔ)

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

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

最新評(píng)論