DIV CSS 佈局教程網

JavaScript資料結構與演算法入門:二叉樹完全解析
編輯:關於JavaScript     

一、什麼是二叉樹

二叉樹(Binary Tree)本質上是一種受限的樹形結構:它由 n(n ≥ 0)個結點組成,當 n 等於 0 時是一棵空樹;否則它由一個根結點,以及分別挂在根結點下的左子樹與右子樹構成,而這兩棵子樹本身也必須是二叉樹。這個定義是遞歸的,理解這一點,後面所有遍歷與操作都會變得自然。

二、二叉樹的特點

二叉樹最直觀的約束是:每個結點最多只能有兩棵子樹,也就是說整棵樹中不存在度大於 2 的結點。左右子樹的位置是有順序的,不能隨意調換,這是二叉樹和普通樹最大的差別。

在程式實現層面,每一個結點通常被建模為一個物件,並持有三個引用:一個指向父結點,另外兩個分別指向左孩子與右孩子。結點之間靠這些引用互相串聯,凡是彼此相連的兩個結點,都構成父子關係。

三、結點結構的定義

以 C 語言風格描述,一個二叉樹結點可以這樣定義:

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

其中 m_nValue 存放數據,m_pLeft 與 m_pRight 分別保存左右孩子的位址。若改用 JavaScript 實現,把指標換成物件引用即可。

四、二叉樹的五種基本形態

二叉樹在形態上可以歸納為五種:空樹;只有一個根結點;根結點只有左子樹;根結點只有右子樹;根結點同時擁有左右子樹。

如果只考慮「有幾層」,含三個結點的普通樹不過兩三種擺法;但二叉樹要嚴格區分左右,同樣三個結點就會衍生出五種形態。

五、幾種特殊的二叉樹

斜樹

如上圖倒數第二張圖中的第 2、3 小圖所示,所有結點都只有單側孩子,整棵樹「歪」向一邊,退化成了類似鏈表的結構。

滿二叉樹

如果一棵二叉樹的每個分支結點都同時具備左子樹和右子樹,並且所有葉子結點都集中在同一層上,這樣的樹稱為滿二叉樹。此時深度為 k 的滿二叉樹恰好擁有 2 的 k 次方減 1 個結點,一個位置都不浪費。

完全二叉樹

完全二叉樹的要求比滿二叉樹寬鬆:除最後一層外,其餘各層必須排滿,而最後一層的結點則從左到右連續排列,右側允許留有空位。也就是說,深度為 k 的完全二叉樹,結點數介於 2 的 k-1 次方與 2 的 k 次方減 1 之間。

它有幾個容易驗證的性質:

葉子結點只可能出現在最後一層和倒數第二层;最後一層的葉子一定集中在左部的連續位置;倒數第二层若存在葉子結點,則必定集中在右部的連續位置;若某結點的度為 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 之後還出現非 NULL 節點,說明樹中存在空洞,不是完全二叉樹
        if (NULL != ptr)
        {
             return false;
        }
    }
    return true;
}

思路很直白:把空節點也一起入列,如果一個空節點後面還跟著非空節點,說明中間斷了層,自然不是完全二叉樹。

六、二叉樹的兩個基本性質

性質一:第 i 層上至多有 2 的 (i-1) 次方個結點(i ≥ 1)。

性質二:深度為 k 的二叉樹至多有 2 的 k 次方減 1 個結點(k ≥ 1)。

此外還有一條常用結論:若用 n0 表示葉子結點數、n2 表示度為 2 的結點數,則恆有 n0 = n2 + 1。

七、順序存儲結構

順序存儲就是用一維陣列把二叉樹的結點依次擺放,並靠下標的計算關係來表達父子之間的邏輯聯繫。對於完全二叉樹,這種方式非常緊湊;但一旦樹中出現大量空洞,陣列就會浪費大量空間,適用性明顯下降。

八、二叉鏈表

既然順序結構不夠靈活,工程實踐中更常採用鏈式存儲。二叉樹每個結點最多兩個孩子,因此為它設計一個數據域加兩個指標域是最自然的方案,這樣得到的鏈表稱為二叉鏈表。

九、二叉樹的遍歷

遍歷(Traversing Binary Tree)指的是從根結點出發,按照某種約定的次序訪問樹中每一個結點,且每個結點僅被訪問一次。二叉樹有三種基本遍歷方式:

前序遍歷(DLR):先訪問根結點,再遍歷左子樹,最後遍歷右子樹,簡記為「根—左—右」。

中序遍歷(LDR):先遍歷左子樹,再訪問根結點,最後遍歷右子樹,簡記為「左—根—右」。

後序遍歷(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)

二叉查找樹是一種有附加約束的二叉樹:對任意結點而言,其左子樹上所有結點的值都小於它,右子樹上所有結點的值都大於它。正因這種有序性,查找、插入、求極值等操作都能沿著單一分支快速逼近目標。

先定義結點結構:

function Node(data, left, right){
    this.data = data;
    this.left = left; //保存左子節點鏈接
    this.right = right;
    this.show = show;
}

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

查找最小值與最大值

由於左子樹恆小於當前結點、右子樹恆大於當前結點,求最小值的過程就是一路向左走到不能再走;求最大值則一路向右。

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

當某個結點滿足 current.left == null 時,它就是整棵樹最左端的結點,其 data 即為最小值。

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

同理,最右端結點上保存的值就是最大值。這兩個操作的時間複雜度取決於樹高,在理想情況下為 O(log n),若樹退化為斜樹則退化為 O(n)。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved