JavaScript資料結構與演算法之二元樹詳解_基礎知識

二元樹的概念

二元樹（Binary Tree）是n（n>=0）個結點的有限集合，該集合或者為空集（空二叉樹），或者由一個根結點和兩棵互不相交的、分別稱為根結點的左子樹和右子樹的二元樹組成。

二元樹的特徵

每個結點最多有兩棵子樹，所以二元樹中不存在度大於2的結點。二元樹中每一個節點都是一個對象，每個資料節點都有三個指針，分別是指向父母、左孩子和右孩子的指針。每一個節點都是透過指標相互連接的。相連指針的關係都是父子關係。

二元樹節點的定義

二元樹節點定義如下：

複製程式碼 程式碼如下:

struct BinaryTreeNode
{
    int m_nValue;
    BinaryTreeNode* m_pLeft;
    BinaryTreeNode* m_pRight;
};

二元樹的五種基本形態

空二元樹
只有一個根結點
根結點只有左子樹
根結點只有右子樹
根結點既有左子樹又有右子樹

擁有三個結點的普通樹只有兩種情況：兩層或三層。但由於二元樹要區分左右，所以就會演變成如下的五種形態：

特殊二元樹

斜樹

如上面倒數第一副圖的第2、3小圖所示。

滿二元樹

在一棵二元樹中，如果所有分支結點都存在左子樹和右子樹，並且所有葉子都在同一層上，這樣的二元樹稱為滿二叉樹。如下圖：

完全二元樹

完全二元樹是指最後一層左邊是滿的，右邊可能滿也可能不滿，然後其餘層都是滿的。一個深度為k，節點個數為 2^k - 1 的二元樹為滿二元樹（完全二元樹）。就是一棵樹，深度為k，沒有空位。

完全二元樹的特徵有：

葉子結點只能出現在最下兩層。

最下層的葉子一定集中在左部連續位置。

倒數第二層，若有葉子結點，一定都在右邊連續位置。

如果結點度為1，則該結點只有左孩子。

同樣結點樹的二元樹，完全二元樹的深度最小。

注意：滿叉樹一定是完全二元樹，但完全二元樹不一定是滿二元樹。

演算法如下：

複製程式碼 程式碼如下:

bool is_complete(tree *root) 
{ 
    queue q; 
    tree *ptr; 
    // 進行廣度優先遍歷（層次遍歷），並將NULL節點也放入佇列 
    q.push(root); 
    while ((ptr = q.pop()) != NULL) 
    { 
        q.push(ptr->left); 
        q.push(ptr->right); 
    } 

    // 判斷是否仍有未被存取的節點 
    while (!q.is_empty()) 
    { 
        ptr = q.pop(); 

        // 有未存取的非NULL節點，則樹存在空洞，為非完全二叉樹 
        if (NULL != ptr) 
        { 
            return false; 
        } 
    } 

    return true; 
} 

二元樹的性質

二元樹的性質一：在二元樹的第i層上至多有2^(i-1)個結點(i>=1)

二元樹的性質二：深度為k的二元樹至多有2^k-1個結點(k>=1)

二元樹的順序儲存結構

二元樹的順序儲存結構就是用一維數組儲存二元樹中的各個結點，而結點的儲存位置能體現結點之間的邏輯關係。

二元鍊錶

既然順序儲存方式的適用性不強，那我們就要考慮鍊式儲存結構啦。二元樹的儲存按照國際慣例來說一般也是採用鍊式儲存結構的。

二元樹每個結點最多有兩個孩子，所以為它設計一個資料域和兩個指標域是比較自然的想法，我們稱這樣的鍊錶叫做二元鍊錶。

二元樹的遍歷

二元樹的遍歷(traversing binary tree)是指從根結點出發，按照某種次序依次訪問二叉樹中所有結點，使得每個結點被訪問一次且僅被訪問一次。

二元樹的遍歷有三種方式，如下：

（1）前序遍歷（DLR），先造訪根結點，再遍歷左子樹，最後遍歷右子樹。簡記根-左-右。

（2）中序遍歷（LDR），先遍歷左子樹，然後訪問根結點，最後遍歷右子樹。簡記左-根-右。

（3）後序遍歷（LRD），先遍歷左子樹，再遍歷右子樹，最後造訪根結點。簡記左-右-根。

前序遍歷：

若二元樹為空，則空操作返回，否則先訪問根結點，然後前序遍歷左子樹，再前序遍歷右子樹。

遍歷的順序為：A B D H I E J C F K G

複製程式碼 程式碼如下:

//先序遍歷
function preOrder(node){
    if(!node == null){
        putstr(node.show() " ");
        preOrder(node.left);
        preOrder(node.right);
    }
}

中序遍歷：

若樹為空，則空操作返回，否則從根結點開始（注意並不是先訪問根結點），中序遍歷根結點的左子樹，然後是訪問根結點，最後中序遍歷右子樹。

遍歷的順序為：H D I B E J A F K C G

複製程式碼 程式碼如下:

//使用遞歸方式實作中序遍歷
function inOrder(node){
    if(!(node == null)){
        inOrder(node.left);//先造訪左子樹
        putstr(node.show() " ");//再存取根節點
        inOrder(node.right);//最後造訪右子樹
    }
}

後序遍歷：

若樹為空，則空操作返回，否則從左到右先葉子後結點的方式遍歷訪問左右子樹，最後訪問根結點。

遍歷的順序為：H I D J E B K F G C A

複製程式碼 程式碼如下:

//後序遍歷
function postOrder(node){
    if(!node == null){
        postOrder(node.left);
        postOrder(node.right);
        putStr(node.show() " ");
    }
}

實作二元查找樹

二元查找樹（BST）由節點組成，所以我們定義一個Node節點物件如下：

複製程式碼 程式碼如下:

function Node(data,left,right){
    this.data = data;
    this.left = left;//儲存left節點連結
    this.right = right;
    this.show = show;
}

function show(){
    return this.data;//顯示保存在節點中的資料
}

找出最大值和最小值

找出BST上的最小值和最大值非常簡單，因為較小的值總是在左子節點上，在BST上尋找最小值，只需遍歷左子樹，直到找到最後一個節點

找最小值

複製程式碼 程式碼如下:

function getMin(){
    var current = this.root;
    while(!(current.left == null)){
        current = current.left;
    }
    return current.data;
}

此方法沿著BST的左子樹挨個遍歷，直到遍歷到BST最左的節點，該節點被定義為：

複製程式碼 程式碼如下:

current.left = null;

這時，目前節點上保存的值就是最小值

找最大值

在BST上找出最大值只需要遍歷右子樹，直到找到最後一個節點，該節點上儲存的值就是最大值。

複製程式碼 程式碼如下:

function getMax(){
    var current = this.root;
    while(!(current.right == null)){
        current = current.right;
    }
    return current.data;
}