摘要：大家在聊到二叉樹的時候，總會離不開鏈表。受限線性表主要包括棧和隊列，受限表示對結點的操作受限制。存儲結構線性表主要由順序表示或鏈式表示。鏈式表示指的是用一組任意的存儲單元存儲線性表中的數據元素，稱為線性表的鏈式存儲結構。

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

線性表是最基本、最簡單、也是最常用的一種數據結構。

線性表中數據元素之間的關系是一對一的關系，即除了第一個和最后一個數據元素之外，其它數據元素都是首尾相接的（注意，這句話只適用大部分線性表，而不是全部。比如，循環(huán)鏈表邏輯層次上也是一種線性表（存儲層次上屬于鏈式存儲），但是把最后一個數據元素的尾指針指向了首位結點）。

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

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

線性表主要由順序表示或鏈式表示。在實際應用中，常以棧、隊列、字符串等特殊形式使用。

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

鏈式表示指的是用一組任意的存儲單元存儲線性表中的數據元素，稱為線性表的鏈式存儲結構。它的存儲單元可以是連續(xù)的，也可以是不連續(xù)的。在表示數據元素之間的邏輯關系時，除了存儲其本身的信息之外，還需存儲一個指示其直接后繼的信息（即直接后繼的存儲位置），這兩部分信息組成數據元素的存儲映像，稱為結點（node）。它包括兩個域；存儲數據元素信息的域稱為數據域；存儲直接后繼存儲位置的域稱為指針域。指針域中存儲的信息稱為指針或鏈

鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表由一系列結點（鏈表中每一個元素稱為結點）組成，結點可以在運行時動態(tài)生成。

每個結點包括兩個部分：

存儲數據元素的數據域

存儲下一個結點地址的指針域。

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

class ListNode
{
    let nodeValue; //數據
    let next; //指向下一個節(jié)點的指針

};

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

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

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

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

循環(huán)鏈表，類似于單鏈表，也是一種鏈式存儲結構，循環(huán)鏈表由單鏈表演化過來。單鏈表的最后一個結點的鏈域指向NULL，而循環(huán)鏈表的建立，不要專門的頭結點，讓最后一個結點的鏈域指向鏈表結點。

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

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

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

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

求單鏈表中結點的個數
這是最最基本的了，應該能夠迅速寫出正確的代碼，注意檢查鏈表是否為空。時間復雜度為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;  
} 

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

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

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

// 合并兩個有序鏈表  
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;  
} 

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

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

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

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

查找單鏈表中的倒數第K個結點（k > 0）
主要思路就是使用兩個指針，先讓前面的指針走到正向第k個結點，這樣前后兩個指針的距離差是k-1，之后前后兩個指針一起向前走，前面的指針走到最后一個結點時，后面指針所指結點就是倒數第k個結點。
參考代碼如下：

// 查找單鏈表中倒數第K個結點  
function GetRKthNode(head, k)
{  
    if(k == 0 || head == NULL) // 這里k的計數是從1開始的，若k為0或鏈表為空返回NULL  
        return NULL;  
  
    let pAhead = head;  
    let pBehind = head;  
    while(k > 1 && pAhead != NULL) // 前面的指針先走到正向第k個結點  
    {  
        pAhead = pAhead.next;  
        k--;  
    }  
    if(k > 1 || pAhead == NULL)     // 結點個數小于k，返回NULL  
        return NULL;  
    while(pAhead.next != NULL)  // 前后兩個指針一起向前走，直到前面的指針指向最后一個結點  
    {  
        pBehind = pBehind.next;  
        pAhead = pAhead.next;
    }  
    return pBehind;  // 后面的指針所指結點就是倒數第k個結點  
} 

查找單鏈表的中間結點
此題可應用于上一題類似的思想。也是設置兩個指針，只不過這里是，兩個指針同時向前走，前面的指針每次走兩步，后面的指針每次走一步，前面的指針走到最后一個結點時，后面的指針所指結點就是中間結點，即第（n/2+1）個結點。注意鏈表為空，鏈表結點個數為1和2的情況。時間復雜度O（n）。參考代碼如下：

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

反轉雙向鏈表

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）個結點的有限集合，該集合或者為空集（空二叉樹），或者由一個根結點和兩棵互不相交的、分別稱為根結點的左子樹和右子樹的二叉樹組成。

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

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

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

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

完全二叉樹的特點有：

葉子結點只能出現在最下兩層。

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

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

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

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

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

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

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

二叉查找樹（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é)點中的數據
}

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

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;
}

遞歸解法：
（1）如果二叉樹為空，節(jié)點個數為0
（2）如果二叉樹不為空，二叉樹節(jié)點個數 = 左子樹節(jié)點個數 + 右子樹節(jié)點個數 + 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é)點，前序遍歷左子樹，前序遍歷右子樹
參考代碼如下：

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

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

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

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

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

相當于廣度優(yōu)先搜索，使用隊列實現。隊列初始化，將根節(jié)點壓入隊列。當隊列不為空，進行如下操作：彈出一個節(jié)點，訪問，若左子節(jié)點或右子節(jié)點不為空，將其壓入隊列。

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

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

/*******************************************************************
參數： 
pRoot: 二叉查找樹根節(jié)點指針 
pFirstNode: 轉換后雙向有序鏈表的第一個節(jié)點指針 
pLastNode: 轉換后雙向有序鏈表的最后一個節(jié)點指針 
*******************************************************************/  
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)  
    {  
        // 如果左子樹為空，對應雙向有序鏈表的第一個節(jié)點是根節(jié)點  
        pFirstNode = pRoot;  
    }  
    else  
    {  
        Convert(pRoot->m_pLeft, pFirstLeft, pLastLeft);  
        // 二叉查找樹對應雙向有序鏈表的第一個節(jié)點就是左子樹轉換后雙向有序鏈表的第一個節(jié)點  
        pFirstNode = pFirstLeft;  
        // 將根節(jié)點和左子樹轉換后的雙向有序鏈表的最后一個節(jié)點連接  
        pRoot->m_pLeft = pLastLeft;  
        pLastLeft->m_pRight = pRoot;  
    }  
  
    if(pRoot->m_pRight == NULL)  
    {  
        // 對應雙向有序鏈表的最后一個節(jié)點是根節(jié)點  
        pLastNode = pRoot;  
    }  
    else  
    {  
        Convert(pRoot->m_pRight, pFirstRight, pLastRight);  
        // 對應雙向有序鏈表的最后一個節(jié)點就是右子樹轉換后雙向有序鏈表的最后一個節(jié)點  
        pLastNode = pLastRight;  
        // 將根節(jié)點和右子樹轉換后的雙向有序鏈表的第一個節(jié)點連接  
        pRoot->m_pRight = pFirstRight;  
        pFirstRight->m_pLeft = pRoot;  
    }  
  
    return;  
}  

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

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é)點個數  
    let numRight = GetNodeNumKthLevel(pRoot->m_pRight, k-1); // 右子樹中k-1層的節(jié)點個數  
    return (numLeft + numRight);  
} 

不考慮數據內容。結構相同意味著對應的左子樹和對應的右子樹都結構相同。
遞歸解法：
（1）如果兩棵二叉樹都為空，返回真
（2）如果兩棵二叉樹一棵為空，另一棵不為空，返回假
（3）如果兩棵二叉樹都不為空，如果對應的左子樹和右子樹都同構返回真，其他返回假
參考代碼如下：

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

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

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) // 已經出現了有空子樹的節(jié)點了，后面出現的必須為葉節(jié)點（左右子樹都為空）  
        {  
            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;  
}