用JavaScript學習資料結構與演算法 8：樹、 二元搜尋樹

簡介

這次來介紹一種名為樹( Tree )的資料結構，有基本的認識後會進入二元搜尋樹( Binary Search Tree )的介紹與實現；最後導入樹遍歷的觀念並實作深度、廣度優先( Depth-First Search、Breadth-first search)。

範例程式碼：下載

樹

基本認識與名詞

樹是一種模擬現實生活中樹幹與樹枝的資料結構，是一種非線性、且具有階層架構的資料結構，如學校的組織圖、家族的族譜等。

學校組織圖也是樹的一種應用

有了樹的概念後就來認識下樹的結構及基本名詞吧：

如上圖所示，Ａ 節點為樹的根( Root)，節點的下一層還可以有其他的節點，稱之為子節點( Child )，如 B、C 節點為 A 的子節點；若是上層的關係則稱為父節點( Parent )，如節點 B 是 I 和 J 的父節點，節點 E 是 K、L 和 M 的父節點。若節點間擁有共同的父節點，則稱為兄弟節點( Siblings )，如節點 I 與 J 有相同的父節點 B，則 I 與 J 即為兄弟節點。而沒有子節點的節點則叫做葉節點( Leaf )，如範例中的節點 I~M；每個節點所擁有的子節點數為分支度( Degree)，如節點 B 的分支度為 2，節點 E 的分支度為 3；而每個樹皆會有階層( Level )代表各個層級，如 A 節點為階層 1，I 節點為階層 3；樹深( Depth )為樹的最大階層數，從這個範例中可以得知最大的階層數為 3。

二元樹

樹依照不同的分支度可以分成很多種，其中二元樹( Binary Tree )相當廣泛的被使用；二元樹是指樹中的每一個「節點」最多只能有兩個子節點，即分支度小於或等於 2 。如下圖所示：

二元搜尋樹

二元搜尋樹( Binary Search Trees ) 其實就是二元樹的一種，只不過其內部每個節點的排列是有規則的，規則如下：

1. 二元樹中的每個節點都擁有不同的值
2. 每一個節點的資料大於其左側子節點的資料，但小於右側子節點。

典型的二元搜尋樹如下圖所示，從中可看出剛剛的兩項規則，接下來將針對二元搜尋樹進行程式實作與遍歷。

實作二元搜尋樹

首先建立節點的 class，建構式中除了存放節點的數值 value 外，也可指向左節點與右節點：

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

接著就可以建立主要的 class :

class BinarySearchTree {
    constructor() {
        this.root = null;
    }
    insert(){} //插入
    find(){} //搜尋
    BFS(){} //廣度優先
    DFS(){} //深度優先
}

在建構式中設定了根節點 (初始為 null )，接下來將實作插入( insert )、搜尋 ( find )與樹的遍歷。

插入

插入的程式碼如下：

insert(value){
    let newNode = new Node(value);
    //1.無root情況
    if (this.root === null) {
        this.root = newNode;
        return this;
    }
    //2.有root時,判斷往左還是往右走
    let current = this.root;
    while(true){//3.往左走
        if (value < current.value) {//4.插入左節點並返回
            if (current.left === null) {
                current.left=newNode
                return this;
            }
            current = current.left
        }
        //3.往右走
        else if(value > current.value) {//4.插入右節點並返回
            if (current.right === null) {
                current.right=newNode
                return this;
            }
            current = current.right
        }
        //3.插入重複節點
        else {
            console.log("插入重複節點");
            return false;
        }
    }    
}

首先宣告一個新的節點 newNode，接著判斷資料結構中是否有根節點存在，若無根節點則直接令新節點為根節點即可；已經有根節點時則宣告一個變數 current 存放當前的節點，接著建立一個 while 迴圈並令執行條件為 true 已確保其能找到合適的插入位置；接著判斷往左還是往右查找，若欲插入節點的value 比當前節點的 value 小的時候，則往左查找(反之則往右)，接著令當前的節點 current 為其左邊的節點並繼續進行迴圈；若 current 的左邊節點為 null 時，代表找到插入位置了，則令 current 的左節點為新節點 newNode，即可結束迴圈(return)。往右查找的邏輯也是一樣，需要注意的是若插入重複的節點，會直接結束迴圈。

接著可將 class 實體化並實現剛剛二元搜尋樹的例子：

let tree = new BinarySearchTree();
tree.insert(10);
tree.insert(5);
tree.insert(20);
tree.insert(1);
tree.insert(8);
tree.insert(15);
tree.insert(30);
console.log(tree);

在控制台可看到資料結構與剛才的範例是一致的，接著試著插入一個新的節點 18：

執行 insert 方法後會進入迴圈，此時的 current 為根節點 10 ，18 比 10 還大，因此往右邊節點走，令 current 為 20 後繼續執行迴圈；18 比 20還小，因此往左邊節點走，令 current 為 15 後繼續執行迴圈；18 比 15 還大，因此往右邊節點走，此時發現 15 的右邊並沒有節點( null )，因此我們令 current 的右邊節點為 18 ，並返回整個資料結構。結果如下圖所示：

搜尋

搜尋的程式碼如下所示：

find(value){
    if(this.root === null) return false;//無節點
    let current = this.root;
    let found = false;
    while (current && !found) {//當前還有節點且還沒找到時
        if (value < current.value) {
            current = current.left;
        }else if (value > current.value) {
            current = current.right;
        }else{
            found = true;
        }
    }
    if (!found) {//都沒找到時
        console.log('cant find the value');
        return false;
    }else {//找到時
        return current;
    }
}

首先判斷有無根節點存在，若無根節點說明資料結構中無任何節點，故返回 false；接著一樣令變數 current 為當前的根節點，變數 found 代表是否已經找到要找的節點(初始為 false)，接著使用 while 迴圈，執行的條件為 current 有節點且還未找到要找的節點時執行，迴圈內部則跟插入的程式碼大同小異，需要注意的是當 current 等於要找的 value 時，需要令 found 為 true，執行完迴圈後可從 found 的狀態知道要找的節點是否存在，不存在的話返回 false，存在的話即返回該節點。

樹的遍歷

樹的遍歷即是訪問樹中的所有節點，訪問的方式可簡易分成廣度、深度優先(Depth-First Search、Breadth-first search)，下面將依序做介紹並用之前建立的二元搜尋樹來進行實作。

廣度優先

廣度優先遍歷會先存取離根節點最近的節點，即剛開始會訪問根結點的左右兩邊，之後按層次不斷的往下遍歷：

廣度優先遍歷 ：F, B, G, A, D, I, C, E, H

二元搜尋樹的廣度優先程式碼如下：

BFS(){
    let node = this.root;
    let data = [];//已訪問的節點
    let queue = [];//尚未返問的節點
    queue.push(node);
    while (queue.length) {//佇列queue中還有資料時,取出並塞入data中
        node = queue.shift();//取出
        data.push(node);
        if (node.left) queue.push(node.left);
        if (node.right) queue.push(node.right);
    }
    return data;
}

首先令變數 node 為當前的根結點，接著建立兩個陣列，data 存放已訪問的節點，queue 放入尚未訪問的節點。開始時會先將存放根節點的 node 存入程式中，接著執行 while 迴圈，執行的條件為 queue 中還有節點存在時，則會將 queue 中的首元素取初並推入 data 中(表示已訪問)，接著將 node 的左節點與右節點再分別推入 queue 中即可；當迴圈結束時即可返回 data 。

用剛剛建立的二次元搜尋樹執行廣度優先:

let tree = new BinarySearchTree();
tree.insert(10);
tree.insert(5);
tree.insert(20);
tree.insert(1);
tree.insert(8);
tree.insert(15);
tree.insert(30);

console.log(tree.BFS()); //廣度優先

即可得到結果：

深度優先

深度優先是沿著樹的深度遍歷樹的節點，儘可能深的搜尋樹的分支；當節點所在邊都己被探尋過，搜尋將回溯到發現節點的那條邊的起始節點。深度優先又有 PreOrder、PostOrder，InOrder 三種形式，原則上大同小異，這邊將以 PreOrder 進行講解。深度優先 PreOrder 的程式碼如下：

DFSPreOrder(){
    let data = [];
    function traverse(node) {
        data.push(node);
        if (node.left) traverse(node.left);
        if (node.right) traverse(node.right);
    }
    traverse(this.root)
    return data;
}

這邊使用遞迴來進行實作，首先一樣宣告一陣列 data 存放已訪問過的節點，接著建立遞迴函式 traverse，函式需要傳入一個節點，執行時會將該節點推入 data 中(表示已訪問)，接著判斷該節點是否有左節點/右節點，若有的話則繼續執行 traversetraverse 並代入其左節點/右節點，不斷的執行遞迴並在最後將 data 返回。接著在範例程式中呼叫此方法並顯示結果：

let tree = new BinarySearchTree();
tree.insert(10);
tree.insert(5);
tree.insert(20);
tree.insert(1);
tree.insert(8);
tree.insert(15);
tree.insert(30);

console.log(tree.DFSPreOrder());　//執行深度優先 PreOrder

可觀察出結果為 [10, 5, 1, 8, 20, 15, 30 ]，符合深度優先 PreOrder 的結果。

效能分析

透過觀察法可以得到搜尋與插入方法的時間複雜度為 O(log n)，空間複雜度為 O(1)；而廣度優先及深度優先的時間/空間複雜度為 O(n)( 取決於實作的方式)。

重點複習

1. 樹是一種非線性、且具有階層架構的資料結構。
2. 二元樹中的每個節點最多只能有兩個子節點。
3. 二元搜尋樹為二元樹的一種實作方式，樹中的每個節點皆為不重複的元素，且左側的節點必定小於右側節點。