首頁 >Java >java教程 >詳解java中二元樹的深度優先遍歷

詳解java中二元樹的深度優先遍歷

青灯夜游
青灯夜游轉載
2020-06-28 09:42:443541瀏覽

詳解java中二元樹的深度優先遍歷

這兩天在做一個二元樹相關的演算法問題,做一點學習筆記。 (連二元樹都不會?確實不熟練,平時工作也沒有要去寫二叉樹相關的演算法或資料結構的場景。因為自己菜,所以更加要努力學!)

定義

先看維基百科的解釋:在電腦科學中,二元樹(英文:Binary tree)是每個節點最多只有兩個分支(即不存在分支度大於2的節點)的樹狀結構。通常分支被稱作“左子樹”或“右子樹”。二元樹的分支具有左右次序,不能隨意顛倒。

由於二元樹本身定義的特點,具有高度的局部重複性,所以在深度優先遍歷二叉樹時,通常採用遞歸的方式去實現,這樣實現出來的程式碼非常簡潔漂亮,也比較容易看懂。

深度優先遍歷

一般我們深度優先遍歷二元樹有三種最常見的順序遍歷:前序、中序、後序。

前序的遍歷順序為:訪問根結點-> 遍歷左子樹-> 遍歷右子樹

中序的遍歷順序為:遍歷左子樹-> ; 訪問根結點-> 遍歷右子樹

後序的遍歷順序為:遍歷左子樹-> 遍歷右子樹-> 訪問根結點

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

舉個例子,假如有如下二元樹:

詳解java中二元樹的深度優先遍歷

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

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

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

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

第一層遞歸:

先訪問根結點,所以輸出根結點A,然後遍歷左子樹(L1),再遍歷右子樹(R1);

第二層遞歸:

#對於L1,先訪問根結點,所以輸出此時的根結點B,然後發現B 的左右子樹為空,結束遞歸;

對於R1,先訪問根結點,所以輸出此時的根結點C,然後遍歷左子樹( L2),再遍歷右子樹(R2);

第三層遞歸:

#對於L2,先訪問根結點,所以輸出此時的根結點D,然後發現D 的左右子樹為空,結束遞歸;

對於R2,先訪問根結點,所以輸出此時的根結點E,然後發現E 的左右子樹為空,結束遞歸;

前中後序特徵

根據前中後序的定義,其實我們不難發現有以下特徵:

• 前序的第一個一定是root 節點,後序的最後一個一定是root 節點

• 每個排序的左子樹和右子樹分佈都是有規律的

• 對於每一個子樹都遵循上面兩個規律的樹

詳解java中二元樹的深度優先遍歷

這些特徵也就是定義中對順序的表現。

各種推導

這邊列舉一下對於二元樹的遍歷最基本的幾個演算法題:

•給定二元樹得出其前/中/後序遍歷的序列;

• 根據前序和中序推導後序(或推導整顆二元樹);

• 根據後序和中序推導前序(或推導整顆二元樹);

對於二元樹的遍歷,前面也講過,通常採用遞歸來做,對於遞歸,有模版可以直接套用:

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
}

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

這裡拿根據前序和中序推導後序來舉例:

先初始化兩個序列:

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

透過上面說到的幾個特徵,我們已經可以找到最小重複子問題了,每次遞歸

根據前序的第一個結點值去匹配中序中該結點值所在的索引i,這樣我們就能得到索引i 的前後兩部分分別對應左右子樹,接著分別去遍歷這兩個左右子樹,然後輸出目前前序的第一個結點值,也就是根結點。

根據自頂向下的程式設計方法,我們可以先寫出如下初始遞歸呼叫:

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

第一個參數表示前序序列的第一個元素索引;

第二個參數表示中序序列的第一個元素索引;

第三個參數表示序列長度;

第四个参数表示前序序列;

第五个参数表示后序序列;

第六个参数用于保存结果;

先来考虑终止条件是什么,也就是什么时候结束递归,当我们的根结点为空的时候终止,对应这里就是序列长度为零的时候。

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]);

因为推导的是后序序列,所以顺序如上,添加根结点的操作是在最后的。前三个参数如何得出来的呢,我们走一下第一次遍历就可以得出来。

前序序列的第一个结点 1 在中序序列中的索引为 2,此时

左子树的中序系列起始索引为总序列的第 1 个索引,长度为 2;

左子树的前序序列起始索引为总序列的第 2 个索引,长度为 2;

右子树的中序系列起始索引为总序列的第 3 个索引,长度为 length - 3;

右子树的前序序列起始索引为总序列的第 3 个索引,长度为 length - 3;

完整代码如下:

/**
 * 根据前序和中序推导后序
 *
 * @param preIndex    前序索引
 * @param inIndex     中序索引
 * @param length      序列长度
 * @param preSequence 前序序列
 * @param inSequence  中序序列
 * @param result      结果序列
 */
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]);
}

参考链接

• 维基百科 - 二叉树(https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%8F%89%E6%A0%91)

推荐教程:《java教程

以上是詳解java中二元樹的深度優先遍歷的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文轉載於:segmentfault.com。如有侵權,請聯絡admin@php.cn刪除