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

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

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

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

有且僅有一個(gè)特定的稱(chēng)為根（Root）的結(jié)點(diǎn)；

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

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

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

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

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

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

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

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

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

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

二叉樹(shù)的性質(zhì)：

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

深度為k的二叉樹(shù)至多有$2^k - 1$個(gè)結(jié)點(diǎn)，(k>=1)。

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

一棵深度為k且有$2^k$ - 1個(gè)結(jié)點(diǎn)的二叉樹(shù)稱(chēng)為滿二叉樹(shù)。

深度為k的，有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹(shù)中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱(chēng)之為完全二叉樹(shù)。

完全二叉樹(shù)的兩個(gè)特性：

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

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

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

二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)

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

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

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

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

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

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

遍歷二叉樹(shù)(Traversing Binary Tree)：是指按指定的規(guī)律對(duì)二叉樹(shù)中的每個(gè)結(jié)點(diǎn)訪問(wèn)一次且僅訪問(wèn)一次。

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

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

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

前序遍歷：訪問(wèn)根–>遍歷左子樹(shù)–>遍歷右子樹(shù);
中序遍歷：遍歷左子樹(shù)–>訪問(wèn)根–>遍歷右子樹(shù);
后序遍歷：遍歷左子樹(shù)–>遍歷右子樹(shù)–>訪問(wèn)根;
廣度遍歷：按照層次一層層遍歷;

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

對(duì)該二叉樹(shù)進(jìn)行深度和廣度遍歷為：

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

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

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

深度遍歷也可稱(chēng)為深度優(yōu)先遍歷（Depth-First Search，DFS），因?yàn)樗偸莾?yōu)先往深處訪問(wèn)。

先序遍歷

遞歸遍歷

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

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

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

先序非遞歸遍歷思路：

初始化一個(gè)棧，將根節(jié)點(diǎn)壓入棧中；

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

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

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

中序遍歷

遞歸遍歷

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

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

中序遞歸遍歷的思路：

先遞歸遍歷左子樹(shù)，從最后一個(gè)左子樹(shù)開(kāi)始存入數(shù)組，然后回溯遍歷雙親結(jié)點(diǎn)，再是右子樹(shù)，這樣遞歸循環(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; // 如果沒(méi)有右子樹(shù) 會(huì)再次向棧中取一個(gè)結(jié)點(diǎn)即雙親結(jié)點(diǎn)
        }
    }
    return result;
}

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

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

非遞歸遍歷的思路：

將當(dāng)前結(jié)點(diǎn)壓入棧，然后將左子樹(shù)當(dāng)做當(dāng)前結(jié)點(diǎn)，如果當(dāng)前結(jié)點(diǎn)為空，將雙親結(jié)點(diǎn)取出來(lái)，將值保存進(jìn)數(shù)組，然后將右子樹(shù)當(dāng)做當(dāng)前結(jié)點(diǎn)，進(jìn)行循環(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", "/", "-"]

寫(xiě)到這，深深的被遞歸折服。。。。服

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

非遞歸遍歷

(含大量注釋代碼的)

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

dfs(tree);

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

步驟：

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

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

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

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

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

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

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

遞歸遍歷

let result = [];
let stack = [tree]; // 先將要遍歷的樹(shù)壓入棧
let count = 0; // 用來(lái)記錄執(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ù)雜度高），用一個(gè)指針代替
        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"]

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

function bfs (node) {
    let result = [];
    let queue = [];
    queue.push(node);
    while(queue.length) {
        node = queue.shift();
        result.push(node.value); // 不要忘記訪問(wèn)
        // 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"]

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