成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

js數(shù)據(jù)結(jié)構(gòu)和算法（三）二叉樹

DesGemini / 1304人閱讀

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

二叉樹的概念

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

二叉樹的特點

每個結(jié)點最多有兩棵子樹，所以二叉樹中不存在度大于2的結(jié)點。二叉樹中每一個節(jié)點都是一個對象，每一個數(shù)據(jù)節(jié)點都有三個指針，分別是指向父母、左孩子和右孩子的指針。每一個節(jié)點都是通過指針相互連接的。相連指針的關(guān)系都是父子關(guān)系。

二叉樹節(jié)點的定義

二叉樹節(jié)點定義如下：

struct BinaryTreeNode
{
    int m_nValue;
    BinaryTreeNode* m_pLeft;
    BinaryTreeNode* m_pRight;
};
二叉樹的五種基本形態(tài) 
空二叉樹
只有一個根結(jié)點
根結(jié)點只有左子樹
根結(jié)點只有右子樹
根結(jié)點既有左子樹又有右子樹

擁有三個結(jié)點的普通樹只有兩種情況：兩層或者三層。但由于二叉樹要區(qū)分左右，所以就會演變成如下的五種形態(tài)：

特殊二叉樹 斜樹

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

滿二叉樹

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

完全二叉樹

完全二叉樹是指最后一層左邊是滿的，右邊可能滿也可能不滿，然后其余層都是滿的。一個深度為k，節(jié)點個數(shù)為 2^k - 1 的二叉樹為滿二叉樹（完全二叉樹）。就是一棵樹，深度為k，并且沒有空位。

完全二叉樹的特點有：

葉子結(jié)點只能出現(xiàn)在最下兩層。

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

倒數(shù)第二層，若有葉子結(jié)點，一定都在右部連續(xù)位置。

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

同樣結(jié)點樹的二叉樹，完全二叉樹的深度最小。

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

算法如下：

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

    // 判斷是否還有未被訪問到的節(jié)點  
    while (!q.is_empty())  
    {  
        ptr = q.pop();  

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

    return true;  
}
二叉樹的性質(zhì)

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

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

二叉樹的順序存儲結(jié)構(gòu)

二叉樹的順序存儲結(jié)構(gòu)就是用一維數(shù)組存儲二叉樹中的各個結(jié)點，并且結(jié)點的存儲位置能體現(xiàn)結(jié)點之間的邏輯關(guān)系。

二叉鏈表

既然順序存儲方式的適用性不強，那么我們就要考慮鏈式存儲結(jié)構(gòu)啦。二叉樹的存儲按照國際慣例來說一般也是采用鏈式存儲結(jié)構(gòu)的。

二叉樹每個結(jié)點最多有兩個孩子，所以為它設(shè)計一個數(shù)據(jù)域和兩個指針域是比較自然的想法，我們稱這樣的鏈表叫做二叉鏈表。

二叉樹的遍歷

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

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

（1）前序遍歷（DLR），首先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹。簡記根-左-右。

（2）中序遍歷（LDR），首先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹。簡記左-根-右。

（3）后序遍歷（LRD），首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點。簡記左-右-根。
前序遍歷：

若二叉樹為空，則空操作返回，否則先訪問根結(jié)點，然后前序遍歷左子樹，再前序遍歷右子樹。


遍歷的順序為：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);
    }
}
中序遍歷：

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


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

//使用遞歸方式實現(xiàn)中序遍歷
function inOrder(node){
    if(!(node == null)){
        inOrder(node.left);//先訪問左子樹
        putstr(node.show()+ " ");//再訪問根節(jié)點
        inOrder(node.right);//最后訪問右子樹
    }
}
后序遍歷：

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

遍歷的順序為：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()+ " ");
    }
}
實現(xiàn)二叉查找樹

二叉查找樹（BST）由節(jié)點組成，所以我們定義一個Node節(jié)點對象如下：

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


function show(){
    return this.data;//顯示保存在節(jié)點中的數(shù)據(jù)
}
查找最大和最小值

查找BST上的最小值和最大值非常簡單，因為較小的值總是在左子節(jié)點上，在BST上查找最小值，只需遍歷左子樹，直到找到最后一個節(jié)點

查找最小值 
function getMin(){
    var current = this.root;
    while(!(current.left == null)){
        current = current.left;
    }
    return current.data;
}

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

current.left = null;

這時，當前節(jié)點上保存的值就是最小值

查找最大值

在BST上查找最大值只需要遍歷右子樹，直到找到最后一個節(jié)點，該節(jié)點上保存的值就是最大值。

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

二叉樹相關(guān)題目：http://blog.csdn.net/luckyxiaoqiang/article/details/7518888

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/85346.html

相關(guān)文章

  • 數(shù)據(jù)結(jié)構(gòu)與算法:二叉樹算法

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

    Little_XM 評論0 收藏0

  • JS中的二叉樹遍歷

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

    ghnor 評論0 收藏0

  • JS二叉樹非遞歸遍歷

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

    guyan0319 評論0 收藏0

  • LeetCode 攻略 - 2019 年 7 月上半月匯總（55 題攻略）

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

    warmcheng 評論0 收藏0

  • LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

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

    tain335 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<