1．6樹與二叉樹
一、樹的基本概念
在樹結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱為父結(jié)點(diǎn)，沒有前件的結(jié)點(diǎn)只有一個(gè)，稱為樹的根結(jié)點(diǎn)，簡(jiǎn)稱為樹的根。
在樹結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件，它們都稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。
在樹結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后件個(gè)數(shù)稱為該結(jié)點(diǎn)的度。
葉子結(jié)點(diǎn)的度為0。
樹的層次稱為樹的深度。
在一個(gè)算術(shù)表達(dá)式中，有運(yùn)算符和運(yùn)算對(duì)象。一個(gè)運(yùn)算符可以有若干個(gè)運(yùn)算對(duì)象。例職，取正（+）等只有一個(gè)運(yùn)算對(duì)象，稱為單目運(yùn)算符；二個(gè)運(yùn)算對(duì)象稱為雙目運(yùn)算符，三目運(yùn)算符。
用樹來表示算術(shù)表達(dá)式的原則如下：
表達(dá)式中的每一個(gè)運(yùn)算符在樹中對(duì)應(yīng)一個(gè)結(jié)點(diǎn)，稱為運(yùn)算符結(jié)點(diǎn)。
運(yùn)算符的每一個(gè)運(yùn)算對(duì)象在樹中為該運(yùn)算符結(jié)點(diǎn)的子樹（在樹中的順序?yàn)閺淖蟮接遥?BR> 運(yùn)算對(duì)象中的單變量均為葉子結(jié)點(diǎn)。
二、二叉樹及其基本性質(zhì)
1、什么是二叉樹
二叉樹是一種很有用的非線性結(jié)構(gòu)。二就樹具有以下兩個(gè)特點(diǎn)：
非空二叉樹只有一個(gè)根結(jié)點(diǎn)；
每一個(gè)結(jié)點(diǎn)最多有兩棵子樹，且分別稱為該結(jié)點(diǎn)的左子樹與右子樹。
由以上特點(diǎn)可以看出，在二叉樹中，每一個(gè)結(jié)點(diǎn)的度為2，即所有子樹（左子樹或右子樹）也均為二叉樹，而樹結(jié)構(gòu)中的每一個(gè)結(jié)點(diǎn)的度可以是任意的。另外，二叉樹中的每一個(gè)結(jié)點(diǎn)的子樹被明顯地分為左子樹與右子樹?？梢詻]有其中的一個(gè)，也可以全沒有。
二叉樹的基本性質(zhì)
性質(zhì)1：在二叉樹的第K層上，最多有（K≥1）個(gè)結(jié)點(diǎn)。
性質(zhì)2：濃度為M的二叉樹最多有2m-1 個(gè)結(jié)點(diǎn)。
深度為m 的二叉樹是指二叉樹共有m層。
性質(zhì)3：在任意一棵二叉樹中度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個(gè)。
性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的二叉樹，其深度至少為[ log2n]+1,其中[ log2n]表示取的整數(shù)部分。
滿二叉樹與完全二叉樹
滿二叉樹與完全二叉樹是兩種特殊形態(tài)的二叉樹。
滿二叉樹
所謂滿二叉樹是指這樣的一種二叉樹；除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。這就是說，在滿二叉樹中，每一層上的結(jié)點(diǎn)數(shù)都達(dá)到值，即在滿二叉樹的第K層上有2K-1個(gè)結(jié)點(diǎn)，且深度為m的滿二叉樹有2m-1個(gè)結(jié)點(diǎn)。
完全二叉樹
所謂完全二叉樹是指這樣的二叉樹，除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)的值；在最后一層上只缺少右邊的若干結(jié)點(diǎn)。
列確切地說，如果從根結(jié)點(diǎn)起，對(duì)二叉樹的結(jié)點(diǎn)自上而下、自左至右用自然數(shù)進(jìn)行邊疆編號(hào)，則深度為m、且有n 個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為m的滿二叉樹中編號(hào)從1到n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱之為完全二叉樹。
對(duì)于完全二叉樹來說，葉子結(jié)點(diǎn)只可能在層次的兩層上出現(xiàn)；對(duì)于任何一個(gè)結(jié)點(diǎn)，若其右分支下的子孫結(jié)點(diǎn)的層次為p，則其左分支下的子孫結(jié)點(diǎn)的層次或?yàn)閜，或?yàn)閜+1。
由滿二叉樹與完全二叉樹的特點(diǎn)可以看出，滿二叉樹也是完全二叉樹，而完全二叉樹一般不是滿二叉樹。
完全二叉樹還具有以下兩個(gè)性質(zhì)：
性質(zhì)5：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為[ log2n]+1。
性質(zhì)6：設(shè)完全二叉樹共有n個(gè)結(jié)點(diǎn)。如果從根結(jié)點(diǎn)開始，按層序（每一層從左到右）用自然數(shù)1，2，…，n給結(jié)點(diǎn)進(jìn)行編號(hào)，則對(duì)于編號(hào)為k （k=1,2,…n）的結(jié)點(diǎn)有以下結(jié)論：
若k=1，則該結(jié)點(diǎn)為根結(jié)點(diǎn)，它沒有父結(jié)點(diǎn)；若k>1，則該結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為INT(k/2)。
若2k≤n，則編號(hào)為k 的結(jié)點(diǎn)的左子結(jié)點(diǎn)編號(hào)為2k ；否則該結(jié)點(diǎn)無左子結(jié)點(diǎn)（顯然也沒有右子結(jié)點(diǎn)）。
若2k+1≤n，則編號(hào)為k 的結(jié)點(diǎn)的右子結(jié)點(diǎn)編號(hào)為2k+1；否則該結(jié)點(diǎn)無右子結(jié)點(diǎn)。
三、二叉樹的存儲(chǔ)結(jié)構(gòu)
二叉樹的遍歷
二叉樹的遍歷是指不重復(fù)地訪問二叉樹的所有結(jié)點(diǎn)。
在遍歷二叉樹的過程中，一般先遍歷左子樹，然后再遍歷右子樹。
1、前序遍歷（DLR）
所謂前序遍歷是指在訪問根結(jié)點(diǎn)、遍歷左子樹與遍歷右子樹這三者中，首先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹；并且，在遍歷左、右子樹時(shí)，仍然先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹。F，C，A，D，B，E，G，H，P
2、中序遍歷（LDR）
所謂中序遍歷是指在訪問根結(jié)點(diǎn)、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹；并且，在遍歷左、右子樹時(shí)，仍然先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹。A，C，B，D，F(xiàn)，E，H，G，P
3、后序遍歷（LRD）
所謂中序遍歷是指在訪問根結(jié)點(diǎn)、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點(diǎn)；并且，在遍歷左、右子樹時(shí)，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點(diǎn)。A，B，D，C，H，P，G，E，F(xiàn)
1.7查找技術(shù)
一、順序查找
順序查找又稱順序搜索。順序查找一般是指在線性表中查找指定的元素，其基本方法如下：從線性表的第一個(gè)元素開始，依次將線性表中的元素與被查元素進(jìn)行比較，若相等則表示找到（即查找成功）；若線性表中所有的元素都與被查元素進(jìn)行了比較但都不相等，則表示線性表中沒有要找的元素（即查找失敗）。
順序查找的效率是很低的。以下兩種情況只能采用順序查找：
如果線性表無序表（即表中元素的排列是無序的），則不管是順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，都只能用順序查找。
即使是有序線性表，如果采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，也只能用順序查找。
二、二分法查找
二分法查找只適用于存儲(chǔ)的有序表。在此所說的有序表是指線性表的中元素按值非遞減排列（即從小到大，但允許相鄰元素值相等）。
設(shè)有序線性表的長度為n，被查元素為x，則對(duì)分查找的方法如下：
將x與線性表的中間項(xiàng)進(jìn)行比較：
若中間項(xiàng)的值等于x，則說明查到，查找結(jié)束；
若x小于中間項(xiàng)的值，則在線性表的前半部分（即中間項(xiàng)以前的部分）以相同的方法進(jìn)行查找；
若x大于中間項(xiàng)的值，則在線性表的后半部分（即中間項(xiàng)以后的部分）以相同的方法進(jìn)行查找。
這個(gè)過程一直進(jìn)行到查找成功或子表長度為0（說明線性表中沒有這個(gè)元素）為止。
顯然，當(dāng)有序線性表為順序存儲(chǔ)時(shí)才能采用二分查找，并且，二分查找的效率要比順序查找高得多?？梢宰C明，對(duì)于長度為n的有序線性表，在最壞情況下，二分查找只需要比較log2n次，而順序查找需要比較n次。
一、樹的基本概念
在樹結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱為父結(jié)點(diǎn)，沒有前件的結(jié)點(diǎn)只有一個(gè)，稱為樹的根結(jié)點(diǎn)，簡(jiǎn)稱為樹的根。
在樹結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件，它們都稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。
在樹結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后件個(gè)數(shù)稱為該結(jié)點(diǎn)的度。
葉子結(jié)點(diǎn)的度為0。
樹的層次稱為樹的深度。
在一個(gè)算術(shù)表達(dá)式中，有運(yùn)算符和運(yùn)算對(duì)象。一個(gè)運(yùn)算符可以有若干個(gè)運(yùn)算對(duì)象。例職，取正（+）等只有一個(gè)運(yùn)算對(duì)象，稱為單目運(yùn)算符；二個(gè)運(yùn)算對(duì)象稱為雙目運(yùn)算符，三目運(yùn)算符。
用樹來表示算術(shù)表達(dá)式的原則如下：
表達(dá)式中的每一個(gè)運(yùn)算符在樹中對(duì)應(yīng)一個(gè)結(jié)點(diǎn)，稱為運(yùn)算符結(jié)點(diǎn)。
運(yùn)算符的每一個(gè)運(yùn)算對(duì)象在樹中為該運(yùn)算符結(jié)點(diǎn)的子樹（在樹中的順序?yàn)閺淖蟮接遥?BR> 運(yùn)算對(duì)象中的單變量均為葉子結(jié)點(diǎn)。
二、二叉樹及其基本性質(zhì)
1、什么是二叉樹
二叉樹是一種很有用的非線性結(jié)構(gòu)。二就樹具有以下兩個(gè)特點(diǎn)：
非空二叉樹只有一個(gè)根結(jié)點(diǎn)；
每一個(gè)結(jié)點(diǎn)最多有兩棵子樹，且分別稱為該結(jié)點(diǎn)的左子樹與右子樹。
由以上特點(diǎn)可以看出，在二叉樹中，每一個(gè)結(jié)點(diǎn)的度為2，即所有子樹（左子樹或右子樹）也均為二叉樹，而樹結(jié)構(gòu)中的每一個(gè)結(jié)點(diǎn)的度可以是任意的。另外，二叉樹中的每一個(gè)結(jié)點(diǎn)的子樹被明顯地分為左子樹與右子樹?？梢詻]有其中的一個(gè)，也可以全沒有。
二叉樹的基本性質(zhì)
性質(zhì)1：在二叉樹的第K層上，最多有（K≥1）個(gè)結(jié)點(diǎn)。
性質(zhì)2：濃度為M的二叉樹最多有2m-1 個(gè)結(jié)點(diǎn)。
深度為m 的二叉樹是指二叉樹共有m層。
性質(zhì)3：在任意一棵二叉樹中度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個(gè)。
性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的二叉樹，其深度至少為[ log2n]+1,其中[ log2n]表示取的整數(shù)部分。
滿二叉樹與完全二叉樹
滿二叉樹與完全二叉樹是兩種特殊形態(tài)的二叉樹。
滿二叉樹
所謂滿二叉樹是指這樣的一種二叉樹；除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。這就是說，在滿二叉樹中，每一層上的結(jié)點(diǎn)數(shù)都達(dá)到值，即在滿二叉樹的第K層上有2K-1個(gè)結(jié)點(diǎn)，且深度為m的滿二叉樹有2m-1個(gè)結(jié)點(diǎn)。
完全二叉樹
所謂完全二叉樹是指這樣的二叉樹，除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)的值；在最后一層上只缺少右邊的若干結(jié)點(diǎn)。
列確切地說，如果從根結(jié)點(diǎn)起，對(duì)二叉樹的結(jié)點(diǎn)自上而下、自左至右用自然數(shù)進(jìn)行邊疆編號(hào)，則深度為m、且有n 個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為m的滿二叉樹中編號(hào)從1到n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱之為完全二叉樹。
對(duì)于完全二叉樹來說，葉子結(jié)點(diǎn)只可能在層次的兩層上出現(xiàn)；對(duì)于任何一個(gè)結(jié)點(diǎn)，若其右分支下的子孫結(jié)點(diǎn)的層次為p，則其左分支下的子孫結(jié)點(diǎn)的層次或?yàn)閜，或?yàn)閜+1。
由滿二叉樹與完全二叉樹的特點(diǎn)可以看出，滿二叉樹也是完全二叉樹，而完全二叉樹一般不是滿二叉樹。
完全二叉樹還具有以下兩個(gè)性質(zhì)：
性質(zhì)5：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為[ log2n]+1。
性質(zhì)6：設(shè)完全二叉樹共有n個(gè)結(jié)點(diǎn)。如果從根結(jié)點(diǎn)開始，按層序（每一層從左到右）用自然數(shù)1，2，…，n給結(jié)點(diǎn)進(jìn)行編號(hào)，則對(duì)于編號(hào)為k （k=1,2,…n）的結(jié)點(diǎn)有以下結(jié)論：
若k=1，則該結(jié)點(diǎn)為根結(jié)點(diǎn)，它沒有父結(jié)點(diǎn)；若k>1，則該結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為INT(k/2)。
若2k≤n，則編號(hào)為k 的結(jié)點(diǎn)的左子結(jié)點(diǎn)編號(hào)為2k ；否則該結(jié)點(diǎn)無左子結(jié)點(diǎn)（顯然也沒有右子結(jié)點(diǎn)）。
若2k+1≤n，則編號(hào)為k 的結(jié)點(diǎn)的右子結(jié)點(diǎn)編號(hào)為2k+1；否則該結(jié)點(diǎn)無右子結(jié)點(diǎn)。
三、二叉樹的存儲(chǔ)結(jié)構(gòu)
二叉樹的遍歷
二叉樹的遍歷是指不重復(fù)地訪問二叉樹的所有結(jié)點(diǎn)。
在遍歷二叉樹的過程中，一般先遍歷左子樹，然后再遍歷右子樹。
1、前序遍歷（DLR）
所謂前序遍歷是指在訪問根結(jié)點(diǎn)、遍歷左子樹與遍歷右子樹這三者中，首先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹；并且，在遍歷左、右子樹時(shí)，仍然先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹。F，C，A，D，B，E，G，H，P
2、中序遍歷（LDR）
所謂中序遍歷是指在訪問根結(jié)點(diǎn)、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹；并且，在遍歷左、右子樹時(shí)，仍然先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹。A，C，B，D，F(xiàn)，E，H，G，P
3、后序遍歷（LRD）
所謂中序遍歷是指在訪問根結(jié)點(diǎn)、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點(diǎn)；并且，在遍歷左、右子樹時(shí)，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點(diǎn)。A，B，D，C，H，P，G，E，F(xiàn)
1.7查找技術(shù)
一、順序查找
順序查找又稱順序搜索。順序查找一般是指在線性表中查找指定的元素，其基本方法如下：從線性表的第一個(gè)元素開始，依次將線性表中的元素與被查元素進(jìn)行比較，若相等則表示找到（即查找成功）；若線性表中所有的元素都與被查元素進(jìn)行了比較但都不相等，則表示線性表中沒有要找的元素（即查找失敗）。
順序查找的效率是很低的。以下兩種情況只能采用順序查找：
如果線性表無序表（即表中元素的排列是無序的），則不管是順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，都只能用順序查找。
即使是有序線性表，如果采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，也只能用順序查找。
二、二分法查找
二分法查找只適用于存儲(chǔ)的有序表。在此所說的有序表是指線性表的中元素按值非遞減排列（即從小到大，但允許相鄰元素值相等）。
設(shè)有序線性表的長度為n，被查元素為x，則對(duì)分查找的方法如下：
將x與線性表的中間項(xiàng)進(jìn)行比較：
若中間項(xiàng)的值等于x，則說明查到，查找結(jié)束；
若x小于中間項(xiàng)的值，則在線性表的前半部分（即中間項(xiàng)以前的部分）以相同的方法進(jìn)行查找；
若x大于中間項(xiàng)的值，則在線性表的后半部分（即中間項(xiàng)以后的部分）以相同的方法進(jìn)行查找。
這個(gè)過程一直進(jìn)行到查找成功或子表長度為0（說明線性表中沒有這個(gè)元素）為止。
顯然，當(dāng)有序線性表為順序存儲(chǔ)時(shí)才能采用二分查找，并且，二分查找的效率要比順序查找高得多?？梢宰C明，對(duì)于長度為n的有序線性表，在最壞情況下，二分查找只需要比較log2n次，而順序查找需要比較n次。