js數據結構和算法（三）二叉樹

DesGemini 發布于2019-08-21 10:20 / 1280人閱讀

摘要：同樣結點樹的二叉樹，完全二叉樹的深度最小。二叉樹每個結點最多有兩個孩子，所以為它設計一個數據域和兩個指針域是比較自然的想法，我們稱這樣的鏈表叫做二叉鏈表。

二叉樹的概念

二叉樹（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;
}

二叉樹相關題目：http://blog.csdn.net/luckyxiaoqiang/article/details/7518888

云服務器 GPU云服務器二叉樹算法最優二叉樹算法圖 JS二叉樹遍歷 js怎么建二叉樹

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/85346.html

數據結構與算法:二叉樹算法

摘要：因此，根據題目給出的先序遍歷和中序遍歷，可以畫出二叉樹選參考數據結構與算法描述實現二叉樹算法淺談數據結構二叉樹慕課網實現二叉樹算法前端樹控件騰訊軟件開發面試題內容銜接上一章數據結構與算法:常見排序算法內容提要什么是樹　　- 為什么使用樹二叉樹二叉查找樹紅黑樹Ｂ、Ｂ＋樹堆伸展樹樹可以點擊鏈接感受下筆者用d3.js畫的tree https://codepen...

Little_XM 2019-08-22 11:09 評論0 收藏0
JS中的二叉樹遍歷

摘要：一個二叉樹的例子廣度優先遍歷廣度優先遍歷是從二叉樹的第一層根結點開始，自上至下逐層遍歷在同一層中，按照從左到右的順序對結點逐一訪問。有的書里將二叉樹的遍歷只講了上面三種遞歸遍歷。二叉樹是由根節點，左子樹，右子樹組成，左子樹和友子樹分別是一個二叉樹。這篇文章主要在JS中實現二叉樹的遍歷。一個二叉樹的例子 var tree = { value: 1, left: { ...

ghnor 2019-08-19 17:52 評論0 收藏0
JS二叉樹非遞歸遍歷

摘要：一個二叉樹的例子先實現三種遍歷的遞歸算法以作比較。先序遍歷遞歸算法中序遍歷遞歸算法先遍歷到最左邊的節點，然后輸出后序遍歷看完上面的遞歸遍歷，下面對比一下非遞歸的二叉樹遍歷。終止條件最后樹遍歷完了自然就結束后序遍歷二叉樹的遞歸遍歷很簡單就可以實現，二叉樹非遞歸遍歷卻想不出來？那你可以看看下面的例子。一個二叉樹的例子 var root = { val: 1, left: { val...

guyan0319 2019-08-21 16:20 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月匯總（55 題攻略）

摘要：微信公眾號記錄截圖記錄截圖目前關于這塊算法與數據結構的安排前。已攻略返回目錄目前已攻略篇文章。會根據題解以及留言內容，進行補充，并添加上提供題解的小伙伴的昵稱和地址。本許可協議授權之外的使用權限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目錄不...

warmcheng 2019-08-26 10:09 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經到題，所以后面會調整自己，在刷算法與數據結構的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。一目錄不折騰的前端，和咸魚有什么區別...

tain335 2019-08-26 10:28 評論0 收藏0