js 中二叉樹的深度遍歷與廣度遍歷(遞歸實現(xiàn)與非遞歸實現(xiàn))

Yuanf 發(fā)布于2019-08-23 11:38 / 1438人閱讀

摘要：樹中結(jié)點的最大層次稱為樹的深度或高度。二叉樹有深度遍歷和廣度遍歷，深度遍歷有前序中序和后序三種遍歷方法。二叉樹的前序遍歷可以用來顯示目錄結(jié)構(gòu)等中序遍歷可以實現(xiàn)表達式樹，在編譯器底層很有用后序遍歷可以用來實現(xiàn)計算目錄內(nèi)的文件及其信息等。

樹的簡介

棧、隊列、鏈表等數(shù)據(jù)結(jié)構(gòu)，都是順序數(shù)據(jù)結(jié)構(gòu)。而樹是非順序數(shù)據(jù)結(jié)構(gòu)。樹型結(jié)構(gòu)是一類非常重要的非線性結(jié)構(gòu)。直觀地，樹型結(jié)構(gòu)是以分支關(guān)系定義的層次結(jié)構(gòu)。

樹在計算機領(lǐng)域中也有著廣泛的應(yīng)用，例如在編譯程序中，用樹來表示源程序的語法結(jié)構(gòu)；在數(shù)據(jù)庫系統(tǒng)中，可用樹來組織信息；在分析算法的行為時，可用樹來描述其執(zhí)行過程等等。

樹（Tree）是n（n>=0）個結(jié)點的有限集。在任意一棵非空樹中：

有且僅有一個特定的稱為根（Root）的結(jié)點；

當(dāng)n>1時，其余結(jié)點可分為m(m>0)個互不相交的有限集T1,T2,T3,...Tm，其中每一個集合本身又是一棵樹，并且稱為根的子樹（Subtree）。

例如，（a）是只有一個根結(jié)點的樹；（b）是有13個結(jié)點的樹，其中A是根，其余結(jié)點分成3個互不相交的子集：T1={B,E,F,K,L},t2={D,H,I,J,M};T1,T2和T3都是根A的子樹，且本身也是一棵樹。

樹的結(jié)點包含一個數(shù)據(jù)元素及若干指向其子樹的分支。

結(jié)點擁有的子樹數(shù)稱為結(jié)點的度（Degree）。例如，（b）中A的度為3，C的度為1，F(xiàn)的度為0。度為0的結(jié)點稱為葉子（Leaf）或者終端結(jié)點。度不為0的結(jié)點稱為非終端結(jié)點或分支結(jié)點。

樹的度是樹內(nèi)各結(jié)點的度的最大值。（b）的樹的度為3。結(jié)點的子樹的根稱為該結(jié)點的孩子（Child）。相應(yīng)的，該結(jié)點稱為孩子的雙親（Parent）。同一個雙親的孩子之間互稱兄弟（Sibling）。結(jié)點的祖先是從根到該結(jié)點所經(jīng)分支上的所有結(jié)點。反之，以某結(jié)點為根的子樹中的任一結(jié)點都稱為該結(jié)點的子孫。

結(jié)點的層次（Level）從根開始定義起，根為第一層，跟的孩子為第二層。若某結(jié)點在第層，則其子樹的根就在第l+1層。其雙親在同一層的結(jié)點互為堂兄弟。例如，結(jié)點G與E，F(xiàn),H,I,J互為堂兄弟。樹中結(jié)點的最大層次稱為樹的深度（Depth）或高度。（b）的樹的深度為4。

求樹的深度：看這篇：https://www.jianshu.com/p/9fc...

如果將樹中結(jié)點的各子樹看成從左至右是有次序的（即不能交換），則稱該樹為有序樹，否則稱為無序樹。在有序樹中最左邊的子樹的根稱為第一個孩子，最右邊的稱為最后一個孩子。

森林（Forest）是m（m>=0）棵互不相交的樹的集合。對樹中每個結(jié)點而言，其子樹的集合即為森林。

二叉樹

二叉樹（Binary Tree）是另一種樹型結(jié)構(gòu)，它的特點是每個結(jié)點至多只有兩棵子樹（即二叉樹中不存在度大于2的結(jié)點），并且，二叉樹的子樹有左右之分（其次序不能任意顛倒。）

二叉樹的性質(zhì)：

在二叉樹的第 i 層上至多有$2^{i-1}$個結(jié)點(i>=1)。

深度為k的二叉樹至多有$2^k - 1$個結(jié)點，(k>=1)。

對任何一棵二叉樹T，如果其終端結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0 = n2 + 1;

一棵深度為k且有$2^k$ - 1個結(jié)點的二叉樹稱為滿二叉樹。

深度為k的，有n個結(jié)點的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為k的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng)時，稱之為完全二叉樹。

完全二叉樹的兩個特性：

具有n個結(jié)點的完全二叉樹的深度為$Math.floor(log_2 n) + 1$;

如果對一棵有n個結(jié)點的完全二叉樹（其深度為$Math.floor(log_2 n) + 1$）的結(jié)點按層序編號（從第1層到第$Math.floor(log_2 n) + 1$，每層從左到右），則對任一結(jié)點（1<=i<=n）有：

如果i=1，則結(jié)點i是二叉樹的根，無雙親；如果i>1，則其雙親parent(i)是結(jié)點Math.floor(i/2)。
如果2i > n，則結(jié)點i無左孩子（結(jié)點i為葉子結(jié)點）；否則其左孩子LChild(i)是結(jié)點2i.
如果2i + 1 > n，則結(jié)點i無右孩子；否則其右孩子RChild(i)是結(jié)點2i + 1;

二叉樹的存儲結(jié)構(gòu)

順序存儲結(jié)構(gòu)

用一組連續(xù)的存儲單元依次自上而下，自左至右存儲完全二叉樹上的結(jié)點元素，即將二叉樹上編號為i的結(jié)點元素存儲在加上定義的一維數(shù)組中下標(biāo)為i-1的分量中。“0”表示不存在此結(jié)點。這種順序存儲結(jié)構(gòu)僅適用于完全二叉樹。因為，在最壞情況下，一個深度為k且只有k個結(jié)點的單支樹（樹中不存在度為2的結(jié)點）卻需要長度為2的n次方-1的一維數(shù)組。

順序：[1, 2, 3, 4, 5, , 6, , , 7]

鏈?zhǔn)酱鎯Y(jié)構(gòu)

二叉樹的結(jié)點由一個數(shù)據(jù)元素和分別指向其左右子樹的兩個分支構(gòu)成，則表示二叉樹的鏈表中的結(jié)點至少包含三個域：數(shù)據(jù)域和左右指針域。有時，為了便于找到結(jié)點的雙親，還可在結(jié)點結(jié)構(gòu)中增加一個指向其雙親結(jié)點的指針域。利用這兩種結(jié)構(gòu)所得的二叉樹的存儲結(jié)構(gòu)分別稱之為二叉鏈表和三叉鏈表。在含有n個結(jié)點的二叉鏈表中有n+1個空鏈域，我們可以利用這些空鏈域存儲其他有用信息，從而得到另一種鏈?zhǔn)酱鎯Y(jié)構(gòu)---線索鏈表。

鏈?zhǔn)剑簕 data, left, right}

二叉樹的遍歷

遍歷二叉樹(Traversing Binary Tree)：是指按指定的規(guī)律對二叉樹中的每個結(jié)點訪問一次且僅訪問一次。

二叉樹有深度遍歷和廣度遍歷，深度遍歷有前序、中序和后序三種遍歷方法。二叉樹的前序遍歷可以用來顯示目錄結(jié)構(gòu)等；中序遍歷可以實現(xiàn)表達式樹，在編譯器底層很有用；后序遍歷可以用來實現(xiàn)計算目錄內(nèi)的文件及其信息等。

二叉樹是非常重要的數(shù)據(jù)結(jié)構(gòu)，其中二叉樹的遍歷要使用到棧和隊列還有遞歸等，很多其它數(shù)據(jù)結(jié)構(gòu)也都是基于二叉樹的基礎(chǔ)演變而來的。熟練使用二叉樹在很多時候可以提升程序的運行效率，減少代碼量，使程序更易讀。

二叉樹不僅是一種數(shù)據(jù)結(jié)構(gòu)，也是一種編程思想。學(xué)好二叉樹是程序員進階的一個必然進程。

前序遍歷：訪問根–>遍歷左子樹–>遍歷右子樹;
中序遍歷：遍歷左子樹–>訪問根–>遍歷右子樹;
后序遍歷：遍歷左子樹–>遍歷右子樹–>訪問根;
廣度遍歷：按照層次一層層遍歷;

例如(a+b*c)-d/e，該表達式用二叉樹表示如圖：

對該二叉樹進行深度和廣度遍歷為：

前序遍歷：- + a b c / d e
中序遍歷：a + b * c - d / e
后序遍歷：a b c + d e / -
廣度遍歷：- + / a * d e b c

1. js中的二叉樹

上述二叉樹(a+b*c)-d/e在js中可以用對象的形式表示出來：

var tree = {
    value: "-",
    left: {
        value: "+",
        left: {
            value: "a",
        },
        right: {
            value: "*",
            left: {
                value: "b",
            },
            right: {
                value: "c",
            }
        }
    },
    right: {
        value: "/",
        left: {
            value: "d",
        },
        right: {
            value: "e",
        }
    }
}

2. js中二叉樹的深度遍歷

深度遍歷也可稱為深度優(yōu)先遍歷（Depth-First Search，DFS），因為它總是優(yōu)先往深處訪問。

先序遍歷

遞歸遍歷

let result = [];
let dfs = function (node) {
    if(node) {
        result.push(node.value);
        dfs(node.left);
        dfs(node.right);
    }
}

dfs(tree);
console.log(result); 
// ["-", "+", "a", "*", "b", "c", "/", "d", "e"]

先序遞歸遍歷思路：

先遍歷根結(jié)點，將值存入數(shù)組，然后遞歸遍歷：先左結(jié)點，將值存入數(shù)組，繼續(xù)向下遍歷；直到（二叉樹為空）子樹為空，則遍歷結(jié)束；
然后再回溯遍歷右結(jié)點，將值存入數(shù)組，這樣遞歸循環(huán)，直到（二叉樹為空）子樹為空，則遍歷結(jié)束。

非遞歸遍歷（利用棧：將遍歷到的結(jié)點都依次存入棧中，拿結(jié)果時從棧中訪問）

let dfs = function (nodes) {
    let result = [];
    let stack = [];
    stack.push(nodes);
    while(stack.length) { // 等同于 while(stack.length !== 0) 直到棧中的數(shù)據(jù)為空
        let node = stack.pop(); // 取的是棧中最后一個j
        result.push(node.value);
        if(node.right) stack.push(node.right); // 先壓入右子樹
        if(node.left) stack.push(node.left); // 后壓入左子樹
    }
    return result;
}
dfs(tree);

先序非遞歸遍歷思路：

初始化一個棧，將根節(jié)點壓入棧中；

當(dāng)棧為非空時，循環(huán)執(zhí)行步驟3到4，否則執(zhí)行結(jié)束；

從隊列取得一個結(jié)點（取的是棧中最后一個結(jié)點），將該值放入結(jié)果數(shù)組；

若該結(jié)點的右子樹為非空，則將該結(jié)點的右子樹入棧，若該結(jié)點的左子樹為非空，則將該結(jié)點的左子樹入棧；（注意：先將右結(jié)點壓入棧中，后壓入左結(jié)點，從棧中取得時候是取最后一個入棧的結(jié)點，而先序遍歷要先遍歷左子樹，后遍歷右子樹）

中序遍歷

遞歸遍歷

let result = [];
let dfs = function (node) {
     if(node) {
        dfs(node.left);
        result.push(node.value); // 直到該結(jié)點無左子樹 將該結(jié)點存入結(jié)果數(shù)組 接下來并開始遍歷右子樹
        dfs(node.right);
    }
}

dfs(tree);
console.log(result);
// ?["a", "+", "b", "*", "c", "-", "d", "/", "e"]

中序遞歸遍歷的思路：

先遞歸遍歷左子樹，從最后一個左子樹開始存入數(shù)組，然后回溯遍歷雙親結(jié)點，再是右子樹，這樣遞歸循環(huán)。

非遞歸遍歷

function dfs(node) {
    let result = [];
    let stack = [];
    while(stack.length || node) { // 是 || 不是 &&
        if(node) {
            stack.push(node);
            node = node.left;
        } else {
            node = stack.pop();
            result.push(node.value);
            //node.right && stack.push(node.right);
            node = node.right; // 如果沒有右子樹 會再次向棧中取一個結(jié)點即雙親結(jié)點
        }
    }
    return result;
}

dfs(tree);
// ["a", "+", "b", "*", "c", "-", "d", "/", "e"]

一種利用回溯法思想的代碼：
看這里：https://zhuanlan.zhihu.com/p/... 但是他的代碼有些問題。。。

非遞歸遍歷的思路：

將當(dāng)前結(jié)點壓入棧，然后將左子樹當(dāng)做當(dāng)前結(jié)點，如果當(dāng)前結(jié)點為空，將雙親結(jié)點取出來，將值保存進數(shù)組，然后將右子樹當(dāng)做當(dāng)前結(jié)點，進行循環(huán)。

后序遍歷

遞歸遍歷

result = [];
function dfs(node) {
    if(node) {
        dfs(node.left);
        dfs(node.right);
        result.push(node.value);
    }
}
dfs(tree);
console.log(result);
// ["a", "b", "c", "*", "+", "d", "e", "/", "-"]

寫到這，深深的被遞歸折服。。。。服

先走左子樹，當(dāng)左子樹沒有孩子結(jié)點時，將此結(jié)點的值放入數(shù)組中，然后回溯遍歷雙親結(jié)點的右結(jié)點，遞歸遍歷。

非遞歸遍歷

(含大量注釋代碼的)

function dfs(node) {
    let result = [];
    let stack = [];
    stack.push(node);
    while(stack.length) {
        // 不能用node.touched !== "left" 標(biāo)記‘left’做判斷，
        // 因為回溯到該結(jié)點時，遍歷右子樹已經(jīng)完成，該結(jié)點標(biāo)記被更改為‘right’ 若用標(biāo)記‘left’判斷該if語句會一直生效導(dǎo)致死循環(huán)
        if(node.left && !node.touched) { // 不要寫成if(node.left && node.touched !== "left")
            // 遍歷結(jié)點左子樹時，對該結(jié)點做 ‘left’標(biāo)記；為了子結(jié)點回溯到該（雙親）結(jié)點時，便不再訪問左子樹
            node.touched = "left";
            node = node.left;
            stack.push(node);
            continue;
        }
        if(node.right && node.touched !== "right") { // 右子樹同上
            node.touched = "right";
            node = node.right;
            stack.push(node);
            continue;
        }
        node = stack.pop(); // 該結(jié)點無左右子樹時，從棧中取出一個結(jié)點，訪問(并清理標(biāo)記)
        node.touched && delete node.touched; // 可以不清理不影響結(jié)果 只是第二次對同一顆樹再執(zhí)行該后序遍歷方法時，結(jié)果就會出錯啦因為你對這棵樹做的標(biāo)記還留在這棵樹上
        result.push(node.value);
        node = stack.length ? stack[stack.length - 1] : null;
        //node = stack.pop(); 這時當(dāng)前結(jié)點不再從棧中?。◤棾觯?，而是不改變棧數(shù)據(jù)直接訪問棧中最后一個結(jié)點
        //如果這時當(dāng)前結(jié)點去棧中?。◤棾觯?dǎo)致回溯時當(dāng)該結(jié)點左右子樹都被標(biāo)記過時 當(dāng)前結(jié)點又變成從棧中取會漏掉對結(jié)點的訪問（存入結(jié)果數(shù)組中）
    }
    return result; // 返回值
}

dfs(tree);

后序遍歷非遞歸遍歷思路：先把根結(jié)點和左樹推入棧，然后取出左樹，再推入右樹，取出，最后取根結(jié)點。

步驟：

初始化一個棧，將根節(jié)點壓入棧中，并標(biāo)記為當(dāng)前節(jié)點(node)；

當(dāng)棧為非空時，執(zhí)行步驟3，否則執(zhí)行結(jié)束；

如果當(dāng)前節(jié)點(node)有左子樹且沒有被 touched，則執(zhí)行4；如果當(dāng)前結(jié)點有右子樹，被 touched left 但沒有被 touched right 則執(zhí)行5 否則執(zhí)行6；

對當(dāng)前節(jié)點(node)標(biāo)記 touched left，將當(dāng)前節(jié)點的左子樹賦值給當(dāng)前節(jié)點(node=node.left) 并將當(dāng)前節(jié)點(node)壓入棧中，回到3；

對當(dāng)前節(jié)點(node)標(biāo)記 touched right，將當(dāng)前節(jié)點的右子樹賦值給當(dāng)前節(jié)點(node=node.right) 并將當(dāng)前節(jié)點(node)壓入棧中，回到3；

清理當(dāng)前節(jié)點(node)的 touched 標(biāo)記，彈出棧中的一個節(jié)點并訪問，然后再將棧頂節(jié)點標(biāo)記為當(dāng)前節(jié)點(item)，回到3；

3. js中二叉樹的廣度遍歷

廣度優(yōu)先遍歷二叉樹(層序遍歷)是用隊列來實現(xiàn)的，廣度遍歷是從二叉樹的根結(jié)點開始，自上而下逐層遍歷；在同一層中，按照從左到右的順序?qū)Y(jié)點逐一訪問。

遞歸遍歷

let result = [];
let stack = [tree]; // 先將要遍歷的樹壓入棧
let count = 0; // 用來記錄執(zhí)行到第一層
let bfs = function () {
    let node = stack[count];
    if(node) {
        result.push(node.value);
        if(node.left) stack.push(node.left);
        if(node.right) stack.push(node.right);
        count++;
        bfs();
    }
}
dfc();
console.log(result);
// ?["-", "+", "/", "a", "*", "d", "e", "b", "c"]

非遞歸算法

function bfs(node) {
    let result = [];
    let queue = [];
    queue.push(node);
    let pointer = 0;
    while(pointer < queue.length) {
        let node = queue[pointer++]; // // 這里不使用 shift 方法（復(fù)雜度高），用一個指針代替
        result.push(node.value);
        node.left && queue.push(node.left);
        node.right && queue.push(node.right);
    }
    return result;
}

bfs(tree);
// ["-", "+", "/", "a", "*", "d", "e", "b", "c"]

另外一種比較消耗性能的方法：不額外定義一個指針變量 pointer，使用數(shù)組的shift()方法，每次改變 queue 的數(shù)據(jù)（入棧、出棧），來讀取數(shù)據(jù)，直到棧 queue 中數(shù)據(jù)為空，執(zhí)行結(jié)束。（頻繁的改變數(shù)組，因為數(shù)組是引用類型，要改變它，要新開辟一個地址，所以比較消耗空間）

function bfs (node) {
    let result = [];
    let queue = [];
    queue.push(node);
    while(queue.length) {
        node = queue.shift();
        result.push(node.value); // 不要忘記訪問
        // console.log(node.value);
        node.left && queue.push(node.left);
        node.right && queue.push(node.right);
    }
    return result;
}
bfs(tree);
//? ["-", "+", "/", "a", "*", "d", "e", "b", "c"]

References

二叉樹與JavaScript
JavaScript與簡單算法
javascript實現(xiàn)數(shù)據(jù)結(jié)構(gòu)：樹和二叉樹,二叉樹的遍歷和基本操作
圖的基本算法（BFS和DFS）
搜索思想——DFS & BFS（基礎(chǔ)基礎(chǔ)篇）

云服務(wù)器 GPU云服務(wù)器非遞歸二叉樹遍歷二叉樹的遍歷 JS二叉樹遍歷二叉樹遍歷

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/97238.html

發(fā)表評論

登陸后可評論

0條評論

Yuanf

男|高級講師

我要關(guān)注我要私信

TA的文章

anaconda卸載tensorflow

閱讀 1612·2023-04-25 17:18
gigsgigscloud，全新馬來西亞VPS，$6.8/月，1核/500M內(nèi)存/15Gssd/40

閱讀 1949·2021-10-27 14:18
2021-09-07 統(tǒng)計二進制中1的個數(shù)

閱讀 2197·2021-09-09 09:33
學(xué)習(xí)如何用CSS變量創(chuàng)建網(wǎng)頁響應(yīng)布局 — css var()

閱讀 1893·2019-08-30 15:55
前端布局總結(jié)（持續(xù)更新）

閱讀 2087·2019-08-30 15:53
BOM-各種寬高

閱讀 3498·2019-08-29 16:17
前端培訓(xùn)-初級階段-場景實戰(zhàn)（2019-05-30）-input 搜索如何防抖，如何處理中文輸入

閱讀 3489·2019-08-26 13:57
CSS實現(xiàn)兩個球相交的粘粘效果

閱讀 1793·2019-08-26 13:46

成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲中文字幕日韩无码

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

js 中二叉樹的深度遍歷與廣度遍歷(遞歸實現(xiàn)與非遞歸實現(xiàn))

相關(guān)文章

二叉樹遍歷

JS中的二叉樹遍歷

樹和樹的算法

發(fā)表評論

0條評論

Yuanf

男|高級講師

TA的文章

anaconda卸載tensorflow

gigsgigscloud，全新馬來西亞VPS，$6.8/月，1核/500M內(nèi)存/15Gssd/40

2021-09-07 統(tǒng)計二進制中1的個數(shù)

學(xué)習(xí)如何用CSS變量創(chuàng)建網(wǎng)頁響應(yīng)布局 — css var()

前端布局總結(jié)（持續(xù)更新）

BOM-各種寬高

前端培訓(xùn)-初級階段-場景實戰(zhàn)（2019-05-30）-input 搜索如何防抖，如何處理中文輸入

CSS實現(xiàn)兩個球相交的粘粘效果

最新活動

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

js 中二叉樹的深度遍歷與廣度遍歷(遞歸實現(xiàn)與非遞歸實現(xiàn))

相關(guān)文章

發(fā)表評論

0條評論

男|高級講師

TA的文章

最新活動

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！