欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

JavaScript數(shù)據(jù)結(jié)構(gòu)和算法之二叉樹詳解

 更新時(shí)間:2015年02月11日 10:28:08   投稿:junjie  
這篇文章主要介紹了JavaScript數(shù)據(jù)結(jié)構(gòu)和算法之二叉樹詳解,本文講解了二叉樹的概念、二叉樹的特點(diǎn)、二叉樹節(jié)點(diǎn)的定義、查找最大和最小值等內(nèi)容,需要的朋友可以參考下

二叉樹的概念

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

二叉樹的特點(diǎn)

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

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

二叉樹節(jié)點(diǎn)定義如下:

復(fù)制代碼 代碼如下:

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

二叉樹的五種基本形態(tài)

空二叉樹
只有一個(gè)根結(jié)點(diǎn)
根結(jié)點(diǎn)只有左子樹
根結(jié)點(diǎn)只有右子樹
根結(jié)點(diǎn)既有左子樹又有右子樹

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

特殊二叉樹

斜樹

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

滿二叉樹

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

完全二叉樹

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

完全二叉樹的特點(diǎn)有:

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

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

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

如果結(jié)點(diǎn)度為1,則該結(jié)點(diǎn)只有左孩子。

同樣結(jié)點(diǎn)樹的二叉樹,完全二叉樹的深度最小。

注意:滿二叉樹一定是完全二叉樹,但完全二叉樹不一定是滿二叉樹。

算法如下:

復(fù)制代碼 代碼如下:

bool is_complete(tree *root) 

    queue q; 
    tree *ptr; 
    // 進(jìn)行廣度優(yōu)先遍歷(層次遍歷),并把NULL節(jié)點(diǎn)也放入隊(duì)列 
    q.push(root); 
    while ((ptr = q.pop()) != NULL) 
    { 
        q.push(ptr->left); 
        q.push(ptr->right); 
    } 

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

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

    return true; 

二叉樹的性質(zhì)

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

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

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

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

二叉鏈表

既然順序存儲(chǔ)方式的適用性不強(qiáng),那么我們就要考慮鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)啦。二叉樹的存儲(chǔ)按照國(guó)際慣例來(lái)說(shuō)一般也是采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的。

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

二叉樹的遍歷

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

二叉樹的遍歷有三種方式,如下:

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

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

(3)后序遍歷(LRD),首先遍歷左子樹,然后遍歷右子樹,最后訪問根結(jié)點(diǎn)。簡(jiǎn)記左-右-根。

前序遍歷:

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

遍歷的順序?yàn)椋篈 B D H I E J C F K G

復(fù)制代碼 代碼如下:

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

中序遍歷:

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

遍歷的順序?yàn)椋篐 D I B E J A F K C G

復(fù)制代碼 代碼如下:

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

后序遍歷:

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

遍歷的順序?yàn)椋篐 I D J E B K F G C A

復(fù)制代碼 代碼如下:

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

實(shí)現(xiàn)二叉查找樹

二叉查找樹(BST)由節(jié)點(diǎn)組成,所以我們定義一個(gè)Node節(jié)點(diǎn)對(duì)象如下:

復(fù)制代碼 代碼如下:

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


function show(){
    return this.data;//顯示保存在節(jié)點(diǎn)中的數(shù)據(jù)
}

查找最大和最小值

查找BST上的最小值和最大值非常簡(jiǎn)單,因?yàn)檩^小的值總是在左子節(jié)點(diǎn)上,在BST上查找最小值,只需遍歷左子樹,直到找到最后一個(gè)節(jié)點(diǎn)

查找最小值

復(fù)制代碼 代碼如下:

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

該方法沿著BST的左子樹挨個(gè)遍歷,直到遍歷到BST最左的節(jié)點(diǎn),該節(jié)點(diǎn)被定義為:
復(fù)制代碼 代碼如下:

current.left = null;

這時(shí),當(dāng)前節(jié)點(diǎn)上保存的值就是最小值

查找最大值

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

復(fù)制代碼 代碼如下:

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

相關(guān)文章

  • 淺談JavaScript數(shù)據(jù)類型及轉(zhuǎn)換

    淺談JavaScript數(shù)據(jù)類型及轉(zhuǎn)換

    本文向大家簡(jiǎn)單介紹了javascript的數(shù)據(jù)類型以及他們直接的轉(zhuǎn)換方法,雖然沒有太多示例,但是也是個(gè)人的一些經(jīng)驗(yàn)總結(jié),這里推薦給大家。
    2015-02-02
  • 微信小程序訪問node.js接口服務(wù)器搭建教程

    微信小程序訪問node.js接口服務(wù)器搭建教程

    這篇文章主要給大家分享了微信小程序訪問node.js接口服務(wù)器的搭建教程,文中介紹的非常詳細(xì),對(duì)大家具有一定的參考價(jià)值,需要的朋友們下面來(lái)跟著小編一起看看吧。
    2017-04-04
  • 薦書|您有一份JavaScript書單待簽收

    薦書|您有一份JavaScript書單待簽收

    ​學(xué)習(xí)是一個(gè)持續(xù)不斷的過程,在互聯(lián)網(wǎng)技術(shù)里暢游的程序員們,對(duì)學(xué)習(xí)的渴望更是難以窮盡,下面這篇文章主要給大家分享了關(guān)于Javascript相關(guān)的書籍,對(duì)大家學(xué)習(xí)Javascript具有一定的參考學(xué)習(xí)價(jià)值,下面來(lái)一起看看吧。
    2017-07-07
  • document.styleSheets[0].disabled

    document.styleSheets[0].disabled

    document.styleSheets[0].disabled...
    2006-10-10
  • JavaScript 學(xué)習(xí)筆記之語(yǔ)句

    JavaScript 學(xué)習(xí)筆記之語(yǔ)句

    這篇文章主要介紹了JavaScript中的語(yǔ)句,包括條件分支語(yǔ)句、循環(huán)語(yǔ)句、迭代語(yǔ)句、Lable語(yǔ)句、break和continue語(yǔ)句、with語(yǔ)句、swith語(yǔ)句,十分全面細(xì)致,推薦給小伙伴們。
    2015-01-01
  • javascript的BOM

    javascript的BOM

    BOM是瀏覽器的窗口對(duì)象,提供了很多窗口處理的API。在webapp框架越來(lái)越多的情況下,需要我們?cè)谕淮翱谔幚聿煌?yè)面、不同的ajax數(shù)據(jù),則需要我們熟悉BOM的內(nèi)容。
    2016-05-05
  • JavaScript之?dāng)?shù)組扁平化詳解

    JavaScript之?dāng)?shù)組扁平化詳解

    這篇文章主要介紹了JavaScript之?dāng)?shù)組扁平化詳解的方法,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,,需要的朋友可以參考下
    2019-06-06
  • JS div勻速移動(dòng)動(dòng)畫與變速移動(dòng)動(dòng)畫代碼實(shí)例

    JS div勻速移動(dòng)動(dòng)畫與變速移動(dòng)動(dòng)畫代碼實(shí)例

    這篇文章主要介紹了JS div勻速移動(dòng)動(dòng)畫與變速移動(dòng)動(dòng)畫,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
    2019-03-03
  • 使用按鈕控制以何種方式打開新窗口的屬性介紹

    使用按鈕控制以何種方式打開新窗口的屬性介紹

    在用戶體驗(yàn)過程中可能會(huì)出現(xiàn)這樣的情況:自定義打開新窗口的樣式,本文將介紹詳細(xì)的解決方法,需要了解的朋友可以參考下
    2012-12-12
  • javascript cookie用法基礎(chǔ)教程(概念,設(shè)置,讀取及刪除)

    javascript cookie用法基礎(chǔ)教程(概念,設(shè)置,讀取及刪除)

    這篇文章主要介紹了javascript cookie用法,結(jié)合實(shí)例形式總結(jié)分析了javascript中cookie的定義、特點(diǎn)及獲取、設(shè)置、刪除等基本操作技巧,需要的朋友可以參考下
    2016-09-09

最新評(píng)論