java中的二叉樹是什么

java中的二叉樹是什么？很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細(xì)講解，有這方面需求的人可以來學(xué)習(xí)下，希望你能有所收獲。

定義

樹是一種重要的非線性數(shù)據(jù)結(jié)構(gòu)，直觀地看，它是數(shù)據(jù)元素（在樹中稱為結(jié)點）按分支關(guān)系組織起來的結(jié)構(gòu)，很象自然界中的樹那樣。樹結(jié)構(gòu)在客觀世界中廣泛存在，如人類社會的族譜和各種社會組織機構(gòu)都可用樹形象表示。樹在計算機領(lǐng)域中也得到廣泛應(yīng)用，如在編譯源程序如下時，可用樹表示源源程序如下的語法結(jié)構(gòu)。又如在數(shù)據(jù)庫系統(tǒng)中，樹型結(jié)構(gòu)也是信息的重要組織形式之一。一切具有層次關(guān)系的問題都可用樹來描述。滿二叉樹，完全二叉樹，排序二叉樹。

深度優(yōu)先遍歷

一般我們深度優(yōu)先遍歷二叉樹有三種最常見的順序遍歷：前序、中序、后序。

前序的遍歷順序為：訪問根結(jié)點 -> 遍歷左子樹 -> 遍歷右子樹

中序的遍歷順序為：遍歷左子樹 -> 訪問根結(jié)點 -> 遍歷右子樹

后序的遍歷順序為：遍歷左子樹 -> 遍歷右子樹 -> 訪問根結(jié)點

注意這里的左右是整個子樹，而不是一個結(jié)點，因為我們需要遍歷整棵樹，所以每次遍歷都是按照這個順序去執(zhí)行，直到葉子結(jié)點。

舉個例子，假如有如下二叉樹：

前序遍歷得到的序列就是 A - B - C - D - E

中序遍歷得到的序列就是 B - A - D - C - E

后序遍歷得到的序列就是 B - D - E - C - A

思路我們就用前序遍歷來講（非常不建議去人肉遞歸，至少我的腦子吃不消三層。。。）：

第一層遞歸：

先訪問根結(jié)點，所以輸出根結(jié)點 A，然后遍歷左子樹（L1），再遍歷右子樹（R1）；

第二層遞歸：

對于 L1，先訪問根結(jié)點，所以輸出此時的根結(jié)點 B，然后發(fā)現(xiàn) B 的左右子樹為空，結(jié)束遞歸；

對于 R1，先訪問根結(jié)點，所以輸出此時的根結(jié)點 C，然后遍歷左子樹（L2），再遍歷右子樹（R2）；

第三層遞歸：

對于 L2，先訪問根結(jié)點，所以輸出此時的根結(jié)點 D，然后發(fā)現(xiàn) D 的左右子樹為空，結(jié)束遞歸；

對于 R2，先訪問根結(jié)點，所以輸出此時的根結(jié)點 E，然后發(fā)現(xiàn) E 的左右子樹為空，結(jié)束遞歸；

前中后序特征

根據(jù)前中后序的定義，其實我們不難發(fā)現(xiàn)有如下特征：

? 前序的第一個一定是 root 節(jié)點，后序的最后一個一定是 root 節(jié)點

? 每種排序的左子樹和右子樹分布都是有規(guī)律的

? 對于每一個子樹都遵循上面兩個規(guī)律的樹

這些特征也就是定義中對順序的表現(xiàn)。

各種推導(dǎo)

這邊列舉一下對于二叉樹的遍歷最基本的幾個算法題：

? 給定二叉樹得出其前/中/后序遍歷的序列；

? 根據(jù)前序和中序推導(dǎo)后序（或者推導(dǎo)整顆二叉樹）；

? 根據(jù)后序和中序推導(dǎo)前序（或者推導(dǎo)整顆二叉樹）；

對于二叉樹的遍歷，前面也講過，通常采用遞歸來做，對于遞歸，有模版可以直接套用：

public void recur(int level, int param) {
    
    // terminator
    if (level > MAX_LEVEL) {
        // process result
         return;   
    }
    
    // process current logic
    process(level, param);
    
    // drill down
    recur(level+1, newParam);
    
    // restore current status
}

這個是我這兩天看極客時間的算法訓(xùn)練營中超哥（覃超）講到的比較實用的小技巧（這個模版對于新手特別好），遵循上面的三步驟（如果有局部變量需要釋放或者額外處理則第四步去做）能比較有條理的寫出遞歸代碼。

這里拿根據(jù)前序和中序推導(dǎo)后序來舉例：

先初始化兩個序列：

int[] preSequence = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int[] inSequence = {2, 3, 1, 6, 7, 8, 5, 9, 4};

通過上面說到的幾個特征，我們已經(jīng)可以找到最小重復(fù)子問題了，每次遞歸

根據(jù)前序的第一個結(jié)點值去匹配中序中該結(jié)點值所在的索引 i，這樣我們就能得到索引 i 的前后兩部份分別對應(yīng)左右子樹，接著分別去遍歷這兩個左右子樹，然后輸出當(dāng)前前序的第一個結(jié)點值，也就是根結(jié)點。

根據(jù)自頂向下的程序設(shè)計方法，我們可以先寫出如下初始遞歸調(diào)用：

List<Integer> result = new ArrayList<>();
preAndInToPost(0, 0, preSequence.length, preSequence, inSequence, result);

第一個參數(shù)表示前序序列的第一個元素索引；

第二個參數(shù)表示中序序列的第一個元素索引；

第三個參數(shù)表示序列長度；

第四個參數(shù)表示前序序列；

第五個參數(shù)表示后序序列；

第六個參數(shù)用于保存結(jié)果；

先來考慮終止條件是什么，也就是什么時候結(jié)束遞歸，當(dāng)我們的根結(jié)點為空的時候終止，對應(yīng)這里就是序列長度為零的時候。

if (length == 0) {
    return;
}

接著考慮處理邏輯，也就是找到索引 i：

int i = 0;
while (inSequence[inIndex + i] != preSequence[preIndex]) {
    i++;
}

然后開始向下遞歸：

preAndInToPost(preIndex + 1, inIndex, i, preSequence, inSequence, result);
preAndInToPost(preIndex + i + 1, inIndex + i + 1, length - i - 1, preSequence, inSequence, result);
result.add(preSequence[preIndex]);

因為推導(dǎo)的是后序序列，所以順序如上，添加根結(jié)點的操作是在最后的。前三個參數(shù)如何得出來的呢，我們走一下第一次遍歷就可以得出來。

前序序列的第一個結(jié)點 1 在中序序列中的索引為 2，此時

左子樹的中序系列起始索引為總序列的第 1 個索引，長度為 2；

左子樹的前序序列起始索引為總序列的第 2 個索引，長度為 2；

右子樹的中序系列起始索引為總序列的第 3 個索引，長度為 length - 3；

右子樹的前序序列起始索引為總序列的第 3 個索引，長度為 length - 3；

完整代碼如下：

/**
 * 根據(jù)前序和中序推導(dǎo)后序
 *
 * @param preIndex    前序索引
 * @param inIndex     中序索引
 * @param length      序列長度
 * @param preSequence 前序序列
 * @param inSequence  中序序列
 * @param result      結(jié)果序列
 */
private void preAndInToPost(int preIndex, int inIndex, int length, int[] preSequence, int[] inSequence, List<Integer> result) {
    if (length == 0) {
        return;
    }

    int i = 0;
    while (inSequence[inIndex + i] != preSequence[preIndex]) {
        i++;
    }

    preAndInToPost(preIndex + 1, inIndex, i, preSequence, inSequence, result);
    preAndInToPost(preIndex + i + 1, inIndex + i + 1, length - i - 1, preSequence, inSequence, result);
    result.add(preSequence[preIndex]);
}

看完上述內(nèi)容是否對您有幫助呢？如果還想對相關(guān)知識有進一步的了解或閱讀更多相關(guān)文章，請關(guān)注億速云行業(yè)資訊頻道，感謝您對億速云的支持。