友情鏈接：C/C++系列系統(tǒng)學(xué)習(xí)目錄

??樹

??一、樹的原理精講

（一）樹的定義

之前我們一直在談的是一對一的線性結(jié)構(gòu)，可現(xiàn)實中，還有很多一對多的情況需要處理，所以我們需要研究這種一對多的數(shù)據(jù)結(jié)構(gòu)——“樹”

樹：樹是由n（n>=0）個有限結(jié)點組成一個具有層次關(guān)系的集合。當(dāng)n = 0時，稱為空樹。把它叫做“樹”是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。

• 有且僅有一個特定的稱為根的結(jié)點。
• 當(dāng)n>1時，其余節(jié)點可分為m（m>0）個互不相交的有限集T1,T2,…,Tm，其中每個集合本身又是一棵樹，并且稱為根的子樹。
• 樹的根結(jié)點沒有前驅(qū)（父節(jié)點），除根結(jié)點外的所有結(jié)點有且只有一個前驅(qū)（父節(jié)點）。
• 樹中所有結(jié)點可以有零個或多個后繼（子結(jié)點）。

以上可以看出，在樹的定義中又用到了樹的概念，顯然是一種遞歸的方式，所以，樹不單單是一種分層結(jié)構(gòu)，還是一種遞歸的數(shù)據(jù)結(jié)構(gòu)

（二）基本術(shù)語

區(qū)別說明：

和我之前在線性表中說的一樣，在C語言中，我們一般是從0開始第一個下標(biāo)的，但我們數(shù)數(shù)都是從1開始數(shù)的，在大多數(shù)書記講解中，樹的計數(shù)，比如：深度、高度、層級以及其它許多數(shù)據(jù)結(jié)構(gòu)叔叔起始也是1，如果為了和C語言下標(biāo)法嵌合，我們也可以將這些從0開始數(shù)，只是在代碼實現(xiàn)上需要改動一點而已。

為了習(xí)慣C語言下標(biāo)法，我經(jīng)常用后者，兩種代碼實現(xiàn)的差別我都會提到，讀者不必擔(dān)心這點，只是希望讀者注意此差距，因為不同的文章用的不同的方法，避免造成歧義。

以上的圖即采用數(shù)數(shù)從0開始的方式

（三）樹的性質(zhì)

提幾個基本性質(zhì)，其它還有很多讀者自行搜索相關(guān)資料

1. 樹中的結(jié)點數(shù)等于所有結(jié)點的度數(shù)加1.
2. 度為m的樹中第i層上至多有$m^i$個結(jié)點（i > = 0 ）
3. 高度為h的m叉樹至多有$( m^{h+1} ? 1 ) / ( m ? 1 ) ( m^h ? 1 ) / ( m ? 1 ) $
4. 具有n個結(jié)點的m叉樹的最小高度為$ log_m ( n ( m ? 1 ) + 1 )-1 $，從1開始數(shù)的話最后不減去個1即可

??二、樹的存儲結(jié)構(gòu)

（一）雙親表示法

每個結(jié)點中，包含data和parent兩部分，data為數(shù)據(jù)域，保存自身的數(shù)據(jù)，而parent為指針域，存儲該結(jié)點的雙親在數(shù)組中的下標(biāo)

結(jié)構(gòu)體定義：

/*樹的雙親表示法結(jié)點結(jié)構(gòu)定義*/
#define MAX_TREE_SIZE 100

typedef int ElemType;	//樹結(jié)點的數(shù)據(jù)類型，目前暫定為整型

/*結(jié)點結(jié)構(gòu)*/
typedef struct PTNode{
	ElemType data;	//結(jié)點數(shù)據(jù)
	int parent;	//雙親位置
}PTNode;

/*樹結(jié)構(gòu)*/
typedef struct{
	PTNode nodes[MAX_TREE_SIZE];	//結(jié)點數(shù)組
	int r, n;	//根的位置和結(jié)點數(shù)
}PTree;

解釋：

這樣的存儲結(jié)構(gòu)，我們可以根據(jù)結(jié)點的parent 指針很容易找到它的雙親結(jié)點，所用的時間復(fù)雜度為0(1)，直到parent為-1時，表示找到了樹結(jié)點的根?？扇绻覀円澜Y(jié)點的孩子是什么，則需要遍歷整顆樹

（二）孩子表示法

前面已經(jīng)知道在樹中每個結(jié)點有零個或多個子結(jié)點，我們將每個結(jié)點的孩子節(jié)點以單鏈表的形式排列起來，則n個結(jié)點就有n個孩子鏈表，如果是葉子結(jié)點則它的孩子鏈表為空。然后這n個頭指針又組成一個線性表，采用順序存儲結(jié)構(gòu)，存放進一個一維數(shù)組中

1. 方法一：

   結(jié)構(gòu)體定義：

   /*樹的孩子表示法結(jié)構(gòu)定義*/
   #define MAX_TREE_SIZE 100
   
   /*樹的結(jié)點定義*/
   typedef struct CTNode{
   	ElemType data;
   	struct CTNode *next;
   }CTNode;
   
   /*樹結(jié)構(gòu)*/
   typedef struct{
   	CTNode nodes[MAX_TREE_SIZE];	//結(jié)點數(shù)組
   	int r, n;	//根的位置和結(jié)點數(shù)
   }
   

   解釋：

   上面已經(jīng)提到，n個結(jié)點就有n個孩子鏈表，然后我們將這n個孩子鏈表的表頭放進一個一維結(jié)構(gòu)體數(shù)組中即可，并且孩子鏈表的順序都是從左到右，存在數(shù)組中的表頭即為該子樹的根結(jié)點

2. 方法二：

   在《大話數(shù)據(jù)結(jié)構(gòu)》是以另外一種方式定義的，我們將孩子鏈表的結(jié)點，表頭分別定義，需要設(shè)計兩種數(shù)據(jù)結(jié)構(gòu)：

   （1）孩子鏈表的結(jié)點結(jié)構(gòu)

   

   （2）頭指針組成的數(shù)組的每個元素（表頭）結(jié)構(gòu)

   

   結(jié)構(gòu)體定義：

/*樹的孩子表示法結(jié)構(gòu)定義*/
#define MAX_TREE_SIZE 100

/*孩子結(jié)點*/
typedef struct CTNode{
  int child;
  struct CTNode *next;
}*ChildPtr;

/*表頭結(jié)點*/
typedef struct{
  ElemType data;
  ChildPtr firstchild;
}CTBox;

/*樹結(jié)構(gòu)*/
typedef struct{
  CTBox nodes[MAX_TREE_SIZE];	//結(jié)點數(shù)組
  int r, n;	//根的位置和結(jié)點數(shù)
}

解釋：

每個結(jié)點我們都存在了數(shù)組里面，所以表頭我們只需要表示出數(shù)據(jù)以及指向孩子鏈表的指針即可，進而孩子鏈表的結(jié)點因為它作為某個表頭的孩子，同時又作為另一顆子樹的表頭存在數(shù)組里，所以我們只需要用個int類型表示是數(shù)組中哪個結(jié)點作為孩子即可，還有一個next指針指向它的兄弟結(jié)點

這兩種方式本質(zhì)都是一樣的，這樣的結(jié)構(gòu)對于我們要查找某個結(jié)點的某個孩子，或者找某個結(jié)點的兄弟，只需要查找這個結(jié)點的孩子單鏈表即可。對于遍歷整棵樹也是很方便的，對頭結(jié)點的數(shù)組循環(huán)即可。

但同時，又造成了我們很難訪問到某個結(jié)點的雙親結(jié)點，需要整棵樹遍歷才行，失去了雙親表示法的優(yōu)點，難道就不可以把雙親表示法和孩子表示法綜合一下嗎? 當(dāng)然是可以，這個讀者可自己嘗試結(jié)合一下，在次不做贅述。

（三）孩子兄弟表示法

剛才我們分別從雙親的角度和從孩子的角度研究樹的存儲結(jié)構(gòu)，如果我們從樹結(jié)點的兄弟的角度又會如何呢？

任意一棵樹， 它的結(jié)點的第一個孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。 因此，我們設(shè)置兩個指針，分別指向該結(jié)點的第一個孩子和此結(jié)點的右兄弟。

結(jié)構(gòu)體定義：

/*樹的孩子兄弟表示法結(jié)構(gòu)定義*/
typedef struct CSNode{
	TElemtype data;
	struct CSNode *firstchild, *rightsib;
} CSNode, *CSTree;

于是通過這種結(jié)構(gòu)，我們就把原來的樹變成了這個樣子：

這不就是個二叉樹么？

我們在實際使用中最常用的也就是二叉樹，這種存儲結(jié)構(gòu)的最大優(yōu)點就是：它把一棵復(fù)雜的樹變成了一棵二叉樹，它和二叉樹的二叉鏈表表示完全一樣。可利用二叉樹的算法來實現(xiàn)對樹的操作 。接下來，我們就詳細來介紹一下二叉樹。

??二叉樹

??一、二叉樹的原理精講

（一）二叉樹的定義

我們以前介紹的線性表一樣，一個沒有限制的線性表應(yīng)用范圍可能有限，但是我們對線性表進行一些限制就可以衍生出非常有用的數(shù)據(jù)結(jié)構(gòu)如棧、隊列、優(yōu)先隊列等。

樹也是一樣，一個沒有限制的樹由于太靈活，控制起來比較復(fù)雜。如果對普通的樹加上一些人為的限制，比如節(jié)點只允許有兩個子節(jié)點，這就是我們接下來要介紹的二叉樹

二叉樹：與樹相似，二叉樹也以遞歸的形式定義。二叉樹是n (n≥0) 個結(jié)點的有限集合:

• 或者為空二叉樹，即n=0。
• 或者由一個根結(jié)點和兩個互不相交的被稱為根的左子樹和右子樹組成。左子樹和右子樹又分別是一棵二叉樹。
• 每個結(jié)點最多只能有兩個分支的樹，左邊的分支稱之為左子樹，右邊的分支稱之為右子樹。

二叉樹是一個有序樹，若將其左、右子樹顛倒，則成為另一棵不同的二叉樹。即使樹中結(jié)點只有一棵子樹，也要區(qū)分它是左子樹還是右子樹。故而二叉樹有五種基本形態(tài)：

（二）二叉樹的性質(zhì)

1. 任意一棵樹，若結(jié)點數(shù)量為n,則邊的數(shù)量為n ? 1。
2. 非空二叉樹上的葉子結(jié)點數(shù)等于度為2的結(jié)點數(shù)加1，即$n_0=n_2+1$。
3. 在非空二叉樹中，第 $i$ 層的結(jié)點總數(shù)不超過 $2^i,i>=0$；如果層數(shù)是從1開始，則定義改為：非空二叉樹上第 $i$ 層上至多有$2^i?1$個結(jié)點，i>=1。
4. 高度為 h 的二叉樹最多有 $2^{h+1}?1個$結(jié)點$(h>=0)$，最少有 $h+1$ 個結(jié)點；同樣若高度從1開始：高度為h的二叉樹至多有$2^h?1$ 個結(jié)點$(h\ge 1)$。
5. 對于任意一棵二叉樹，如果其葉結(jié)點數(shù)為 $N_0$，而度數(shù)為 2 的結(jié)點總數(shù)為 $N_2$，則 $N_0=N_2+1$；
6. 具有$n(n>0)$個結(jié)點的完全二叉樹的高度為$lo{g}_{2}n$。從1開始的話就加各一即可，高度為$lo{g}_{2}n+1$
7. 對完全二叉樹按從上到下、從左到右的順序依次編號1，2…，n,則有以下關(guān)系:
   • $i>1$時，結(jié)點$i$的雙親的編號為$i/2$，即當(dāng)$i$為偶數(shù)時， 它是雙親的左孩子；當(dāng)$i$為奇數(shù)時，它是雙親的右孩子。
   • 當(dāng)$2 i ≤ n i$的左孩子編號為$2i$, 否則無左孩子。
   • 當(dāng)$2 i + 1 ≤ n i$的右孩子編號為$2i+1$，否則無右孩子。
   • 結(jié)點$i$所在層次(深度)為$lo{g}_{2}n+1$。
8. 對完全二叉樹按從上到下、從左到右的順序依次編號0，1…，n:
   • $i$的左子結(jié)點：$2i+1$，$i$的右子結(jié)點：$2i+2$
   • i的父結(jié)點：$(i?1)/2$

??二、二叉樹的存儲結(jié)構(gòu)

（一）順序存儲結(jié)構(gòu)

前面我們已經(jīng)談到了樹的存儲結(jié)構(gòu)，并且談到順序存儲對樹的這種一對多的關(guān)系結(jié)構(gòu)實現(xiàn)起來是比較困難的。但是二叉樹是一種特殊的樹，由于它的特殊性，使得用順序存儲結(jié)構(gòu)也可以實現(xiàn)

二叉樹的順序存儲：用一組地址連續(xù)的存儲單元依次自上而下、自左至右存儲完全二叉樹上的結(jié)點元素，即將完全二叉樹上編號為i的結(jié)點元素存儲在一維數(shù)組下標(biāo)為i的分量中。還是一樣從0開始數(shù)數(shù)，如果從1開始數(shù)結(jié)點數(shù)，就應(yīng)該將編號為i的結(jié)點存在一維數(shù)組下標(biāo)為i-1的位置上

依據(jù)二叉樹的性質(zhì)，完全二叉樹和滿二叉樹采用順序存儲比較合適，樹中結(jié)點的序號可以唯一地反映結(jié)點之間的邏輯關(guān)系，這樣既能最大可能地節(jié)省存儲空間，又能利用數(shù)組元素的下標(biāo)值確定結(jié)點在二叉樹中的位置，以及結(jié)點之間的關(guān)系。

對于一般的二叉樹，為了讓數(shù)組下標(biāo)能反映二叉樹中結(jié)點之間的邏輯關(guān)系，只能添加一些并不存在的空結(jié)點，讓其每個結(jié)點與完全二叉樹上的結(jié)點相對照，再存儲到一維數(shù)組的相應(yīng)分量中。然而，在最壞情況下，一個高度為h且只有h+1個結(jié)點的單支樹卻需要占據(jù)近$2(h+1)?1$個存儲單元。

（二）鏈?zhǔn)酱鎯Y(jié)構(gòu)

既然順序存儲結(jié)構(gòu)適用性不強，我們就要考慮鏈?zhǔn)酱鎯Y(jié)構(gòu)。在前面講樹的存儲結(jié)構(gòu)中孩子兄弟表示法就是采用二叉鏈表的方式將一棵復(fù)雜的樹變成了一棵二叉樹。樹的孩子兄弟表示法和二叉樹的二叉鏈表表示完全一樣

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

講孩子兄弟表示法的時候，我們設(shè)置的兩個指針firstchild指向該結(jié)點的第一個孩子結(jié)點的存儲地址，rightsib指針，存儲該結(jié)點的右兄弟結(jié)點的存儲地址。我們只需要稍微轉(zhuǎn)換一下思想：

每個結(jié)點包含兩個指針域，指向兩個孩子結(jié)點，LCHILD指向左子結(jié)點，RCHILD指向右子結(jié)點，同樣還包含一個數(shù)據(jù)域，存儲結(jié)點信息

結(jié)構(gòu)體定義：

/*樹的孩子兄弟表示法結(jié)構(gòu)定義*/
typedef struct BITNode{
	Elemtype data;
	struct BITNode *lchild, *rchild;
} BITNode, *BITNode;

??二、常見二叉樹的分類

（一）斜樹

所有的結(jié)點都只有左子樹的二叉樹叫左斜樹。所有結(jié)點都是只有右子樹的二叉樹叫右斜樹。這兩者統(tǒng)稱為斜樹。

（二）完全二叉樹

若設(shè)二叉樹的高度為 h，除第 h 層外，其它各層 (0～h-1) 的結(jié)點數(shù)都達到最大個數(shù)，第 h 層有葉子節(jié)點，并且葉子結(jié)點都是從左到右依次排布，這就是完全二叉樹（堆就是完全二叉樹）。

堆也是常見的數(shù)據(jù)結(jié)構(gòu)，常常單獨拿出來研究使用：【數(shù)據(jù)結(jié)構(gòu)篇C++實現(xiàn)】- 堆

（三）滿二叉樹

除了葉結(jié)點外每一個結(jié)點都有左右子節(jié)點且葉子結(jié)點都處在最底層的二叉樹。

滿二叉樹就是特殊的完全二叉樹

（四）平衡二叉樹

又被稱為 AVL 樹，它是一顆空樹或左右兩個子樹的高度差的絕對值不超過 1，并且左右兩個子樹都是一棵平衡二叉樹

（五）二叉搜索樹（二叉排序樹）

又稱二叉查找樹、二叉排序樹（Binary Sort Tree）。它是一顆空樹或是滿足下列性質(zhì)的二叉樹：

• 若左子樹不空，則左子樹上所有節(jié)點的值均小于或等于它的根節(jié)點的值；
• 若右子樹不空，則右子樹上所有節(jié)點的值均大于或等于它的根節(jié)點的值；
• 左、右子樹也分別為二叉排序樹。

??三、二叉樹的遍歷

二叉樹的遍歷是指從根結(jié)點出發(fā)，按照某種次序依次訪問所有結(jié)點，使得每個結(jié)點被當(dāng)且訪問一次。共分為四種方式：

（一）前序遍歷（先序遍歷）

先序遍歷(PreOrder) 的操作過程如下：

1. 若二叉樹為空，則什么也不做，否則
2. 訪問根結(jié)點
3. 先序遍歷左子樹
4. 先序遍歷右子樹

上圖前序遍歷結(jié)果： 19 7 5 11 15 25 21 61

1.前序遍歷-遞歸實現(xiàn)：

/************************
* 采用遞歸方式實現(xiàn)前序遍歷
*************************/
void PreOrderRec(Btree *root) {
    if (root == NULL)
    {
    	return;
    }
    printf("- %d -", root->data);  //訪問根節(jié)點
    preOrderRec(root->lchild);     //遞歸遍歷左子樹
    preOrderRec(root->rchild);     //遞歸遍歷右子樹
}

2.前序遍歷-非遞歸方式實現(xiàn)：

1. 首先申請一個新的棧，記為 stack；
2. 將頭結(jié)點 head 壓入 stack 中；
3. 每次從 stack 中彈出棧頂節(jié)點，記為 cur，然后打印 cur 值，如果 cur 右孩子不為空，則將右孩子壓入棧中；如果 cur 的左孩子不為空，將其壓入 stack 中；
4. 重復(fù)步驟 3，直到 stack 為空.

/************************
* 借助棧實現(xiàn)前序遍歷
*************************/
void PreOrder(Btree *root) 	{
    Bnode cur ;
    if (root == NULL)
    {
    	return;
    }
    
    SqStack stack;
    InitStack(stack);
    PushStack(stack, *root); //頭節(jié)點先入棧
    
    while (!(IsEmpty(stack))) //棧為空，所有節(jié)點均已處理
    {
        PopStack(stack, cur); //要遍歷的節(jié)點
        printf("- %d -", cur.data);
        
        if (cur.rchild != NULL) {
        PushStack(stack, *(cur.rchild)); //右子節(jié)點先入棧，后處理
        }
        if (cur.lchild != NULL) {
        PushStack(stack, *(cur.lchild)); //左子節(jié)點后入棧，接下來先處理
        }
    }
    DestroyStack(stack);
}

（二）中序遍歷

中序遍歷( InOrder)的操作過程如下：

1. 若二叉樹為空，則什么也不做，否則
2. 中序遍歷左子樹
3. 訪問根結(jié)點
4. 中序遍歷右子樹

中序遍歷結(jié)果： 5 7 11 15 19 21 25 61

1.中序遍歷-遞歸實現(xiàn)：

void InOrder(BiTree root){
    if (root == NULL)
    {
    	return;
    }
    preOrderRec(root->lchild);  //遞歸遍歷左子樹
    printf("- %d -", root->data);  //訪問根結(jié)點
    preOrderRec(root->rchild);    //遞歸遍歷右子樹
}

2.中序遍歷-非遞歸方式實現(xiàn)：

1. 沿著根的左孩子，依次入棧，直到左孩子為空，說明已找到可以輸出的結(jié)點，
2. 棧頂元素出棧并訪問
3. 判斷棧頂元素若其右孩子為空，繼續(xù)執(zhí)行步驟2;若其右孩子不空,將右子樹轉(zhuǎn)執(zhí)行步驟1。

void InOrder2(BiTree T){
	InitStack(S);	//初始化棧S
	BiTree p = T;	//p是遍歷指針
	while(p || !IsEmpty(S)){	//棧不空或p不空時循環(huán)
		if(p){
			Push(S, p);	//當(dāng)前節(jié)點入棧
			p = p->lchild;	//左孩子不空，一直向左走
		}else{
			Pop(S, p);	//棧頂元素出棧
			visit(p);	//訪問出棧結(jié)點
			p = p->rchild;	//向右子樹走，p賦值為當(dāng)前結(jié)點的右孩子
		}
	}
}

（三）后序遍歷

后序遍歷(PostOrder) 的操作過程如下：

1. 若二叉樹為空，則什么也不做，否則
2. 后序遍歷左子樹
3. 后序遍歷右子樹
4. 訪問根結(jié)點

后序遍歷結(jié)果： 5 15 11 7 21 61 25 19

1.后序遍歷-遞歸實現(xiàn)：

void PostOrder(BiTree T){
	if (root == NULL)
    {
    	return;
    }
    preOrderRec(root->rchild);   //遞歸遍歷左子樹
    preOrderRec(root->lchild);   //遞歸遍歷右子樹
    printf("- %d -", root->data);
}

2.后序遍歷-非遞歸方式實現(xiàn)：

1. 在后序遍歷中，要保證左孩了和右孩子都已被訪問并且左孩子在右孩子前訪問才能訪問根結(jié)點，
2. 沿著根的左孩子，依次入棧，直到左孩子為空。
3. 讀棧頂元素:若其右孩子不空且未被訪問過，將右子樹轉(zhuǎn)執(zhí)行1否則，棧頂元素出棧并訪問。

void PostOrder2(BiTree T){
	InitStack(S);
	p = T;
	r = NULL;
	while(p || !IsEmpty(S)){
		if(p){	//走到最左邊
			push(S, p);
			p = p->lchild;
		}else{	//向右
			GetTop(S, p);	//讀棧頂元素（非出棧）
			//若右子樹存在，且未被訪問過
			if(p->rchild && p->rchild != r){
				p = p->rchild;	//轉(zhuǎn)向右
				push(S, p);	//壓入棧
				p = p->lchild;	//再走到最左
			}else{	//否則，彈出結(jié)點并訪問
				pop(S, p);	//將結(jié)點彈出
				visit(p->data);	//訪問該結(jié)點
				r = p;	//記錄最近訪問過的結(jié)點
				p = NULL;
			}
		}
	}
}

（四）層序遍歷

從根節(jié)點從上往下逐層遍歷，在同一層，按從左到右的順序?qū)?jié)點逐個訪問

上圖層序遍歷結(jié)果： 19 7 25 5 11 21 61 15

對應(yīng)的遞歸算法：

要進行層次遍歷，需要借助一個隊列。先將二叉樹根結(jié)點入隊，然后出隊，訪問出隊結(jié)點，若它有左子樹，則將左子樹根結(jié)點入隊;若它有右子樹，則將右子樹根結(jié)點入隊。然后出隊，訪問出隊結(jié)點…如此反復(fù)，直至隊列為空。
二叉樹的層次遍歷算法如下:

void LevelOrder(BiTree T){
	InitQueue(Q);	//初始化輔助隊列
	BiTree p;
	EnQueue(Q, T);	//將根節(jié)點入隊
	while(!IsEmpty(Q)){	//隊列不空則循環(huán)
		DeQueue(Q, p);	//隊頭結(jié)點出隊
		visit(p);	//訪問出隊結(jié)點
		if(p->lchild != NULL){
			EnQueue(Q, p->lchild);	//左子樹不空，則左子樹根節(jié)點入隊
		}
		if(p->rchild != NULL){
			EnQueue(Q, p->rchild);	//右子樹不空，則右子樹根節(jié)點入隊
		}
	}
}

??四、樹、森林與二叉樹的轉(zhuǎn)化

我們前面已經(jīng)講過樹的定義和存儲結(jié)構(gòu)，對于樹來說，在滿足樹的條件下可以是任意形狀，一個結(jié)點可以有任意多個孩子，顯然對樹的處理要復(fù)雜得多，我們前面也講了二叉樹，如果所有的樹都像二叉樹一樣方便就好了。

在講樹的存儲結(jié)構(gòu)時，我們提到了樹的孩子兄弟法可以將一棵樹用二叉鏈表進行存儲，所以借助二叉鏈表，樹和二叉樹可以相互進行轉(zhuǎn)換。從物理結(jié)構(gòu)來看，它們的二叉鏈表也是相同的，只是解釋不太一樣而已。 因此，只要我們設(shè)定一定的規(guī)則，用二叉樹來表示樹，甚至表示森林都是可以的，森林與二叉樹也可以互相進行轉(zhuǎn)換。

（一）樹轉(zhuǎn)換為二叉樹

步驟如下：

1. 加線。在所有兄弟結(jié)點之間加一條連線。
2. 去線。對樹中每個結(jié)點，只保留它與第一個孩子結(jié)點的連線，刪除它與其他孩子結(jié)點之間的連線。
3. 層次調(diào)整。以樹的根結(jié)點為軸心，將整棵樹順時針旋轉(zhuǎn)一定的角度，使之結(jié)構(gòu)層次分明。注意第一個孩子是二叉樹結(jié)點的左孩子，兄弟轉(zhuǎn)換過來的孩子是結(jié)點的右孩子。

如上圖：一棵樹經(jīng)過三個步驟轉(zhuǎn)換為一棵二叉樹。初學(xué)者容易犯的錯誤就是在層次調(diào)整時，弄錯了左右孩子的關(guān)系。比如圖中F、G本都是樹結(jié)點B的孩子，是結(jié)點E的兄弟，因此轉(zhuǎn)換后，F(xiàn)就是二叉樹結(jié)點E的右孩子，G是二叉樹結(jié)點F的右孩子。

（二）森林轉(zhuǎn)換為二叉樹

森林是由若干棵樹組成的，所以完全可以理解為,森林中的每一棵樹都是兄弟，可以按照兄弟的處理辦法來操作。
步驟如下：

1. 將森林中的每棵樹轉(zhuǎn)換成相應(yīng)的二叉樹;
2. 第一棵二叉樹不動，從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點作為前一棵二叉樹的根結(jié)點的右孩子，用線連接起來。當(dāng)所有的二叉樹連接起來后就得到了由森林轉(zhuǎn)換來的二叉樹。

??五、樹和森林的遍歷

（一）樹的遍歷

樹的遍歷是指用某種方式訪問樹中的每個結(jié)點，且僅訪問一次。主要有兩種方式:

1. 先根遍歷：先訪問樹的根結(jié)點，然后依次先根遍歷根的每棵子樹。遍歷子樹時仍遵循先根后子樹的規(guī)則。其遍歷序列與這棵樹相應(yīng)二叉樹的先序序列相同。

2. 后根遍歷：先依次后根遍歷每棵子樹，然后再訪問根結(jié)點。遍歷子樹時仍遵循先子樹后根的規(guī)則。其遍歷序列與這棵樹相應(yīng)二叉樹的中序序列相同。

下圖的樹的先根遍歷序列為ABEFCDG,后根遍歷序列為EFBCGDA。

另外，樹也有層次遍歷，與二叉樹的層次遍歷思想基本相同，即按層序依次訪問各結(jié)點。

（二）森林的遍歷

森林的遍歷也分為兩種方式:

1. 前序遍歷：先訪問森林中第一棵樹的根結(jié)點，然后再依次先根遍歷根的每棵子樹，再依次用同樣方式遍歷除去第一棵樹的剩余樹構(gòu)成的森林。
2. 后序遍歷：是先訪問森林中第一棵樹，后根遍歷的方式遍歷每棵子樹，然后再訪問根結(jié)點，再依次同樣方式遍歷除去第一棵樹的剩余樹構(gòu)成的森林。

下圖森林的前序遍歷序列為ABCDEFGHI，后序遍歷序列為BCDAFEHIG。

當(dāng)森林轉(zhuǎn)換成二叉樹時，其第一棵樹的子樹森林轉(zhuǎn)換成左子樹，剩余樹的森林轉(zhuǎn)換成右子樹，可知森林的先序和后序遍歷即為其對應(yīng)二叉樹的先序和中序遍歷。

??線索二叉樹

??一、線索二叉樹原理精講

回顧我們之前講的二叉鏈表：

• 首先，傳統(tǒng)的二叉鏈表存儲僅能體現(xiàn)一種父子關(guān)系，不能直接得到結(jié)點在遍歷中的前驅(qū)或后繼。

• 其次，觀察圖可以發(fā)現(xiàn)，指針域并不是充分的利用了，有許多的空指針的存在，比如18的Rchild。對于一個有n個結(jié)點的二叉鏈表，每個結(jié)點有指向左右孩子的兩個指針域，所以一共是2n個指針域。而n個結(jié)點的二叉樹一共有n-1 條分支線數(shù)，也就是說，其實是存在2n- (n-1) =n+1個空指針域。

  [外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-Mk0Xq6Ay-1690729766453)(E:\create\圖片\樹\21.png)]

由此設(shè)想能否利用這些空指針來存放指向其前驅(qū)或后繼的指針?這樣就可以像遍歷單鏈表那樣方便地遍歷二叉樹。引入線索二叉樹正是為了加快查找結(jié)點前驅(qū)和后繼的速度。

線索鏈表：我們把這種指向前驅(qū)和后繼的指針稱為線索，加上線索的二叉鏈表稱為線索鏈表，相應(yīng)的二叉樹就稱為線索二叉樹(Threaded Binary Tree)。

其結(jié)點結(jié)構(gòu)如下所示：

其中

• ltag為0時指向該結(jié)點的左孩子，為1時指向該結(jié)點的前驅(qū)。
• rtag為0時指向該結(jié)點的右孩子，為1時指向該結(jié)點的后繼。

于是我們可以將上面提到的二叉鏈表修改成如下的線索鏈表：

??二、線索二叉樹的結(jié)構(gòu)實現(xiàn)

二叉樹的線索存儲結(jié)構(gòu)代碼如下：

typedef struct ThreadNode{
	ElemType data;	//數(shù)據(jù)元素
	struct ThreadNode *lchild, *rchild;	//左、右孩子指針
	int ltag, rtag;	//左、右線索標(biāo)志
}ThreadNode, *ThreadTree;

??三、二叉樹的線索化

線索化的實質(zhì)就是將二叉鏈表中的空指針改為指向前驅(qū)或后繼的線索。由于前驅(qū)和后繼的信息只有在遍歷該二叉樹的時候才能得到，所以線索化的過程就是在遍歷的過程中修改空指針的過程。我們先以中序線索二叉樹的建立為例，還是繼續(xù)拿上面的二叉鏈表講解

（一）中序線索二叉樹

1.建立中序線索二叉樹

1. 在中序遍歷的過程中，P指向當(dāng)前結(jié)點，用一個pre指針記錄上一個訪問過的結(jié)點
2. 檢查當(dāng)前結(jié)點P的左孩子指針Lchild是否為空，若為空，將P的Ltag設(shè)為1，并將Lchild指向上一個結(jié)點pre
3. 同時檢查父結(jié)點pre的右指針Rchild是否為空，若為空，將pre的Rtag設(shè)為1，并將Rchild指向當(dāng)前結(jié)點P

中序遍歷對二叉樹線索化的遞歸算法:

struct Tree *pre = NULL;    //全局變量 
 
void InThread(struct  Tree  *p) {
    InThread(p->lchild);    //遞歸左子樹線索化
 
    if(!p->lchild)            //沒有左孩子
    {
        p->Ltag = 1;
        p->lchild = pre;    //本來指向左孩子的指針指向前驅(qū)結(jié)點 
    }
 
    if(pre != NULL && !pre->rchild)        //沒有右孩子
    {
        pre->Rtag = 1;
        pre->rchild = p;    //本來指向右孩子的指針指向后繼結(jié)點 
    }
 
    pre = p;    //保持pre指向p的前驅(qū)
 
    InThread(p->rchild);    //遞歸右子樹線索化
}

解釋：

1. 你會發(fā)現(xiàn)，除了中間的代碼，和二叉樹中序遍歷的遞歸代碼幾乎完全一樣。只不過將本是訪問結(jié)點的功能改成了線索化的功能。

2. if(!p->lchild)表示如果某結(jié)點的左指針域為空，因為其前驅(qū)結(jié)點剛剛訪問過（如果是第一個元素則前驅(qū)指向NULL），賦值給了 pre，所以可以將pre賦值給p->lchild,并修改p->L為1，以完成前驅(qū)結(jié)點的線索化。

   后繼結(jié)點的線索化就會麻煩一點。因為此時p結(jié)點的后繼結(jié)點還沒有被訪問到，因此只能對它的前驅(qū)結(jié)點pre的右指針rchild做判斷，if(!pre->rchild)表示如果為空，則p就為pre的后繼結(jié)點，于是就讓pre->rchild = p，并設(shè)置pre->R為1，以完成后繼結(jié)點的線索化。

3. 具體過程：

   • 從4開始，P指向4，prve = NULL，4的Lchild為空，4的Ltag設(shè)為1，同時指向前驅(qū)pre為NULL，因為此時4結(jié)點的后繼結(jié)點還沒有被訪問到，所以只能等下再處理4的Rchild
   • 然后pre指向4，p指向5，4的Rchild為空，5就為4的后繼結(jié)點，此時再處理4的Rchild指向5
   • pre指向5，p指向8，8的Lchild為空，8的Ltag設(shè)為1，同時指向前驅(qū)pre為5，8的Rchild為空，一樣等到12的時候再處理
   • pre指向8，p指向12，因為之前8的Rchild為空，8的Rchild指向12
   • pre指向12，p指向13，操作同上…

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-ShyD63Oe-1680510619306)(E:\create\圖片\樹\29.png)]

通過中序遍歷建立中序線索二叉樹的主過程算法如下：

void CreateInThread(ThreadTree T){
	ThreadTree pre = NULL;
	if(T != NULL){
		InThread(T, pre);	//線索化二叉樹
		pre->rchild = NULL;	//處理遍歷的最后一個結(jié)點
		pre->rtag = 1;
	}
}

但如上操作建立中序線索二叉樹，第一個結(jié)點的Lchild和最后一個結(jié)點的Rchild仍然指向NULL，為了方便,可以在二叉樹的線索鏈表上也添加一個頭結(jié)點，令其lchild域的指針指向二叉樹的根結(jié)點，其rchild域的指針指向中序遍歷時訪問的最后一個結(jié)點;令二叉樹中序序列中的第一個結(jié)點的lchild域指針和最后一個結(jié)點的rchild域指針均指向頭結(jié)點。這好比為二叉樹建立了一個雙向線索鏈表，方便從前往后或從后往前對線索二叉樹進行遍歷，如下圖所示。

2.遍歷中序線索二叉樹

/*T指向頭結(jié)點，頭結(jié)點左鏈lchild指向根結(jié)點，頭結(jié)點右鏈rchild指向中序遍
的最后一個結(jié)點。中序遍歷二叉線索鏈表表示的二叉樹T*/
void InOrderTraverse_Thr(BiThrTree T){
	BiThrTree p;
	p = T->lchild;	//p指向根結(jié)點
	//空樹或遍歷結(jié)束時，p==T（最后一個結(jié)點指向根結(jié)點）
	while(p != T){	
		//當(dāng)ltag==1時循環(huán)到中序序列第一個結(jié)點
		while(p->ltag == 0){	
			p = p->lchild;	//p指向p的左子樹
		}
		visit(p);	//訪問該結(jié)點
		//后繼線索為1且不是指向頭結(jié)點
		while(p->rtag == 1 && p->rchild != T){	
			p = p->rchild;	//p指向p的后繼
			visit(p);	//訪問該節(jié)點
		}
		//p進至其右子樹根，開始對右子樹根進行遍歷
		p = p->rchild;	
	}
}

從這段代碼也可以看出，它等于是一個鏈表的掃描,所以時間復(fù)雜度為0(n)。由于它充分利用了空指針域的空間(這等于節(jié)省了空間)，又保證了創(chuàng)建時的一次遍歷就可以終生受用前驅(qū)后繼的信息(這意味著節(jié)省了時間)。所以在實際問題中，如果所用的二叉樹需經(jīng)常遍歷或查找結(jié)點時需要某種遍歷序列中的前驅(qū)和后繼，那么采用線索二叉鏈表的存儲結(jié)構(gòu)就是非常不錯的選擇。

（二）先序和后序線索二叉樹

上面給出了建立中序線索二叉樹的代碼，建立先序線索二叉樹和后序線索二叉樹的代碼類似，只需變動線索化改造的代碼段與調(diào)用線索化左右子樹遞歸函數(shù)的位置。

以圖(a)的二叉樹為例，其先序序列為ABCDF，后序序列為CDBFA，可得出其先序和后序線索二叉樹分別如圖(b)和( c)所示：

如何在先序線索二叉樹中找結(jié)點的后繼：

如果有左孩子，則左孩子就是其后繼；如果無左孩子但有右孩子，則右孩子就是其后繼；如果為葉結(jié)點，則右鏈域直接指示了結(jié)點的后繼。

在后序線索二叉樹中找結(jié)點的后繼較為復(fù)雜，可分3種情況：

1. 若結(jié)點x是二叉樹的根，則其后繼為空;
2. 若結(jié)點x是其雙親的右孩子，或是其雙親的左孩子且其雙親沒有右子樹，則其后繼即為雙親;
3. 若結(jié)點x是其雙親的左孩子，且其雙親有右子樹，則其后繼為雙親的右子樹上按后序遍歷列出的第一個結(jié)點。圖( c)中找結(jié)點B的后繼無法通過鏈域找到，可見在后序線索二叉樹上找后繼時需知道結(jié)點雙親，即需采用帶標(biāo)志域的三叉鏈表作為存儲結(jié)構(gòu)。

??常用于查找數(shù)據(jù)的樹

樹這種數(shù)據(jù)結(jié)構(gòu)，經(jīng)常使用于查找數(shù)據(jù)的場合，而最常用的就是二叉排序樹與平衡二叉樹，以及多路查找樹

??二叉搜索樹與平衡二叉樹詳解

一、二叉搜索樹

（一）二叉搜索樹的原理精講

1. 當(dāng)我們要在一組數(shù)中要找到你女朋友（或未來女朋友）的年齡，比如 26？你該怎么找

答案： 從左至右 或 從右至左遍歷一次，找到這個數(shù)字

2. 當(dāng)我們把數(shù)據(jù)進行排序（按照從小到大的順序排列）后，再查找相應(yīng)的這條記錄？還是用上面的方法嗎？

答案：最快的方式，是采用折半法（俗稱二分查找）
?
思考：當(dāng)我們有新的數(shù)據(jù)加進來，或者刪除其中的一條記錄，為了保障查找的效率，我們?nèi)匀灰Ｕ蠑?shù)組有序，但是，會碰到我們講順序表時的問題，涉及到大量數(shù)據(jù)的移動！在插入和刪除操作上，就需要耗費大量的時間（需進行元素 的移位），能否有一種既可以使得插入和刪除效率不錯，又可高效查找的數(shù)據(jù)結(jié)構(gòu)和算法呢？
?
拋磚: 首先解決一個問題，插入時不移動元素，我們可以想到鏈表，但是要保證其有序的話，首先得遍歷鏈表尋找合適的位置，那么又如何高效的查找合適的位置呢，能否可以像二分一樣，通過一次比較排除一部分元素？
?
引玉： 那么我們可以用二叉樹的形式，以數(shù)據(jù)集第一個元素為根節(jié)點，之后將比根節(jié)點小的元素放在左子樹中，將比根節(jié) 點大的元素放在右子樹中，在左右子樹中同樣采取此規(guī)則。那么在查找 x 時，若 x 比根節(jié)點小可以排除右子樹所有元素， 去左子樹中查找（類似二分查找），這樣查找的效率非常好，而且插入的時間復(fù)雜度為 O（h），h 為樹的高度，較 O（n） 來說效率提高不少。故二叉搜索樹用作一些查找和插入使用頻率比較高的場景

二叉搜索樹（也稱二叉查找樹、二叉排序樹）或者是一棵空樹，或者是具有下列特性的二叉樹:

• 若左子樹非空，則左子樹上所有結(jié)點的值均小于根結(jié)點的值。
• 若右子樹非空，則右子樹上所有結(jié)點的值均大于根結(jié)點的值。
• 左、右子樹也分別是一棵二叉排序樹。

根據(jù)二叉排序樹的定義，左子樹結(jié)點值根據(jù)二叉排序樹的定義，左子樹結(jié)點值$<$根結(jié)點值$<$右子樹結(jié)點值，所以對二叉排序樹進行中序遍歷，可以得到一個遞增的有序序列。例如，下圖所示二叉排序樹的中序遍歷序列為 5 7 11 15 19 21 25 26 61 99。

（二）二叉搜索樹的算法實現(xiàn)

1.二叉搜索樹的結(jié)構(gòu)體定義

#define MAX_NODE 1024

#define isLess(a, b) (a<b)
#define isEqual(a, b) (a==b)

typedef int ElemType;
/*二叉樹的二叉鏈表結(jié)點結(jié)構(gòu)定義*/
typedef struct _Bnode{
    ElemType data; //元素類型
    struct _Bnode *lchild, *rchild;//指向左右孩子節(jié)點
}Bnode, *Btre

2.二叉搜索樹插入結(jié)點

將要插入的結(jié)點 e，與節(jié)點 root 節(jié)點進行比較，若小于則去到左子樹進行比較，若大于則去到右子樹進行比較，重復(fù)以上 操作直到找到一個空位置用于放置該新節(jié)點。

bool InsertBtree(Btree **root, Bnode *node){
    Bnode *tmp = NULL;
    Bnode *parent = NULL;
    
    if(!node){
    	return false;
    } else {//清空新節(jié)點的左右子樹
        node->lchild = NULL;
        node->rchild = NULL;
    }
    
    if(*root){//存在根節(jié)點
    	tmp= *root;
    }else{ //不存在根節(jié)點
        *root = node;
        return true;
    }
    
    while(tmp != NULL){
        parent = tmp;//保存父節(jié)點
        printf("父節(jié)點： %d\n", parent->data);
        if(isLess(node->data,tmp->data)){
        	tmp = tmp->lchild;
        }else{
        	tmp = tmp->rchild;
        }
    }
    
    //若該樹為空樹,則直接將 node 放置在根節(jié)點上
    if(isLess(node->data, parent->data)){//找到空位置后，進行插入
    	parent->lchild = node;
    }else{
    	parent->rchild = node;
    }
    
    return true;
}

3.二叉搜索樹刪除結(jié)點

將要刪除的節(jié)點的值，與節(jié)點 root 節(jié)點進行比較，若小于則去到左子樹進行比較，若大于則去到右子樹進行比較，重復(fù)以上操作直到找到一個節(jié)點的值等于刪除的值，則將此節(jié)點刪除。刪除時有 4 中情況須分別處理：

（1）刪除節(jié)點不存在左右子節(jié)點，即為葉子節(jié)點，直接刪除

（2）刪除節(jié)點存在左子節(jié)點，不存在右子節(jié)點，直接把左子節(jié)點替代刪除節(jié)點

（3）刪除節(jié)點存在右子節(jié)點，不存在左子節(jié)點，直接把右子節(jié)點替代刪除節(jié)點

（4）刪除節(jié)點存在左右子節(jié)點，則取左子樹上的最大節(jié)點或右子樹上的最小節(jié)點替換刪除節(jié)點

相關(guān)代碼如下：

/************************
* 查找二叉搜索樹上最大的結(jié)點
*************************/
int findMax(Btree* root)
{
    assert(root!=NULL);
    //方式一 采用遞歸
    /*if(root->rchild==NULL){
      	return root->data;
      }
    return findMax(root->rchild);
    */
    
    //方式二 采用循環(huán)
    while(root->rchild){
    	root = root->rchild;
    }
    	return root->data;
    }

//刪除結(jié)點
Btree* DeleteNode(Btree* root, int key) {
    if(root==NULL)return NULL;//沒有找到刪除節(jié)點
    
    if(root->data > key)
    {
        root->lchild = DeleteNode(root->lchild, key);
        return root;
    }
    if(root->data < key)
    {
        root->rchild = DeleteNode(root->rchild, key);
        return root;
    }
    
    //刪除節(jié)點不存在左右子節(jié)點，即為葉子節(jié)點，直接刪除
    if(root->lchild==NULL && root->rchild==NULL)return NULL;
    
    //刪除節(jié)點只存在右子節(jié)點，直接用右子節(jié)點取代刪除節(jié)點
    if(root->lchild==NULL && root->rchild!=NULL)return root->rchild;
    
    //刪除節(jié)點只存在左子節(jié)點，直接用左子節(jié)點取代刪除節(jié)點
    if(root->lchild!=NULL && root->rchild==NULL)return root->lchild;
    
    刪除節(jié)點存在左右子節(jié)點，直接用左子節(jié)點最大值取代刪除節(jié)點
    int val = findMax(root->lchild);
    root->data=val;
    root->lchild = DeleteNode(root->lchild,val);
    return root;
}

4.二叉搜索樹查找結(jié)點

/************************
* 采用遞歸方式查找結(jié)點
*************************/
Bnode* queryByRec(Btree *root, ElemType e){
    if (root == NULL || isEqual(root->data, e)){
    	return root;
    } else if(isLess(e, root->data)) {
    	return queryByRec(root->lchild, e);
    } else {
    	return queryByRec(root->rchild, e);
    }
}

/**
* 使用非遞歸方式查找結(jié)點
*/
Bnode* queryByLoop(Bnode *root, int e){
    while(root != NULL && !isEqual(root->data, e)){
        if(isLess(e, root->data)){
        	root = root->lchild;
        }else{
        	root = root->rchild;
        }
    }
    return root;
}

二、平衡二叉樹（AVL樹）

（一）平衡二叉樹原理精講

平衡二叉樹(Self-Balancing Binary Search Tree 或 Height-Balanced Binary Search Tree)：是一種特殊的二叉排序樹，其中每一個節(jié)點的左子樹和右子樹的高度差至多等于1。

它是一種高度平衡的二叉排序樹。它要么是一棵空樹， 要么它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對值不超過1。我們將二叉樹上結(jié)點的左子樹深度減去右子樹深度的值稱為平衡因子BF (Balance Factor) ， 那么平衡二叉樹上所有結(jié)點的平衡因子只可能是-1、0和1。只要二叉樹上有一個結(jié)點的平衡因子的絕對值大于1，則該二叉樹就是不平衡的。

（二）平衡二叉樹的相關(guān)算法實現(xiàn)

1.平衡二叉樹的查找

在平衡二叉樹上進行查找的過程與二叉排序樹的相同。因此，在查找過程中，與給定值進行比較的關(guān)鍵字個數(shù)不超過樹的深度。假設(shè)以n $n_h$表示深度為$h n 0 = 0 , n 1 = 1 , n 2 = 2 $并且有$n_h = n_{h ? 1} + n_{h ? 2}+ 1$ 可以證明，含有$n$個結(jié)點的平衡二叉樹的最大深度為$O(log2n)$，因此平衡二叉樹的平均查找長度為$O(log2n)$如下圖所示。

2.平衡二叉樹的插入

二叉排序樹保證平衡的基本思想如下：每當(dāng)在二叉排序樹中插入(或刪除)一個結(jié)點時，首先檢查其插入路徑上的結(jié)點是否因為此次操作而導(dǎo)致了不平衡。若導(dǎo)致了不平衡，則先找到插入路徑上離插入結(jié)點最近的平衡因子的絕對值大于1的結(jié)點A，再對以A為根的子樹，在保持二叉排序樹特性的前提下，調(diào)整各結(jié)點的位置關(guān)系，使之重新達到平衡。
注意:每次調(diào)整的對象都是最小不平衡子樹，即以插入路徑上離插入結(jié)點最近的平衡因子的絕對值大于1的結(jié)點作為根的子樹。下圖中的虛線框內(nèi)為最小不平衡子樹。

平衡二叉樹的插入過程的前半部分與二叉排序樹相同，但在新結(jié)點插入后，若造成查找路徑上的某個結(jié)點不再平衡，則需要做出相應(yīng)的調(diào)整。可將調(diào)整的規(guī)律歸納為下列4種情況：

1. LL平衡旋轉(zhuǎn)(右單旋轉(zhuǎn))。由于在結(jié)點A的左孩子(L)的左子樹(L)上插入了新結(jié)點，A的平衡因子由1增至2，導(dǎo)致以A為根的子樹失去平衡，需要一次向右的旋轉(zhuǎn)操作。將A的左孩子B向右上旋轉(zhuǎn)代替A成為根結(jié)點，將A結(jié)點向右下旋轉(zhuǎn)成為B的右子樹的根結(jié)點，而B的原右子樹則作為A結(jié)點的左子樹。
   如下圖所示，結(jié)點旁的數(shù)值代表結(jié)點的平衡因子，而用方塊表示相應(yīng)結(jié)點的子樹，下方數(shù)值代表該子樹的高度。

   

2. RR平衡旋轉(zhuǎn)(左單旋轉(zhuǎn))。由于在結(jié)點A的右孩子?的右子樹?上插入了 新結(jié)點，A的平衡因子由-1減至-2，導(dǎo)致以A為根的子樹失去平衡，需要一次向左的旋轉(zhuǎn)操作。將A的右孩子B向左上旋轉(zhuǎn)代替A成為根結(jié)點，將A結(jié)點向左下旋轉(zhuǎn)成為B的左子樹的根結(jié)點，而B的原左子樹則作為A結(jié)點的右子樹。

   

3. LR平衡旋轉(zhuǎn)(先左后右雙旋轉(zhuǎn))。由于在A的左孩子(L)的右子樹?上插入新結(jié)點，A的平衡因子由1增至2，導(dǎo)致以A為根的子樹失去平衡，需要進行兩次旋轉(zhuǎn)操作，先左旋轉(zhuǎn)后右旋轉(zhuǎn)。先將A結(jié)點的左孩子B的右子樹的根結(jié)點C向左上旋轉(zhuǎn)提升到B結(jié)點的位置（即進行一次RR平衡旋轉(zhuǎn)(左單旋轉(zhuǎn))），然后再把該C結(jié)點向右上旋轉(zhuǎn)提升到A結(jié)點的位置（即進行一次LL平衡旋轉(zhuǎn)(右單旋轉(zhuǎn))）。

   

4. RL平衡旋轉(zhuǎn)(先右后左雙旋轉(zhuǎn))。由于在A的右孩子?的左子樹(L)上插入新結(jié)點，A的平衡因子由-1減至-2，導(dǎo)致以A為根的子樹失去平衡，需要進行兩次旋轉(zhuǎn)操作，先右旋轉(zhuǎn)后左旋轉(zhuǎn)。先將A結(jié)點的右孩子B的左子樹的根結(jié)點C向右上旋轉(zhuǎn)提升到B結(jié)點的位置（即進行一次LL平衡旋轉(zhuǎn)(右單旋轉(zhuǎn))），然后再把該C結(jié)點向左上旋轉(zhuǎn)提升到A結(jié)點的位置（即進行一次RR平衡旋轉(zhuǎn)(左單旋轉(zhuǎn))）。

   

   注意: LR和RL旋轉(zhuǎn)時，新結(jié)點究竟是插入C的左子樹還是插入C的右子樹不影響旋轉(zhuǎn)過程，而上圖中是以插入C的左子樹中為例。

舉個例子：
假設(shè)關(guān)鍵字序列為15 , 3 , 7 , 10 , 9 , 8 {15,3, 7, 10, 9, 8}15,3,7,10,9,8，通過該序列生成平衡二叉樹的過程如下圖所示。

??多路查找樹

一、B樹

多路查找樹(muitl-way search tree)， 其每一個結(jié)點的孩子數(shù)可以多于兩個，且每一個結(jié)點處可以存儲多個元素。由于它是查找樹，所有元素之間存在某種特定的排序關(guān)系。
在這里，每一個結(jié)點可以存儲多少個元素，以及它的孩子數(shù)的多少是非常關(guān)鍵的。常見的有4種特殊形式：2-3樹、2-3-4樹、B樹和B+樹。這里主要介紹B樹和B+樹，因為2-3樹、2-3-4樹都是B樹的特例。
如下圖所示是一顆2-3樹：

1、定義

B樹，又稱多路平衡查找樹，B樹中所有結(jié)點的孩子個數(shù)的最大值稱為B樹的階，通常用m表示。一棵m階B樹或為空樹，或為滿足如下特性的m叉樹：

1. 樹中每個結(jié)點至多有m 棵子樹，即至多含有m ? 1個關(guān)鍵字。

2. 若根結(jié)點不是終端結(jié)點，則至少有兩棵子樹。

3. 除根結(jié)點外的所有非葉結(jié)點至少有? m / 2 ? 棵子樹，即至少含有? m / 2 ? ? 1個關(guān)鍵字。

4. 所有非葉結(jié)點的結(jié)構(gòu)如下：

   

   其中，K i ( i = 1 , 2 , . . . , n )為結(jié)點的關(guān)鍵字，且滿足K 1 < K 2 < . . . < K n ；P i ( i = 0 , 1 , . . . , n ) 為指向子樹根結(jié)點的指針，且指針$P_{i?1}$所指子樹中所有結(jié)點的關(guān)鍵字均小于Ki ， Pi 所指子樹中所有結(jié)點的關(guān)鍵字均大于Ki （即符合二叉排序樹的左小右大），n ( ? m / 2 ? ? 1 ≤ n ≤ m ? 1 ) 為結(jié)點中關(guān)鍵字的個數(shù)。

5. 所有的葉結(jié)點都出現(xiàn)在同一層次上，并且不帶信息(可以視為外部結(jié)點或類似于折半查找判定樹的查找失敗結(jié)點，實際上這些結(jié)點不存在，指向這些結(jié)點的指針為空)。

B樹是所有結(jié)點的平衡因子均等于0的多路平衡查找樹。
下圖所示的B樹中所有結(jié)點的最大孩子數(shù)m = 5，因此它是一棵5階B樹，在m mm階B樹中結(jié)點最多可以有m個孩子?？梢越柚搶嵗齺矸治錾鲜鲂再|(zhì)：

1. 結(jié)點的孩子個數(shù)等于該結(jié)點中關(guān)鍵字個數(shù)加1（每一個空隙都存在一個分支）。
2. 如果根結(jié)點沒有關(guān)鍵字就沒有子樹，此時B樹為空；如果根結(jié)點有關(guān)鍵字，則其子樹必然大于等于兩棵，因為子樹個數(shù)等于關(guān)鍵字個數(shù)加1。
3. 除根結(jié)點外的所有非終端結(jié)點至少有? m / 2 ? = ? 5 / 2 ? = 3棵子樹(即至少有? m / 2 ? ? 1 = ? 5 / 2 ? ? 1 = 2 個關(guān)鍵字)，至多有5棵子樹(即至多有4個關(guān)鍵字)。
4. 結(jié)點中關(guān)鍵字從左到右遞增有序，關(guān)鍵字兩側(cè)均有指向子樹的指針，左邊指針?biāo)缸訕涞乃嘘P(guān)鍵字均小于該關(guān)鍵字，右邊指針?biāo)缸訕涞乃嘘P(guān)鍵字均大于該關(guān)鍵字?；蛘呖闯上聦咏Y(jié)點關(guān)鍵字總是落在由上層結(jié)點關(guān)鍵字所劃分的區(qū)間內(nèi)，如第二層最左結(jié)點的關(guān)鍵字劃分成了3個區(qū)間：( ? ∞ , 5 ) , ( 5 , 11 ) , ( 11 , + ∞ ) ，該結(jié)點3個指針?biāo)缸訕涞年P(guān)鍵字均落在這3個區(qū)間內(nèi)。
5. 所有葉結(jié)點均在第4層，代表查找失敗的位置。

2、B樹與磁盤存取

B樹中的大部分操作所需的磁盤存取次數(shù)與B樹的高度成正比。

我們的外存，比如硬盤， 是將所有的信息分割成相等大小的頁面，每次硬盤讀寫的都是一個或多個完整的頁面，對于一個硬盤來說，一頁的長度可能是211到214個字節(jié)。
在一個典型的B樹應(yīng)用中，要處理的硬盤數(shù)據(jù)量很大，因此無法一次全部裝入內(nèi)存。因此我們會對B樹進行調(diào)整，使得B樹的階數(shù)(或結(jié)點的元素)與硬盤存儲的頁面大小相匹配。比如說一棵B樹的階為1001 (即1個結(jié)點包含1000個關(guān)鍵字)，高度為2，它可以儲存超過10億個關(guān)鍵字，我們只要讓根結(jié)點持久地保留在內(nèi)存中，那么在這棵樹上，尋找某一個關(guān)鍵字至多需要兩次硬盤的讀取即可。
通過這種方式，在有限內(nèi)存的情況下，每一次磁盤的訪問我們都可以獲得最大數(shù)量的數(shù)據(jù)。由于B樹每結(jié)點可以具有比二叉樹多得多的元素，所以與二叉樹的操作不同，它們減少了必須訪問結(jié)點和數(shù)據(jù)塊的數(shù)量，從而提高了性能。可以說，B樹的數(shù)據(jù)結(jié)構(gòu)就是為內(nèi)外存的數(shù)據(jù)交互準(zhǔn)備的。

3、B樹的查找

在B樹上進行查找與二叉查找樹很相似，只是每個結(jié)點都是多個關(guān)鍵字的有序表，在每個結(jié)點上所做的不是兩路分支決定，而是根據(jù)該結(jié)點的子樹所做的多路分支決定。
B樹的查找包含兩個基本操作：①在B樹中找結(jié)點；②在結(jié)點內(nèi)找關(guān)鍵字。由于B樹常存儲在磁盤上，因此前一個查找操作是在磁盤上進行的，而后一個查找操作是在內(nèi)存中進行的，即在找到目標(biāo)結(jié)點后，先將結(jié)點信息讀入內(nèi)存，然后在結(jié)點內(nèi)采用順序查找法或折半查找法。
在B樹上查找到某個結(jié)點后，先在有序表中進行查找，若找到則查找成功，否則按照對應(yīng)的指針信息到所指的子樹中去查找。

例如，在上圖中查找關(guān)鍵字42 ，首先從根結(jié)點開始，根結(jié)點只有一個關(guān)鍵字，且42 > 22 ，若存在，必在關(guān)鍵字22 的右邊子樹上，右孩子結(jié)點有兩個關(guān)鍵字，而36 < 42 < 45，則若存在，必在36和45中間的子樹上，在該子結(jié)點中查到關(guān)鍵字42，查找成功。若查找到葉結(jié)點時（對應(yīng)指針為空指針)，則說明樹中沒有對應(yīng)的關(guān)鍵字，查找失敗。

4、B樹的插入

與二叉查找樹的插入操作相比，B樹的插入操作要復(fù)雜得多。在二叉査找樹中，僅需査找到需插入的終端結(jié)點的位置。但是，在B樹中找到插入的位置后，并不能簡單地將其添加到終端結(jié)點中，因為此時可能會導(dǎo)致整棵樹不再滿足B樹定義中的要求。將關(guān)鍵字key插入B樹的過程如下：

1. 定位。利用前述的B樹査找算法，找出插入該關(guān)鍵字的最低層中的某個非葉結(jié)點(在B樹中查找key時,會找到表示查找失敗的葉結(jié)點,這樣就確定了最底層非葉結(jié)點的插入位置。注意：插入位置一定是最低層中的某個非葉結(jié)點)。
2. 插入。在B樹中，每個非失敗結(jié)點的關(guān)鍵字個數(shù)都在區(qū)間[ ? m / 2 ? ? 1 , m ? 1 ]內(nèi)。插入后的結(jié)點關(guān)鍵字個數(shù)小于m，可以直接插入；插入后檢查被插入結(jié)點內(nèi)關(guān)鍵字的個數(shù)，當(dāng)插入后的結(jié)點關(guān)鍵字個數(shù)大于m ? 1時，必須對結(jié)點進行分裂。

分裂的方法是：取一個新結(jié)點，在插入key后的原結(jié)點，從中間位置? m / 2 ?將其中的關(guān)鍵字分為兩部分，左部分包含的關(guān)鍵字放在原結(jié)點中，右部分包含的關(guān)鍵字放到新結(jié)點中，中間位置? m / 2 ?的結(jié)點插入原結(jié)點的父結(jié)點。若此時導(dǎo)致其父結(jié)點的關(guān)鍵字個數(shù)也超過了上限，則繼續(xù)進行這種分裂操作，直至這個過程傳到根結(jié)點為止,進而導(dǎo)致B樹高度增1。
對于m = 3的B樹，所有結(jié)點中最多有m ? 1 = 2 個關(guān)鍵字，若某結(jié)點中已有兩個關(guān)鍵字，則結(jié)點已滿，如下圖a所示。插入一個關(guān)鍵字60 后，結(jié)點內(nèi)的關(guān)鍵字個數(shù)超過了m ? 1，如圖b所示，此時必須進行結(jié)點分裂，分裂的結(jié)果如圖c所示。

通俗點講，B樹的插入，結(jié)點不溢出時好說，直接插入；如果結(jié)點溢出那就分裂，并把中間結(jié)點合并到父節(jié)點。

5、B樹的刪除

B樹中的刪除操作與插入操作類似，但要更復(fù)雜一些，即要使得刪除后的結(jié)點中的關(guān)鍵字個數(shù)≥ ? m / 2 ? ? 1，因此將涉及結(jié)點的“合并”問題。

1. 當(dāng)被刪關(guān)鍵字k不在終端結(jié)點(最低層非葉結(jié)點)中時，可以用k kk的前驅(qū)(或后繼) k ′來替替代k ，然后在相應(yīng)的結(jié)點中刪除k ′ ，關(guān)鍵字k ′必定落在某個終端結(jié)點中，則轉(zhuǎn)換成了被刪關(guān)鍵字在終端結(jié)點中的情形。在下圖的B樹中，刪除關(guān)鍵字80，用其前驅(qū)78替代，然后在終端結(jié)點中刪除78。因此只需討論刪除終端結(jié)點中關(guān)鍵字的情形。

   

2. 當(dāng)被刪關(guān)鍵字在終端結(jié)點(最低層非葉結(jié)點)中時，有下列三種情況:
   ① 直接刪除關(guān)鍵字。若被刪除關(guān)鍵字所在結(jié)點的關(guān)鍵字個數(shù)≥ ? m / 2 ?，表明刪除該關(guān)鍵字后仍滿足B樹的定義，則直接刪去該關(guān)鍵字。
   ② 兄弟夠借。若被刪除關(guān)鍵字所在結(jié)點刪除前的關(guān)鍵字個數(shù)= ? m / 2 ? ? 1 ，且與此結(jié)點相鄰的右(或左)兄弟結(jié)點的關(guān)鍵字個數(shù)≥ ? m / 2 ?，則需要調(diào)整該結(jié)點、右(或左)兄弟結(jié)點及其雙親結(jié)點(父子換位法)，以達到新的平衡。在圖(a)中刪除B樹的關(guān)鍵字65，右兄弟關(guān)鍵字個數(shù)≥ ? m / 2 ? = 2 ，將71取代原65的位置，將74調(diào)整到71的位置。

   

   ③ 兄弟不夠借。若被刪除關(guān)鍵字所在結(jié)點刪除前的關(guān)鍵字個數(shù)= ? m / 2 ? ? 1 ，且此時與該結(jié)點相鄰的左、右兄弟結(jié)點的關(guān)鍵字個數(shù)均= ? m / 2 ? ? 1 ，則將關(guān)鍵字刪除后與左(或右)兄弟結(jié)點及雙親結(jié)點中的關(guān)鍵字進行合并。在圖(b)中刪除B樹的關(guān)鍵字5 55，它及其右兄弟結(jié)點的關(guān)鍵字個數(shù)= ? m / 2 ? ? 1 = 1，故在5 刪除后將60合并到65 結(jié)點中。
   在合并過程中，雙親結(jié)點中的關(guān)鍵字個數(shù)會減1。若其雙親結(jié)點是根結(jié)點且關(guān)鍵字個數(shù)減少至0(根結(jié)點關(guān)鍵字個數(shù)為1時，有2棵子樹)，則直接將根結(jié)點刪除，合并后的新結(jié)點成為根；若雙親結(jié)點不是根結(jié)點，且關(guān)鍵字個數(shù)減少到? m / 2 ? ? 2 ，則又要與它自己的兄弟結(jié)點進行調(diào)整或合并操作，并重復(fù)上述步驟，直至符合B樹的要求為止。

其實通俗點講，B樹的刪除，刪除結(jié)點無非就是多留少補的情況，多留不必多說；少補復(fù)雜點：當(dāng)兄弟夠借時，就向左旋轉(zhuǎn)一次（即往左挪一個位置，重構(gòu)根節(jié)點關(guān)鍵字的前驅(qū)和后繼）；當(dāng)兄弟不夠借時就拆根節(jié)點，合并到兄弟結(jié)點，合并拆分要始終保證B樹平衡，理清了就很容易理解。

二、B+樹

盡管B樹的諸多好處，但其實它還是有缺陷的。對于樹結(jié)構(gòu)來說，我們都可以通過中序遍歷來順序查找樹中的元素，這一切都是在內(nèi)存中進行?？墒窃贐樹結(jié)構(gòu)中，我們往返于每個結(jié)點之間也就意味著，我們必須得在硬盤的頁面之間進行多次訪問。

如上圖所示。我們希望遍歷這棵B樹，假設(shè)每個結(jié)點都屬于硬盤的不同頁面，我們中序遍歷所有的元素：
$$頁面2\to 頁面1\to 頁面3\to 頁面1\to 頁面4\to 頁面1\to 頁面5$$
而且我們每次經(jīng)過結(jié)點遍歷時，都會對結(jié)點中的元素進行一次遍歷，這就非常糟糕。有沒有可能讓遍歷時每個元素只訪問一次呢?
B+樹來了。

1、定義

B+樹是應(yīng)文件系統(tǒng)（比如數(shù)據(jù)庫）所需而出現(xiàn)的一種B樹的變形樹。

m階的B+樹與m階的B樹的主要差異如下：

1. 有n棵子樹的結(jié)點中包含有n個關(guān)鍵字;
2. 所有的葉子結(jié)點包含全部關(guān)鍵字的信息，及指向含這些關(guān)鍵字記錄的指針，葉子結(jié)點本身依關(guān)鍵字的大小自小而大順序鏈接;
3. 所有分支結(jié)點可以看成是索引，結(jié)點中僅含有其子樹中的最大(或最小)關(guān)鍵字。
4. 在B+樹中，每個結(jié)點(非根內(nèi)部結(jié)點)的關(guān)鍵字個數(shù)n的范圍是? m / 2 ? ≤ n ≤ m(根結(jié)點：1 ≤ n ≤ m)；在B樹中，每個結(jié)點(非根內(nèi)部結(jié)點)的關(guān)鍵字個數(shù)n范圍是? m / 2 ? ? 1 ≤ n ≤ m ? 1 (根結(jié)點: 1 ≤ n ≤ m ? 1)。

下圖所示為一棵4階B+樹。

B+樹的結(jié)構(gòu)特別適合帶有范圍的查找。比如查找我們學(xué)校18~22歲的學(xué)生人數(shù)，我們可以通過從根結(jié)點出發(fā)找到第一個18歲的學(xué)生，然后再在葉子結(jié)點按順序查找到符合范圍的所有記錄。
B+樹的插入、刪除過程也都與B樹類似，只不過插入和刪除的元素都是在葉子結(jié)點上進行而已。

??哈夫曼樹

哈夫曼編碼

哈夫曼（Huffman）編碼算法是基于二叉樹構(gòu)建編碼壓縮結(jié)構(gòu)的，它是數(shù)據(jù)壓縮中經(jīng)典的一種算法。算法根據(jù)文本字符出現(xiàn)的頻率，重新對字符進行編碼。

首先請大家閱讀下面兩段中外小學(xué)作文：

中國 - 今天天氣晴朗，我和小明出去玩！小明貪玩，不小心摔了一跤，小明被摔得哇哇哭了，小明的爸爸聞聲趕來，又把小明痛扁了一陣。小明的小屁屁都被揍扁了，因為小明把媽媽剛買給他的褲子弄破了！

外國 - 今天天氣晴朗，我和喬伊·亞歷山大·比基·卡利斯勒·達夫·埃利奧特·?？怂埂ひ辆S魯莫·馬爾尼·梅爾斯·帕特森·湯普森·華萊士·普雷斯頓出去玩！喬伊·亞歷山大·比基·卡利斯勒·達夫·埃利奧特·?？怂埂ひ辆S魯莫·馬爾尼·梅爾斯·帕特森·湯普森·華萊士·普雷斯頓貪玩，不小心摔了一跤，喬伊·亞歷山大·比基·卡利斯勒·達夫·埃利奧特·?？怂埂ひ辆S魯莫·馬爾尼·梅爾斯·帕特森·湯普森·華萊士·普雷斯頓被摔得哇哇哭了，喬伊·亞歷山大·比基·卡利斯勒·達夫·埃利奧特·?？怂埂ひ辆S魯莫·馬爾尼·梅爾斯·帕特森·湯普森·華萊士·普雷斯頓的爸爸聞聲趕來，又把喬伊·亞歷山大·比基·卡利斯勒·達夫·埃利奧特·?？怂埂ひ辆S魯莫·馬爾尼·梅爾斯·帕特森·湯普森·華萊士·普雷斯頓痛扁了一陣。喬伊·亞歷山大·比基·卡利斯勒·達夫·埃利奧特·福克斯·伊維魯莫·馬爾尼·梅爾斯·帕特森·湯普森·華萊士·普雷斯頓的小屁屁都被揍扁了，因為喬伊·亞歷山大·比基·卡利斯勒·達夫·埃利奧特·?？怂埂ひ辆S魯莫·馬爾尼·梅爾斯·帕特森·湯普森·華萊士·普雷斯頓把媽媽剛買給他的褲子弄破了！

同一段內(nèi)容，當(dāng)小明換成了外國小朋友的名字，篇幅就增加了幾倍，有沒有辦法把內(nèi)容縮減呢？當(dāng)然有！在文章的開頭，先聲明一個縮寫：

那么，上面這段文字就可以縮成很小的一段：

今天天氣晴朗，我和喬頓出去玩！喬頓貪玩，不小心摔了一跤，喬頓被摔得哇哇哭了，喬頓的爸爸聞聲趕來，又把小明痛扁了一陣。喬頓的小屁屁都被揍扁了，因為喬頓把媽媽剛買給他的褲子弄破了！

哈夫曼編碼就是這樣一個原理！按照文本字符出現(xiàn)的頻率，出現(xiàn)次數(shù)越多的字符用越簡短的編碼替代，因為為了縮短編碼的長度，我們自然希望頻率越高的詞，編碼越短，這樣最終才能最大化壓縮存儲文本數(shù)據(jù)的空間。

哈夫曼編碼舉例： 假設(shè)要對“we will we will r u”進行壓縮。

壓縮前,使用 ASCII 碼保存:

共需： 19 個字節(jié) - 152 個位保存

下面我們先來統(tǒng)計這句話中每個字符出現(xiàn)的頻率。如下表，按頻率高低已排序：

接下來，我們按照字符出現(xiàn)的頻率，制定如下的編碼表：

這樣，“we will we will r u”就可以按如下的位來保存：

01 110 10 01 1111 00 00 10 01 110 10 01 1111 00 00 10 11101 10 11100

??紅黑樹

是每個節(jié)點都帶有顏色屬性（顏色為紅色或黑色）的自平衡二叉查找樹，滿足下列性質(zhì)：

• 節(jié)點是紅色或黑色；
• 根節(jié)點是黑色；
• 所有葉子節(jié)點都是黑色；
• 每個紅色節(jié)點必須有兩個黑色的子節(jié)點。(從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點。)
• 從任一節(jié)點到其每個葉子的所有簡單路徑都包含相同數(shù)目的黑色節(jié)點。

??堆

??一、堆的原理精講

?（一）堆的概念

堆（Heap）：一種有特殊用途的數(shù)據(jù)結(jié)構(gòu)——用來在一組變化頻繁（發(fā)生增刪查改的頻率較高）的數(shù)據(jù)集中查找最值

• 堆中某個節(jié)點的值總是不大于或不小于其父節(jié)點的值;
• 堆總是一棵完全二叉樹。
• 每個節(jié)點最多可以有兩個節(jié)點
• 根結(jié)點的鍵值是所有堆結(jié)點鍵值中最大（小）者，且每個結(jié)點的值都比其孩子的值大（?。?，這樣的堆叫最大（?。┒?/li>
• 除了根節(jié)點沒有兄弟節(jié)點，最后一個左子節(jié)點可以沒有兄弟節(jié)點，其他節(jié)點必須有兄弟節(jié)點
• 這里需要注意的是：在多個子樹中，并不是說其中一個子樹的父結(jié)點一定大于另一個子樹的兒子結(jié)點。

實際上，先弄懂樹這種數(shù)據(jù)結(jié)構(gòu)再來看堆就會簡單很多了，堆是你見過的最有個性的樹！它是用數(shù)組表示的樹。所以邏輯結(jié)構(gòu)上其實是一棵樹，物理結(jié)構(gòu)上是一維數(shù)組，屬于非線性結(jié)構(gòu)

本篇博客默認你沒有事先學(xué)過樹，通俗易懂，講解知識詳細，即使不知道完全二叉樹，也能辨認出堆，即使沒學(xué)過樹也能搞懂堆，本篇以最大堆進行講解

?（二）看圖識最大堆

圖1：因為93 > 87，而且82無左子節(jié)點卻有右子節(jié)點，不滿足除了根節(jié)點和最后一個左子節(jié)點可以沒有兄弟節(jié)點，其他節(jié)點必須要有兄弟節(jié)點的規(guī)定，所以圖1不是堆

圖2：82是最后一個左子節(jié)點，但92不是，而且沒有兄弟節(jié)點，所以圖2也不是堆

圖3：滿足條件，為最大堆

?（三）詳解堆是用數(shù)組表示的樹

i為下標(biāo)，由上圖我們能看出規(guī)律：

• i的左子節(jié)點：2i+1
• i的右子節(jié)點：2i+2
• i的父節(jié)點：(i-1)/2

這也就是我們在代碼實現(xiàn)的時候需要注意的地方

??二、堆的向下調(diào)整算法

向下調(diào)整：是讓調(diào)整的結(jié)點與其孩子節(jié)點進行比較，若想將其調(diào)整為小堆，那么根結(jié)點的左右子樹必須都為小堆，
若想將其調(diào)整為大堆，那么根結(jié)點的左右子樹必須都為大堆，有些文章說單純滿足為堆就行這種說法是不對的

向下調(diào)整算法的基本思想（大部分搜到的都是以最小堆為例，我就繼續(xù)以最大堆為例了）：

1. 從根結(jié)點處開始，選出左右孩子中值較大的孩子。
2. 讓大的孩子與其父親進行比較。
3. 若大的孩子比父親還大，則該孩子與其父親的位置進行交換。并將原來大的孩子的位置當(dāng)成父親繼續(xù)向下進行調(diào)整，直到調(diào)整到葉子結(jié)點為止。
4. 若大的孩子比父親小，則不需處理了，調(diào)整完成，整個樹已經(jīng)是大堆了。

代碼實現(xiàn)：

/*向下調(diào)整將當(dāng)前的節(jié)點和子節(jié)點調(diào)整成最大堆*/
void adjustDown(Heap &heap, int index) { 
    int cur=heap.arr[index];//當(dāng)前待調(diào)整的節(jié)點
	int parent,child;
/*判斷否存在大于當(dāng)前節(jié)點子節(jié)點，如果不存在 ，則堆本身是平衡的，不需要調(diào)整；如果存在，則將最大的子節(jié)點與之交換，交換后，如果這個子節(jié)點還有子節(jié)點，則要繼續(xù)按照同樣的步驟對這個子節(jié)點進行調(diào)整*/
	for(parent=index; (parent*2+1)<heap.size; parent=child) {
        child=parent*2+1;
        
        //取兩個子節(jié)點中的最大的節(jié)點
        
        if(((child+1)<heap.size)&&(heap.arr[child]<heap.arr[child+1])) {
        	child++;
		}
        
            //判斷最大的節(jié)點是否大于當(dāng)前的父節(jié)點
         if(cur>=heap.arr[child]) {//不大于，則不需要調(diào)整，跳出循環(huán)
             break;
         }else {//大于當(dāng)前的父節(jié)點，進行交換，然后從子節(jié)點位置繼續(xù)向下調(diào)整
             heap.arr[parent]=heap.arr[child];
             heap.arr[child]=cur;
         }
    }
}

??三、堆的向上調(diào)整算法

向上調(diào)整：是讓調(diào)整的結(jié)點與其父親結(jié)點進行比較，當(dāng)我們已經(jīng)有一個堆，我們需要在堆的末尾插入數(shù)據(jù)，再對其進行調(diào)整，使其任然保持堆的結(jié)構(gòu)，這里我們就需要用到堆的向上調(diào)整算法

向上調(diào)整算法的基本思想：

1. 將目標(biāo)結(jié)點與其父結(jié)點比較
2. 若目標(biāo)結(jié)點的值比其父結(jié)點的值大，則交換目標(biāo)結(jié)點與其父結(jié)點的位置
3. 將原目標(biāo)結(jié)點的父結(jié)點當(dāng)作新的目標(biāo)結(jié)點繼續(xù)進行向上調(diào)整。若目標(biāo)結(jié)點的值比其父結(jié)點的值大，則停止向上調(diào)整，此時該樹已經(jīng)是大堆了。

代碼實現(xiàn)：

/*將當(dāng)前的節(jié)點和父節(jié)點調(diào)整成最大堆*/
void adjustUp(Heap &heap, int index) {
    if(index<0 || index >= heap.size) {//大于堆的最大值直接 return
    	return;
    }

    while(index>0){	
        int temp = heap.arr[index];
        int parent = (index - 1) / 2;
        
        if(parent >= 0){//如果索引沒有出界就執(zhí)行想要的操作
        	if(temp > heap.arr[parent]){
                heap.arr[index] = heap.arr[parent];
                heap.arr[parent] = temp;
                index = parent;
        	} else {//如果已經(jīng)比父親小 直接結(jié)束循環(huán)
        		break;
        	}
        } else {//越界結(jié)束循環(huán)
        	break;
        }
    }
}

??四、將任意一棵樹建成堆

前面我們已經(jīng)知道，堆的向下調(diào)整算法是在基于根節(jié)點左右子樹已經(jīng)為最大堆或最小堆的前提下才能操作的；而堆的向上調(diào)整算法是在我們已經(jīng)建好了一個最大堆或最小堆，用于插入元素后的調(diào)整

那么如何將任意一棵樹建成最大（?。┒涯?，這里我就改為：如何在數(shù)組中快速創(chuàng)建堆：

我們把向下調(diào)整算法倒著來，我們知道，滿足堆，必須左右子樹都是大堆或者小堆，我們可以利用這個思想，從下往上倒著走，從第一個非葉子節(jié)點開始，通過數(shù)組下標(biāo)的控制，把它當(dāng)做根去向下調(diào)整，依次往上，直到把當(dāng)前路徑調(diào)整成符合條件的大堆或者小堆即可

還是以最大堆為例講解，可以看到，根節(jié)點右子樹不是一個最大堆，所以不能直接用向下調(diào)整算法

1. 首先我們需要找到最后一個結(jié)點的父結(jié)點如圖（a），我們找到的結(jié)點是 87，然后找出該結(jié)點的最大子節(jié)點與自己比較，若該子節(jié)點比自身大，則將兩個結(jié)點交換.。圖(a)中，87 比左子節(jié)點 95 小,則交換之.如圖（b）所示

2. 我們移動到前一個父結(jié)點 93,如圖?所示。同理做第一步的比較操作,結(jié)果不需要交換

3. 繼續(xù)移動結(jié)點到前一個父結(jié)點 82，82 小于右子節(jié)點 95，則 82 與 95 交換，如圖(d)所示，82 交換后，其值小于左子節(jié)點，不符合最大堆的特點，故需要繼續(xù)向下調(diào)整，如圖(e)所示

4. 所有節(jié)點交換完畢,最大堆構(gòu)建完成

?

??五、堆的算法實現(xiàn)

1.堆的結(jié)構(gòu)體定義

#define DEFAULT_CAPCITY 128

typedef struct _Heap{
    int *arr; //存儲堆元素的數(shù)組
    int size; //當(dāng)前已存儲的元素個數(shù)
    int capacity; //當(dāng)前存儲的容量
}Heap;

2.初始化堆

/*初始化堆*/
bool initHeap(Heap &heap, int *orginal, int size){
    //orginal：原數(shù)據(jù)  size：數(shù)據(jù)個數(shù)  heap：堆
    int capacity = DEFAULT_CAPCITY>size? DEFAULT_CAPCITY:size;
    
    heap.arr = new int[capacity];   //分配堆中數(shù)組空間
    if(!heap.arr) return false;
    
    heap.capacity = capacity;
    heap.size = 0;
    
    //如果存在原始數(shù)據(jù)則構(gòu)建堆
    if(size>0){
        memcpy(heap.arr, orginal, size*sizeof(int));
        heap.size = size;
        buildHeap(heap);
    } else {
    	heap.size = 0;
    }
return true;
}


/* 從最后一個父節(jié)點(size/2-1 的位置)逐個往前調(diào)整所有父節(jié)點（直到根節(jié)點）,確保每一個父節(jié)點都是一個最大堆，最后整體上形成一個最大堆 */
void buildHeap(Heap &heap){
    int i;
    for(i=heap.size/2-1; i>=0; i--){
    	adjustDown(heap, i);
    }
}

解釋：

1. 初始化堆操作即為之前講的將任意一棵樹建成堆
2. orginal為函數(shù)外傳入的原數(shù)據(jù)，然后通過初始化將其建成堆
3. buildHeap即為以最后一個非葉子節(jié)點開始的向下調(diào)整算法

3.判斷堆是否為空

/*判斷堆是否為空*/
bool isEmpty(Heap &heap){
	if(heap.size<1) return true;
		return false;
}

4.插入新元素

/*最大堆尾部插入節(jié)點，同時保證最大堆的特性*/
bool insert(Heap &heap, int value) {
	if (heap.size == heap.capacity) {
		fprintf(stderr, "?？臻g耗盡！\n");
		return false;
	}
	
    int index = heap.size;
    heap.arr[heap.size++] = value;
    adjustUp(heap, index);
    return true;
}

5.堆頂元素出列（刪除元素），同時獲取堆頂數(shù)據(jù)

如果我們將堆頂?shù)脑貏h除，那么頂部有一個空的節(jié)點，怎么處理？

我們先將堆頂?shù)臄?shù)據(jù)與最后一個數(shù)據(jù)交換位置，刪除最后一個結(jié)點，然后再修復(fù)堆屬性。

原因：我們?nèi)羰侵苯觿h除堆頂?shù)臄?shù)據(jù)，那么原堆后面數(shù)據(jù)的父子關(guān)系就全部打亂了，需要全體重新建堆，時間復(fù)雜度為O（N）。若是用上述方法，那么只需要對堆進行一次向下調(diào)整即可，因為此時根結(jié)點的左右子樹都是大堆，我們只需要在根結(jié)點處進行一次向下調(diào)整即可，時間復(fù)雜度為O ( log ? ( N ) ）

代碼實現(xiàn)：

/* 刪除堆頂元素，獲取堆頂?shù)臄?shù)據(jù)*/
bool pop(PriorityQueue &pq, DataType &value) {
    
    if (isEmpty(pq)) return false;
    
    value = pq.arr[0];
    pq.arr[0] = pq.arr[--pq.size];
    //heap.arr[0] = heap.arr[heap.size-1];
    //heap.size--;
    adjustDown(pq, 0);// 向下執(zhí)行堆調(diào)整
    return true;
}

6.遍歷打印堆

打印堆中的數(shù)據(jù)，這里用了兩種打印格式。第一種打印格式是按照堆的物理結(jié)構(gòu)進行打印，即打印為一排連續(xù)的數(shù)字。第二種打印格式是按照堆的邏輯結(jié)構(gòu)進行打印，即打印成樹形結(jié)構(gòu)。

//求結(jié)點數(shù)為n的二叉樹的深度
int depth(int n) {
	assert(n >= 0);

	if (n>0) {
		int m = 2;
		int hight = 1;
		while (m < n + 1) {
			m *= 2;
			hight++;
		}
		return hight;
	} else {
		return 0;
	}
}

//打印堆
void HeapPrint(Heap* php) {
	assert(php);
	//按照物理結(jié)構(gòu)進行打印
	int i = 0;
	for (i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
	//按照樹形結(jié)構(gòu)進行打印
	int h = depth(php->size);
	int N = (int)pow(2, h) - 1;//與該二叉樹深度相同的滿二叉樹的結(jié)點總數(shù)
	int space = N - 1;//記錄每一行前面的空格數(shù)
	int row = 1;//當(dāng)前打印的行數(shù)
	int pos = 0;//待打印數(shù)據(jù)的下標(biāo)
	while (1) {
		//打印前面的空格
		int i = 0;
		for (i = 0; i < space; i++) {
			printf(" ");
		}
		//打印數(shù)據(jù)和間距
		int count = (int)pow(2, row - 1);//每一行的數(shù)字個數(shù)
		while (count--)//打印一行
		{
			printf("%02d", php->a[pos++]);//打印數(shù)據(jù)
			if (pos >= php->size)//數(shù)據(jù)打印完畢
			{
				printf("\n");
				return;
			}
			int distance = (space + 1) * 2;//兩個數(shù)之間的空格數(shù)
			while (distance--)//打印兩個數(shù)之間的空格
			{
				printf(" ");
			}
		}
		printf("\n");
		row++;
		space = space / 2 - 1;
	}
}

7.銷毀堆

/*銷毀堆*/
void destroy(Heap &heap){
    if(heap.arr) delete[] heap.arr;
   
    heap->arr = NULL;//及時置空
    heap->size = 0;//元素個數(shù)置0
    heap->capacity = 0;//容量置0  
}

?

??六、拓展

?（一）用最大堆或最小堆來實現(xiàn)優(yōu)先隊列

操作系統(tǒng)內(nèi)核作業(yè)調(diào)度是優(yōu)先隊列的一個應(yīng)用實例，它根據(jù)優(yōu)先級的高低而不是先到先服務(wù)的方式來進行調(diào)度；

如果最小鍵值元素擁有最高的優(yōu)先級，那么這種優(yōu)先隊列叫作升序優(yōu)先隊列（即總是先刪除最小的元素），類似的，如果最大鍵值元素擁有最高的優(yōu)先級，那么這種優(yōu)先隊列叫作降序優(yōu)先隊列（即總是先刪除最大的元素）；由于這兩種類型是完全對稱的，所以只需要關(guān)注其中一種，如升序優(yōu)先隊列

?（二）堆排序算法

堆排序(Heapsort)是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法，它是選擇排序的一種?？梢岳脭?shù)組的特點快速定位指定索引的元素.

(選擇排序工作原理 - 第一次從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個元素，存放在序列的起始位置，然后再從剩余的未排序元素中尋找到最?。ù螅┰?，然后放到已排序的序列的末尾。以此類推，直到全部待排序的數(shù)據(jù)元素的個數(shù)為零)

/* 實現(xiàn)堆排序 */
void heapSort(Heap &heap){
    if (heap.size<1) return ;
    
    while(heap.size>0){
        int tmp = heap.arr[0];
        heap.arr[0] = heap.arr[heap.size-1];
        heap.arr[heap.size-1] = tmp;
        
        heap.size--;
        adjustDown(heap, 0);// 向下執(zhí)行堆調(diào)整
    }
}

?（三）top - k問題

若要從N個數(shù)字中取得最小的K個數(shù)字，則需要創(chuàng)建大小為K的大堆來獲取。若要從N個數(shù)字中取得最大的K個數(shù)字，則需要創(chuàng)建大小為K的小堆來獲取。

拜托，面試別再問我TopK了?。。架構(gòu)師之路-CSDN博客

總結(jié)參考資料:

程杰:大話數(shù)據(jù)結(jié)構(gòu)

嚴蔚敏:數(shù)據(jù)結(jié)構(gòu)C語言版

數(shù)據(jù)結(jié)構(gòu)：線性表(List)【詳解】
（排版結(jié)構(gòu)等都借鑒了此位前輩的博客，對我的學(xué)習(xí)總結(jié)起到了很大的幫助）文章來源地址http://www.zghlxwxcb.cn/news/detail-401955.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)篇】-樹（共計兩萬字，你真的搞懂了它嗎）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！