二叉樹那些事兒

Little_XM 發(fā)布于2019-08-22 16:28 / 3197人閱讀

摘要：大家在聊到二叉樹的時(shí)候，總會(huì)離不開鏈表。受限線性表主要包括棧和隊(duì)列，受限表示對(duì)結(jié)點(diǎn)的操作受限制。存儲(chǔ)結(jié)構(gòu)線性表主要由順序表示或鏈?zhǔn)奖硎?。鏈?zhǔn)奖硎局傅氖怯靡唤M任意的存儲(chǔ)單元存儲(chǔ)線性表中的數(shù)據(jù)元素，稱為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

大家在聊到二叉樹的時(shí)候，總會(huì)離不開鏈表。這里先帶大家一起了解一些基本概念。

線性表 概念

線性表是最基本、最簡(jiǎn)單、也是最常用的一種數(shù)據(jù)結(jié)構(gòu)。

線性表中數(shù)據(jù)元素之間的關(guān)系是一對(duì)一的關(guān)系，即除了第一個(gè)和最后一個(gè)數(shù)據(jù)元素之外，其它數(shù)據(jù)元素都是首尾相接的（注意，這句話只適用大部分線性表，而不是全部。比如，循環(huán)鏈表邏輯層次上也是一種線性表（存儲(chǔ)層次上屬于鏈?zhǔn)酱鎯?chǔ)），但是把最后一個(gè)數(shù)據(jù)元素的尾指針指向了首位結(jié)點(diǎn)）。

我們說“線性”和“非線性”，只在邏輯層次上討論，而不考慮存儲(chǔ)層次，所以雙向鏈表和循環(huán)鏈表依舊是線性表。在數(shù)據(jù)結(jié)構(gòu)邏輯層次上細(xì)分，線性表可分為一般線性表和受限線性表。一般線性表也就是我們通常所說的“線性表”，可以自由的刪除或添加結(jié)點(diǎn)。受限線性表主要包括棧和隊(duì)列，受限表示對(duì)結(jié)點(diǎn)的操作受限制。

特征

1．集合中必存在唯一的一個(gè)“第一元素”。
2．集合中必存在唯一的一個(gè) “最后元素” 。
3．除最后一個(gè)元素之外，均有唯一的后繼(后件)。
4．除第一個(gè)元素之外，均有唯一的前驅(qū)(前件)。

存儲(chǔ)結(jié)構(gòu)

線性表主要由順序表示或鏈?zhǔn)奖硎?。在?shí)際應(yīng)用中，常以棧、隊(duì)列、字符串等特殊形式使用。

順序表示指的是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素，稱為線性表的順序存儲(chǔ)結(jié)構(gòu)或順序映像。它以“物理位置相鄰”來表示線性表中數(shù)據(jù)元素間的邏輯關(guān)系，可隨機(jī)存取表中任一元素。

鏈?zhǔn)奖硎局傅氖怯靡唤M任意的存儲(chǔ)單元存儲(chǔ)線性表中的數(shù)據(jù)元素，稱為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。它的存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的。在表示數(shù)據(jù)元素之間的邏輯關(guān)系時(shí)，除了存儲(chǔ)其本身的信息之外，還需存儲(chǔ)一個(gè)指示其直接后繼的信息（即直接后繼的存儲(chǔ)位置），這兩部分信息組成數(shù)據(jù)元素的存儲(chǔ)映像，稱為結(jié)點(diǎn)（node）。它包括兩個(gè)域；存儲(chǔ)數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域；存儲(chǔ)直接后繼存儲(chǔ)位置的域稱為指針域。指針域中存儲(chǔ)的信息稱為指針或鏈

鏈表

鏈表是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點(diǎn)（鏈表中每一個(gè)元素稱為結(jié)點(diǎn)）組成，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成。

每個(gè)結(jié)點(diǎn)包括兩個(gè)部分：

存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域

存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址的指針域。

鏈表不必須按順序存儲(chǔ)，鏈表在插入的時(shí)候可以達(dá)到O(1)的時(shí)間復(fù)雜度，比另一種線性表順序表快得多，但是查找一個(gè)節(jié)點(diǎn)或者訪問特定編號(hào)的節(jié)點(diǎn)則需要O(n)的時(shí)間，而線性表和順序表相應(yīng)的時(shí)間復(fù)雜度分別是O(logn)和O(1)。
鏈表結(jié)點(diǎn)聲明如下：

class ListNode
{
    let nodeValue; //數(shù)據(jù)
    let next; //指向下一個(gè)節(jié)點(diǎn)的指針

};

從內(nèi)存角度出發(fā)：鏈表可分為靜態(tài)鏈表、動(dòng)態(tài)鏈表。
從鏈表存儲(chǔ)方式的角度出發(fā)：鏈表可分為單向鏈表、雙向鏈表、以及循環(huán)鏈表。

靜態(tài)鏈表

把線性表的元素存放在數(shù)組中，這些元素可能在物理上是連續(xù)存放的，也有可能不是連續(xù)的，它們之間通過邏輯關(guān)系來連接，數(shù)組單位存放鏈表結(jié)點(diǎn)，結(jié)點(diǎn)的鏈域指向下一個(gè)元素的位置，即下一個(gè)元素所在的數(shù)組單元的下標(biāo)。顯然靜態(tài)鏈表需要數(shù)組來實(shí)現(xiàn)。
引出的問題：數(shù)組的長(zhǎng)度定義的問題，無法預(yù)支。

動(dòng)態(tài)鏈表（實(shí)際當(dāng)中用的最多）

改善了靜態(tài)鏈表的缺點(diǎn)。它動(dòng)態(tài)的為節(jié)點(diǎn)分配存儲(chǔ)單元。當(dāng)有節(jié)點(diǎn)插入時(shí)，系統(tǒng)動(dòng)態(tài)的為結(jié)點(diǎn)分配空間。在結(jié)點(diǎn)刪除時(shí)，應(yīng)該及時(shí)釋放相應(yīng)的存儲(chǔ)單元，以防止內(nèi)存泄露。

單鏈表

單鏈表是一種順序存儲(chǔ)的結(jié)構(gòu)。有一個(gè)頭結(jié)點(diǎn)，沒有值域，只有連域，專門存放第一個(gè)結(jié)點(diǎn)的地址。有一個(gè)尾結(jié)點(diǎn)，有值域，也有鏈域，鏈域值始終為NULL。所以，在單鏈表中為找第i個(gè)結(jié)點(diǎn)或數(shù)據(jù)元素，必須先找到第i - 1 結(jié)點(diǎn)或數(shù)據(jù)元素，而且必須知道頭結(jié)點(diǎn)，否者整個(gè)鏈表無法訪問。

循環(huán)鏈表

循環(huán)鏈表，類似于單鏈表，也是一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，循環(huán)鏈表由單鏈表演化過來。單鏈表的最后一個(gè)結(jié)點(diǎn)的鏈域指向NULL，而循環(huán)鏈表的建立，不要專門的頭結(jié)點(diǎn)，讓最后一個(gè)結(jié)點(diǎn)的鏈域指向鏈表結(jié)點(diǎn)。

循環(huán)鏈表與單鏈表的區(qū)別

鏈表的建立。單鏈表需要?jiǎng)?chuàng)建一個(gè)頭結(jié)點(diǎn)，專門存放第一個(gè)結(jié)點(diǎn)的地址。單鏈表的鏈域指向NULL。而循環(huán)鏈表的建立，不要專門的頭結(jié)點(diǎn)，讓最后一個(gè)結(jié)點(diǎn)的鏈域指向鏈表的頭結(jié)點(diǎn)。

鏈表表尾的判斷。單鏈表判斷結(jié)點(diǎn)是否為表尾結(jié)點(diǎn)，只需判斷結(jié)點(diǎn)的鏈域值是否是NULL。如果是，則為尾結(jié)點(diǎn)；否則不是。而循環(huán)鏈表盤判斷是否為尾結(jié)點(diǎn)，則是判斷該節(jié)點(diǎn)的鏈域是不是指向鏈表的頭結(jié)點(diǎn)。

雙鏈表

雙鏈表也是基于單鏈表的，單鏈表是單向的，有一個(gè)頭結(jié)點(diǎn)，一個(gè)尾結(jié)點(diǎn)，要訪問任何結(jié)點(diǎn)，都必須知道頭結(jié)點(diǎn)，不能逆著進(jìn)行。而雙鏈表則是添加了一個(gè)鏈域。通過兩個(gè)鏈域，分別指向結(jié)點(diǎn)的前結(jié)點(diǎn)和后結(jié)點(diǎn)。這樣的話，可以通過雙鏈表的任何結(jié)點(diǎn)，訪問到它的前結(jié)點(diǎn)和后結(jié)點(diǎn)。但是雙鏈表還是不夠靈活，在實(shí)際編程中比較常用的是循環(huán)雙鏈表。但循環(huán)雙鏈表使用較為麻煩。

鏈表相關(guān)題目

求單鏈表中結(jié)點(diǎn)的個(gè)數(shù)
這是最最基本的了，應(yīng)該能夠迅速寫出正確的代碼，注意檢查鏈表是否為空。時(shí)間復(fù)雜度為O（n）。參考代碼如下：

function GetListLength(head)  
{  
    if(head === NULL) return 0;  
    let len = 0;  
    let current = head;  // ListNode
    while(current !== NULL)  
    {  
        len++;  
        current = current.next;  
    }  
    return len;  
}

將單鏈表反轉(zhuǎn)
從頭到尾遍歷原鏈表，每遍歷一個(gè)結(jié)點(diǎn)，將其摘下放在新鏈表的最前端。注意鏈表為空和只有一個(gè)結(jié)點(diǎn)的情況。時(shí)間復(fù)雜度為O（n）。參考代碼如下

// 反轉(zhuǎn)單鏈表  
function ReverseList(ListNode head)  
{  
    // 如果鏈表為空或只有一個(gè)結(jié)點(diǎn)，無需反轉(zhuǎn)，直接返回原鏈表頭指針  
    if(head === NULL || head.next === NULL) return head;  
    let prev = NULL; // ListNode 反轉(zhuǎn)后的新鏈表頭指針，初始為NULL  
    let current = head;  
    while(current !== NULL)  
    {  
        let temp = current;  //獲取當(dāng)前節(jié)點(diǎn)ListNode
        current = current.next;  //獲取下一個(gè)節(jié)點(diǎn)
        temp.next = prev; // 將當(dāng)前結(jié)點(diǎn)摘下，插入新鏈表的最前端  
        prev = temp;  //上一個(gè)節(jié)點(diǎn)前進(jìn)一位
    }  
    return prev;  
}

已知兩個(gè)單鏈表pHead1 和pHead2 各自有序，把它們合并成一個(gè)鏈表依然有序
這個(gè)類似歸并排序。尤其注意兩個(gè)鏈表都為空，和其中一個(gè)為空時(shí)的情況。只需要O（1）的空間。時(shí)間復(fù)雜度為O（max(len1, len2)）。參考代碼如下：

// 合并兩個(gè)有序鏈表  
function MergeSortedList(head1, head2)
{  
    if(head1 == NULL) return head2;  
    if(head2 == NULL) return head1;  
    let headMerged = NULL;  
    if(head1.nodeValue < head2.nodeValue)  
    {  
        headMerged = head1;  
        headMerged.next = MergeSortedList(head1.next, head2);  
    }  
    else  
    {  
        headMerged = head2;  
        headMerged.next = MergeSortedList(head1, head2.next);  
    }  
    return headMerged;  
}

判斷一個(gè)單鏈表中是否有環(huán)
這里也是用到兩個(gè)指針。如果一個(gè)鏈表中有環(huán)，也就是說用一個(gè)指針去遍歷，是永遠(yuǎn)走不到頭的。因此，我們可以用兩個(gè)指針去遍歷，一個(gè)指針一次走兩步，一個(gè)指針一次走一步，如果有環(huán)，兩個(gè)指針肯定會(huì)在環(huán)中相遇。時(shí)間復(fù)雜度為O（n）。參考代碼如下：

function HasCircle(head)  
{  
    let pFast = head; // 快指針每次前進(jìn)兩步  
    let pSlow = head; // 慢指針每次前進(jìn)一步  
    while(pFast != NULL && pFast.next != NULL)  
    {  
        pFast = pFast.next.next;  
        pSlow = pSlow.next;  
        if(pSlow == pFast) // 相遇，存在環(huán)  
            return true;  
    }  
    return false;  
}

判斷兩個(gè)單鏈表是否相交
如果兩個(gè)鏈表相交于某一節(jié)點(diǎn)，那么在這個(gè)相交節(jié)點(diǎn)之后的所有節(jié)點(diǎn)都是兩個(gè)鏈表所共有的。也就是說，如果兩個(gè)鏈表相交，那么最后一個(gè)節(jié)點(diǎn)肯定是共有的。
先遍歷第一個(gè)鏈表，記住最后一個(gè)節(jié)點(diǎn)，然后遍歷第二個(gè)鏈表，到最后一個(gè)節(jié)點(diǎn)時(shí)和第一個(gè)鏈表的最后一個(gè)節(jié)點(diǎn)做比較，如果相同，則相交，否則不相交。時(shí)間復(fù)雜度為O(len1+len2)，因?yàn)橹恍枰粋€(gè)額外指針保存最后一個(gè)節(jié)點(diǎn)地址，空間復(fù)雜度為O(1)。參考代碼如下：

function IsIntersected(head1, head2)  
{  
    if(pHead1 == NULL || pHead2 == NULL) return false;  
    let pTail1 = head1;  // 用來存儲(chǔ)第一個(gè)鏈表的最后一個(gè)節(jié)點(diǎn)
    while(pTail1.next != NULL) { 
        pTail1 = pTail1.next; 
    } 
  
    let pTail2 = head2;  // 用來存儲(chǔ)第二個(gè)鏈表的最后一個(gè)節(jié)點(diǎn)
    while(pTail2.next != NULL) {  
        pTail2 = pTail2.next; 
    } 
    return pTail1 == pTail2;  
}

查找單鏈表中的倒數(shù)第K個(gè)結(jié)點(diǎn)（k > 0）
主要思路就是使用兩個(gè)指針，先讓前面的指針走到正向第k個(gè)結(jié)點(diǎn)，這樣前后兩個(gè)指針的距離差是k-1，之后前后兩個(gè)指針一起向前走，前面的指針走到最后一個(gè)結(jié)點(diǎn)時(shí)，后面指針?biāo)附Y(jié)點(diǎn)就是倒數(shù)第k個(gè)結(jié)點(diǎn)。
參考代碼如下：

// 查找單鏈表中倒數(shù)第K個(gè)結(jié)點(diǎn)  
function GetRKthNode(head, k)
{  
    if(k == 0 || head == NULL) // 這里k的計(jì)數(shù)是從1開始的，若k為0或鏈表為空返回NULL  
        return NULL;  
  
    let pAhead = head;  
    let pBehind = head;  
    while(k > 1 && pAhead != NULL) // 前面的指針先走到正向第k個(gè)結(jié)點(diǎn)  
    {  
        pAhead = pAhead.next;  
        k--;  
    }  
    if(k > 1 || pAhead == NULL)     // 結(jié)點(diǎn)個(gè)數(shù)小于k，返回NULL  
        return NULL;  
    while(pAhead.next != NULL)  // 前后兩個(gè)指針一起向前走，直到前面的指針指向最后一個(gè)結(jié)點(diǎn)  
    {  
        pBehind = pBehind.next;  
        pAhead = pAhead.next;
    }  
    return pBehind;  // 后面的指針?biāo)附Y(jié)點(diǎn)就是倒數(shù)第k個(gè)結(jié)點(diǎn)  
}

查找單鏈表的中間結(jié)點(diǎn)
此題可應(yīng)用于上一題類似的思想。也是設(shè)置兩個(gè)指針，只不過這里是，兩個(gè)指針同時(shí)向前走，前面的指針每次走兩步，后面的指針每次走一步，前面的指針走到最后一個(gè)結(jié)點(diǎn)時(shí)，后面的指針?biāo)附Y(jié)點(diǎn)就是中間結(jié)點(diǎn)，即第（n/2+1）個(gè)結(jié)點(diǎn)。注意鏈表為空，鏈表結(jié)點(diǎn)個(gè)數(shù)為1和2的情況。時(shí)間復(fù)雜度O（n）。參考代碼如下：

// 獲取單鏈表中間結(jié)點(diǎn)，若鏈表長(zhǎng)度為n(n>0)，則返回第n/2+1個(gè)結(jié)點(diǎn)  
function GetMiddleNode(head)  
{  
    if(head == NULL || head.next == NULL) // 鏈表為空或只有一個(gè)結(jié)點(diǎn)，返回頭指針  
        return head;  
  
    let pAhead = head;  
    let pBehind = head;  
    while(pAhead.next != NULL) // 前面指針每次走兩步，直到指向最后一個(gè)結(jié)點(diǎn)，后面指針每次走一步  
    {  
        pAhead = pAhead.next;  
        pBehind = pBehind.next;  
        if(pAhead.next != NULL)  
            pAhead = pAhead.next;  
    }  
    return pBehind; // 后面的指針?biāo)附Y(jié)點(diǎn)即為中間結(jié)點(diǎn)  
}

反轉(zhuǎn)雙向鏈表

function reverse(head){
    let cur = null;
    while(head != null){
        cur = head;
        head = head.next;
        cur.next = cur.prev;
        cur.prev = head;
    }
    return cur;
}

二叉樹 概念

二叉樹（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)的定義

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

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

滿二叉樹

在一棵二叉樹中，如果所有分支結(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)樹的二叉樹，完全二叉樹的深度最小。

二叉樹的遍歷

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

二叉樹的遍歷有三種方式，如下：
前序遍歷：
若二叉樹為空，則空操作返回，否則先訪問根結(jié)點(diǎn)，然后前序遍歷左子樹，再前序遍歷右子樹。
中序遍歷：
若樹為空，則空操作返回，否則從根結(jié)點(diǎn)開始（注意并不是先訪問根結(jié)點(diǎn)），中序遍歷根結(jié)點(diǎn)的左子樹，然后是訪問根結(jié)點(diǎn)，最后中序遍歷右子樹。
后序遍歷：
若樹為空，則空操作返回，否則從左到右先葉子后結(jié)點(diǎn)的方式遍歷訪問左右子樹，最后訪問根結(jié)點(diǎn)。

二叉查找樹

二叉排序樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：
（1）若左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于或等于它的根結(jié)點(diǎn)的值；
（2）若右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于或等于它的根結(jié)點(diǎn)的值；
（3）左、右子樹也分別為二叉排序樹；

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

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)

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

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

二叉樹相關(guān)題目 求二叉樹中的節(jié)點(diǎn)個(gè)數(shù)

遞歸解法：
（1）如果二叉樹為空，節(jié)點(diǎn)個(gè)數(shù)為0
（2）如果二叉樹不為空，二叉樹節(jié)點(diǎn)個(gè)數(shù) = 左子樹節(jié)點(diǎn)個(gè)數(shù) + 右子樹節(jié)點(diǎn)個(gè)數(shù) + 1
參考代碼如下：

function GetNodeNum(pRoot)  
{  
    if(pRoot == NULL) return 0;  
    return GetNodeNum(pRoot->m_pLeft) + GetNodeNum(pRoot->m_pRight) + 1;  
}

求二叉樹的深度

遞歸解法：
（1）如果二叉樹為空，二叉樹的深度為0
（2）如果二叉樹不為空，二叉樹的深度 = max(左子樹深度，右子樹深度) + 1
參考代碼如下：

function GetDepth(pRoot)  
{  
    if(pRoot == NULL) return 0;  
    let depthLeft = GetDepth(pRoot->m_pLeft);  
    let depthRight = GetDepth(pRoot->m_pRight);  
    return depthLeft > depthRight ? (depthLeft + 1) : (depthRight + 1);   
}

前序遍歷，中序遍歷，后序遍歷

前序遍歷遞歸解法：
（1）如果二叉樹為空，空操作
（2）如果二叉樹不為空，訪問根節(jié)點(diǎn)，前序遍歷左子樹，前序遍歷右子樹
參考代碼如下：

function PreOrderTraverse(pRoot)  
{  
    if(pRoot == NULL) return;  
    Visit(pRoot); // 訪問根節(jié)點(diǎn)  
    PreOrderTraverse(pRoot->m_pLeft); // 前序遍歷左子樹  
    PreOrderTraverse(pRoot->m_pRight); // 前序遍歷右子樹  
}

中序遍歷遞歸解法
（1）如果二叉樹為空，空操作。
（2）如果二叉樹不為空，中序遍歷左子樹，訪問根節(jié)點(diǎn)，中序遍歷右子樹
參考代碼如下：

function InOrderTraverse(pRoot)  
{  
    if(pRoot == NULL) return;  
    InOrderTraverse(pRoot->m_pLeft); // 中序遍歷左子樹  
    Visit(pRoot); // 訪問根節(jié)點(diǎn)  
    InOrderTraverse(pRoot->m_pRight); // 中序遍歷右子樹  
}

后序遍歷遞歸解法
（1）如果二叉樹為空，空操作
（2）如果二叉樹不為空，后序遍歷左子樹，后序遍歷右子樹，訪問根節(jié)點(diǎn)
參考代碼如下：

function PostOrderTraverse(pRoot)  
{  
    if(pRoot == NULL) return;  
    PostOrderTraverse(pRoot->m_pLeft); // 后序遍歷左子樹  
    PostOrderTraverse(pRoot->m_pRight); // 后序遍歷右子樹  
    Visit(pRoot); // 訪問根節(jié)點(diǎn)  
}

分層遍歷二叉樹（按層次從上往下，從左往右）

相當(dāng)于廣度優(yōu)先搜索，使用隊(duì)列實(shí)現(xiàn)。隊(duì)列初始化，將根節(jié)點(diǎn)壓入隊(duì)列。當(dāng)隊(duì)列不為空，進(jìn)行如下操作：彈出一個(gè)節(jié)點(diǎn)，訪問，若左子節(jié)點(diǎn)或右子節(jié)點(diǎn)不為空，將其壓入隊(duì)列。

function LevelTraverse(pRoot)  
{  
    if(pRoot == NULL) return;  
    queue q;  
    q.push(pRoot);  
    while(!q.empty())  
    {  
        BinaryTreeNode * pNode = q.front();  
        q.pop();  
        Visit(pNode); // 訪問節(jié)點(diǎn)  
        if(pNode->m_pLeft != NULL)  
            q.push(pNode->m_pLeft);  
        if(pNode->m_pRight != NULL)  
            q.push(pNode->m_pRight);  
    }  
    return;  
}

將二叉查找樹變?yōu)橛行虻碾p向鏈表

要求不能創(chuàng)建新節(jié)點(diǎn)，只調(diào)整指針。
遞歸解法：
（1）如果二叉樹查找樹為空，不需要轉(zhuǎn)換，對(duì)應(yīng)雙向鏈表的第一個(gè)節(jié)點(diǎn)是NULL，最后一個(gè)節(jié)點(diǎn)是NULL
（2）如果二叉查找樹不為空：
如果左子樹為空，對(duì)應(yīng)雙向有序鏈表的第一個(gè)節(jié)點(diǎn)是根節(jié)點(diǎn)，左邊不需要其他操作；
如果左子樹不為空，轉(zhuǎn)換左子樹，二叉查找樹對(duì)應(yīng)雙向有序鏈表的第一個(gè)節(jié)點(diǎn)就是左子樹轉(zhuǎn)換后雙向有序鏈表的第一個(gè)節(jié)點(diǎn)，同時(shí)將根節(jié)點(diǎn)和左子樹轉(zhuǎn)換后的雙向有序鏈表的最后一個(gè)節(jié)點(diǎn)連接；
如果右子樹為空，對(duì)應(yīng)雙向有序鏈表的最后一個(gè)節(jié)點(diǎn)是根節(jié)點(diǎn)，右邊不需要其他操作；
如果右子樹不為空，對(duì)應(yīng)雙向有序鏈表的最后一個(gè)節(jié)點(diǎn)就是右子樹轉(zhuǎn)換后雙向有序鏈表的最后一個(gè)節(jié)點(diǎn)，同時(shí)將根節(jié)點(diǎn)和右子樹轉(zhuǎn)換后的雙向有序鏈表的第一個(gè)節(jié)點(diǎn)連接。
參考代碼如下：

/*******************************************************************
參數(shù)： 
pRoot: 二叉查找樹根節(jié)點(diǎn)指針 
pFirstNode: 轉(zhuǎn)換后雙向有序鏈表的第一個(gè)節(jié)點(diǎn)指針 
pLastNode: 轉(zhuǎn)換后雙向有序鏈表的最后一個(gè)節(jié)點(diǎn)指針 
*******************************************************************/  
function Convert(BinaryTreeNode * pRoot,   
             BinaryTreeNode * & pFirstNode, BinaryTreeNode * & pLastNode)  
{  
    BinaryTreeNode *pFirstLeft, *pLastLeft, * pFirstRight, *pLastRight;  
    if(pRoot == NULL)   
    {  
        pFirstNode = NULL;  
        pLastNode = NULL;  
        return;  
    }  
  
    if(pRoot->m_pLeft == NULL)  
    {  
        // 如果左子樹為空，對(duì)應(yīng)雙向有序鏈表的第一個(gè)節(jié)點(diǎn)是根節(jié)點(diǎn)  
        pFirstNode = pRoot;  
    }  
    else  
    {  
        Convert(pRoot->m_pLeft, pFirstLeft, pLastLeft);  
        // 二叉查找樹對(duì)應(yīng)雙向有序鏈表的第一個(gè)節(jié)點(diǎn)就是左子樹轉(zhuǎn)換后雙向有序鏈表的第一個(gè)節(jié)點(diǎn)  
        pFirstNode = pFirstLeft;  
        // 將根節(jié)點(diǎn)和左子樹轉(zhuǎn)換后的雙向有序鏈表的最后一個(gè)節(jié)點(diǎn)連接  
        pRoot->m_pLeft = pLastLeft;  
        pLastLeft->m_pRight = pRoot;  
    }  
  
    if(pRoot->m_pRight == NULL)  
    {  
        // 對(duì)應(yīng)雙向有序鏈表的最后一個(gè)節(jié)點(diǎn)是根節(jié)點(diǎn)  
        pLastNode = pRoot;  
    }  
    else  
    {  
        Convert(pRoot->m_pRight, pFirstRight, pLastRight);  
        // 對(duì)應(yīng)雙向有序鏈表的最后一個(gè)節(jié)點(diǎn)就是右子樹轉(zhuǎn)換后雙向有序鏈表的最后一個(gè)節(jié)點(diǎn)  
        pLastNode = pLastRight;  
        // 將根節(jié)點(diǎn)和右子樹轉(zhuǎn)換后的雙向有序鏈表的第一個(gè)節(jié)點(diǎn)連接  
        pRoot->m_pRight = pFirstRight;  
        pFirstRight->m_pLeft = pRoot;  
    }  
  
    return;  
}

求二叉樹第K層的節(jié)點(diǎn)個(gè)數(shù)

遞歸解法：
（1）如果二叉樹為空或者k<1返回0
（2）如果二叉樹不為空并且k==1，返回1
（3）如果二叉樹不為空且k>1，返回左子樹中k-1層的節(jié)點(diǎn)個(gè)數(shù)與右子樹k-1層節(jié)點(diǎn)個(gè)數(shù)之和
參考代碼如下：

function GetNodeNumKthLevel(pRoot, k)  
{  
    if(pRoot == NULL || k < 1) return 0;  
    if(k == 1) return 1;  
    let numLeft = GetNodeNumKthLevel(pRoot->m_pLeft, k-1); // 左子樹中k-1層的節(jié)點(diǎn)個(gè)數(shù)  
    let numRight = GetNodeNumKthLevel(pRoot->m_pRight, k-1); // 右子樹中k-1層的節(jié)點(diǎn)個(gè)數(shù)  
    return (numLeft + numRight);  
}

判斷兩棵二叉樹是否結(jié)構(gòu)相同

不考慮數(shù)據(jù)內(nèi)容。結(jié)構(gòu)相同意味著對(duì)應(yīng)的左子樹和對(duì)應(yīng)的右子樹都結(jié)構(gòu)相同。
遞歸解法：
（1）如果兩棵二叉樹都為空，返回真
（2）如果兩棵二叉樹一棵為空，另一棵不為空，返回假
（3）如果兩棵二叉樹都不為空，如果對(duì)應(yīng)的左子樹和右子樹都同構(gòu)返回真，其他返回假
參考代碼如下：

function StructureCmp(BinaryTreeNode * pRoot1, BinaryTreeNode * pRoot2)  
{  
    if(pRoot1 == NULL && pRoot2 == NULL) // 都為空，返回真  
        return true;  
    else if(pRoot1 == NULL || pRoot2 == NULL) // 有一個(gè)為空，一個(gè)不為空，返回假  
        return false;  
    let resultLeft = StructureCmp(pRoot1->m_pLeft, pRoot2->m_pLeft); // 比較對(duì)應(yīng)左子樹   
    let resultRight = StructureCmp(pRoot1->m_pRight, pRoot2->m_pRight); // 比較對(duì)應(yīng)右子樹  
    return (resultLeft && resultRight);  
}

判斷二叉樹是不是平衡二叉樹

遞歸解法：
（1）如果二叉樹為空，返回真
（2）如果二叉樹不為空，如果左子樹和右子樹都是AVL樹并且左子樹和右子樹高度相差不大于1，返回真，其他返回假

求二叉樹的鏡像

遞歸解法：
（1）如果二叉樹為空，返回空
（2）如果二叉樹不為空，求左子樹和右子樹的鏡像，然后交換左子樹和右子樹
參考代碼如下：

function Mirror(BinaryTreeNode * pRoot)  
{  
    if(pRoot == NULL) // 返回NULL  
        return NULL;  
    BinaryTreeNode * pLeft = Mirror(pRoot->m_pLeft); // 求左子樹鏡像  
    BinaryTreeNode * pRight = Mirror(pRoot->m_pRight); // 求右子樹鏡像  
        // 交換左子樹和右子樹  
    pRoot->m_pLeft = pRight;  
    pRoot->m_pRight = pLeft;  
    return pRoot;  
}

判斷二叉樹是不是完全二叉樹

若設(shè)二叉樹的深度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第 h 層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊，這就是完全二叉樹。
有如下算法，按層次（從上到下，從左到右）遍歷二叉樹，當(dāng)遇到一個(gè)節(jié)點(diǎn)的左子樹為空時(shí)，則該節(jié)點(diǎn)右子樹必須為空，且后面遍歷的節(jié)點(diǎn)左右子樹都必須為空，否則不是完全二叉樹。

bool IsCompleteBinaryTree(BinaryTreeNode * pRoot)  
{  
    if(pRoot == NULL)  
        return false;  
    queue q;  
    q.push(pRoot);  
    bool mustHaveNoChild = false;  
    bool result = true;  
    while(!q.empty())  
    {  
        BinaryTreeNode * pNode = q.front();  
        q.pop();  
        if(mustHaveNoChild) // 已經(jīng)出現(xiàn)了有空子樹的節(jié)點(diǎn)了，后面出現(xiàn)的必須為葉節(jié)點(diǎn)（左右子樹都為空）  
        {  
            if(pNode->m_pLeft != NULL || pNode->m_pRight != NULL)  
            {  
                result = false;  
                break;  
            }  
        }  
        else  
        {  
            if(pNode->m_pLeft != NULL && pNode->m_pRight != NULL)  
            {  
                q.push(pNode->m_pLeft);  
                q.push(pNode->m_pRight);  
            }  
            else if(pNode->m_pLeft != NULL && pNode->m_pRight == NULL)  
            {  
                mustHaveNoChild = true;  
                q.push(pNode->m_pLeft);  
            }  
            else if(pNode->m_pLeft == NULL && pNode->m_pRight != NULL)  
            {  
                result = false;  
                break;  
            }  
            else  
            {  
                mustHaveNoChild = true;  
            }  
        }  
    }  
    return result;  
}

GPU云服務(wù)器云服務(wù)器二叉樹 python二叉樹平衡二叉樹實(shí)現(xiàn)二叉樹

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

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

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

Little_XM

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

gatling學(xué)習(xí)筆記（一）——概念理解

閱讀 1674·2021-10-12 10:11
修羅云：成立兩周年特惠，有深港IPCL、香港HKT、廣州、中山、徐州、杭州、佛山等，最低6折起

閱讀 3798·2021-09-03 10:35
表單密碼自動(dòng)填充hack

閱讀 1469·2019-08-30 15:55
小程序自定義switch組件

閱讀 2163·2019-08-30 15:54
H5項(xiàng)目常見問題及注意事項(xiàng)

閱讀 1019·2019-08-30 13:07
vw+rem移動(dòng)端自適應(yīng)布局

閱讀 1051·2019-08-30 11:09
翻譯 | 深入理解CSS時(shí)序函數(shù)

閱讀 602·2019-08-29 13:21
自制jq分頁插件

閱讀 2674·2019-08-29 11:32

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

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來選購(gòu)！

二叉樹那些事兒

相關(guān)文章

JDK源碼那些事兒之紅黑樹基礎(chǔ)上篇

JDK源碼那些事兒之紅黑樹基礎(chǔ)下篇

【數(shù)據(jù)結(jié)構(gòu)初階】第八篇——二叉樹的鏈?zhǔn)浇Y(jié)構(gòu)（二叉樹的前、中和后序遍歷+層序遍歷+鏈?zhǔn)浇Y(jié)構(gòu)的實(shí)現(xiàn)+相關(guān)

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

**數(shù)據(jù)結(jié)構(gòu)-二叉樹和二叉查找樹**

發(fā)表評(píng)論

0條評(píng)論

Little_XM

男|高級(jí)講師

TA的文章

gatling學(xué)習(xí)筆記（一）——概念理解

修羅云：成立兩周年特惠，有深港IPCL、香港HKT、廣州、中山、徐州、杭州、佛山等，最低6折起

表單密碼自動(dòng)填充hack

小程序自定義switch組件

H5項(xiàng)目常見問題及注意事項(xiàng)

vw+rem移動(dòng)端自適應(yīng)布局

翻譯 | 深入理解CSS時(shí)序函數(shù)

自制jq分頁插件

最新活動(dòng)

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來選購(gòu)！

二叉樹那些事兒

相關(guān)文章

發(fā)表評(píng)論

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來選購(gòu)！