考點(diǎn)14樹與二叉樹之間的轉(zhuǎn)換
1.樹轉(zhuǎn)換成二叉樹
將一棵樹轉(zhuǎn)換成相應(yīng)的二叉樹應(yīng)包括以下幾個(gè)步驟：
(1)在兄弟竹點(diǎn)之間加條連線
(2)對每一個(gè)節(jié)點(diǎn)，只保留它與第一個(gè)子節(jié)點(diǎn)的連線，與其他子節(jié)點(diǎn)連線全部抹掉
(3)以樹根為軸心，順時(shí)針旋轉(zhuǎn)45。
2.森林轉(zhuǎn)換成二叉樹
如果F={T¬1¬¬ ，T¬2 ,…Tm}是森林，則可按如下規(guī)則將其轉(zhuǎn)換乘一棵二叉樹B=(root,LB,RB,)：
(1)若F為空，即m＝0，則B為樹。
(2)若F非空，即m≠0, 則B的跟root即為森林中的第一棵樹的跟ROOT(¬¬T)；B的左子樹LB是從T、中根節(jié)點(diǎn)的子樹森林F1＝｛T11，T¬，…，T¬m｝轉(zhuǎn)換而成的二叉樹；其右子樹RB是從森林Fˊ＝{T¬1,T2,…Tm}轉(zhuǎn)換而成的二叉樹。
3.二叉樹轉(zhuǎn)換成森林
如果B二(root，LB，RB)是、棵二叉樹，則可按如下規(guī)則轉(zhuǎn)換成森林F＝{T¬1,T2,…Tm}：
(1)若B為空，則F為空。
(2)若B非空，則F中第一棵樹T1的根ROOT(T1)即為二叉樹B的根root; T1中根節(jié)點(diǎn)的子樹森林Fl是由B的左子樹LB轉(zhuǎn)換而成的；F中除T1之外其余樹組成的森林Fˊ＝ {T¬1,T2,…Tm}是由B的右子樹RB轉(zhuǎn)換而成的。
考點(diǎn)15二叉樹和樹的周游
周游(或稱遍歷)是樹型結(jié)構(gòu)的一種重要運(yùn)算，是其他運(yùn)算的基礎(chǔ)。周游一棵樹就是按一定的次序訪問樹中聽有節(jié)點(diǎn)，并且每個(gè)節(jié)點(diǎn)僅被訪問一次的過程。
1.周游二叉樹
二又樹的周游主要有以下3種方式。
(1)前序法(NLR)。訪問根，按前序周游左子樹，按前序周游右子樹。
(2)后序法(LRN)。按后序周游左子樹，按后序周游右子樹，訪問根。
(3)對稱序法(LNR)。按對稱序周游左子樹，訪問根，按對稱序周游右子樹。
2.周游樹和樹林
對樹和樹林的周游分為按深度優(yōu)先和按廣度優(yōu)先兩種方式進(jìn)行。
按深度優(yōu)先方式又可分為按先根次序和按后根次序周游兩種方式。
(1)先根次序周游訪問第一棵樹的根，按先根次序周游第一棵樹的根子樹，按先根次序周游其他的樹。
(2)后根次序周游按后根次序周游第一棵樹的子樹，訪問第一棵樹的根，按后根次序周游其他的樹。
比較一下樹與一又樹之間的對應(yīng)關(guān)系，可以看出，按先根次序周游樹正好與按前序法周游樹對應(yīng)的二叉樹等同，后根次序周游樹正好與按對稱序法周游對應(yīng)的二叉樹等同。
按廣度優(yōu)先方式可以做層次次序周游，首先依次訪問層數(shù)為0的節(jié)點(diǎn)，然后依次訪問下一層的節(jié)點(diǎn)，直至訪問完最后一層的節(jié)點(diǎn)。
考點(diǎn)16二叉樹的存儲(chǔ)和線索
l二叉樹的llink一rlink法存儲(chǔ)表示
二叉樹的存儲(chǔ)通常采用鏈接方式，即每個(gè)節(jié)點(diǎn)除存儲(chǔ)節(jié)點(diǎn)自身的信息外再設(shè)置兩個(gè)指針域llink和 rlink，分別指向節(jié)點(diǎn)的左子女和右子女。當(dāng)節(jié)點(diǎn)的某個(gè)子女為空時(shí)，則相應(yīng)的指針值為空。再加上一個(gè)指向
樹根的指針t，就構(gòu)成了二叉樹的存儲(chǔ)表示。這種存儲(chǔ)表示法被稱為llink - rlink表示法。
2.線索二叉樹
在有n個(gè)節(jié)點(diǎn)的二叉樹的且ink - rlink法存儲(chǔ)表示中，必定有n+1個(gè)空指針域，將這些指針位置利用起來，存儲(chǔ)節(jié)點(diǎn)在指定周游次序F的前驅(qū)、后繼節(jié)點(diǎn)指針，則得到線索二叉樹。
考點(diǎn)17哈夫曼樹
哈夫曼樹是樹型結(jié)構(gòu)的一種應(yīng)用二哈夫曼(Huffman)樹又稱樹，是一類帶權(quán)路徑長度最短的樹，這種樹在信息檢索中經(jīng)常用到。所謂路徑長度就是從一個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)所經(jīng)過的分支總數(shù)。樹的路徑長度是從樹的根到每個(gè)節(jié)點(diǎn)的路徑長度之和。完全二叉樹就是這種路徑長度最短的二叉樹。節(jié)點(diǎn)的帶權(quán)路徑長度為從該節(jié)點(diǎn)到樹根之間的路徑長度與節(jié)點(diǎn)上權(quán)的乘積。樹的帶權(quán)路徑長度為樹中所有葉子節(jié)點(diǎn)的帶權(quán)路徑長度之和，WPL最小的不是完全二叉樹，而是權(quán)大的葉子離根最近的二叉樹。
2.5“查找
查找是數(shù)據(jù)結(jié)構(gòu)中一種很常用的基本運(yùn)算。
查找就是在數(shù)據(jù)結(jié)構(gòu)中找出滿足某種條件的節(jié)點(diǎn)。所給的條件可以是關(guān)鍵碼字段的值，也可以是非關(guān)鍵碼字段的值，本節(jié)只考慮基于關(guān)鍵碼值的查找
考點(diǎn)18順序查找
順序查找是線性表的最簡單、最基本的查找方法順序查找的優(yōu)點(diǎn)是對線性表節(jié)點(diǎn)的邏輯次序無要求，對線性表存儲(chǔ)結(jié)構(gòu)也無要求
順序查找的缺點(diǎn)是速度較慢，平均檢索長度與表中節(jié)點(diǎn)個(gè)數(shù)和n成正比，查找成功最多需比較n次，平均查找長度為(n +1 )/2次，約為表長的，半，查找失敗需比較n+l次順序查找算法的時(shí)間復(fù)雜度為O(n)。
考點(diǎn)19二分法查找
二分法查找是一種效率比較高的查找方法，在進(jìn)行二分法查找時(shí)，線性表節(jié)點(diǎn)必須按關(guān)鍵碼值排序，且 線性表是以順序存儲(chǔ)方式存儲(chǔ)的。
二分法查找的優(yōu)點(diǎn)是比較次數(shù)少，查找速度快，平均檢索長度小，經(jīng)過｛＿loge n次比較就可以完成查找過程。缺點(diǎn)是在查找之前要為建立有序表付出代價(jià)，同時(shí)對有序表的插人和刪除都需要平均比較和移動(dòng)表中 的一半元素。一般情況下，二分查找適應(yīng)于數(shù)據(jù)相對固定的情況，且二分法查找只適用于線性表的順序存儲(chǔ)。
考點(diǎn)20分塊查找
分塊查找又稱索引順序查找，是介于線性查找和二分法查找之間的一種查找方法。它要求把線性表分 成若干塊，每一塊中的節(jié)點(diǎn)不必有序，但塊與塊之間必須排序，不妨設(shè)每一塊中各節(jié)點(diǎn)的關(guān)鍵碼都大于前一塊的關(guān)鍵碼值。另外，還要求將各塊中的關(guān)鍵碼值組成一個(gè)有序的索引表。滿足上述條件的線性 表稱做分塊有序表。它的分塊檢索的過程分以下兩步進(jìn)行。
(I)先查索引表(可以用線性檢索或二分法檢索)，確定要找的記錄在哪一塊。
(2)在相應(yīng)的塊中線性檢索待查記錄。
1.樹轉(zhuǎn)換成二叉樹
將一棵樹轉(zhuǎn)換成相應(yīng)的二叉樹應(yīng)包括以下幾個(gè)步驟：
(1)在兄弟竹點(diǎn)之間加條連線
(2)對每一個(gè)節(jié)點(diǎn)，只保留它與第一個(gè)子節(jié)點(diǎn)的連線，與其他子節(jié)點(diǎn)連線全部抹掉
(3)以樹根為軸心，順時(shí)針旋轉(zhuǎn)45。
2.森林轉(zhuǎn)換成二叉樹
如果F={T¬1¬¬ ，T¬2 ,…Tm}是森林，則可按如下規(guī)則將其轉(zhuǎn)換乘一棵二叉樹B=(root,LB,RB,)：
(1)若F為空，即m＝0，則B為樹。
(2)若F非空，即m≠0, 則B的跟root即為森林中的第一棵樹的跟ROOT(¬¬T)；B的左子樹LB是從T、中根節(jié)點(diǎn)的子樹森林F1＝｛T11，T¬，…，T¬m｝轉(zhuǎn)換而成的二叉樹；其右子樹RB是從森林Fˊ＝{T¬1,T2,…Tm}轉(zhuǎn)換而成的二叉樹。
3.二叉樹轉(zhuǎn)換成森林
如果B二(root，LB，RB)是、棵二叉樹，則可按如下規(guī)則轉(zhuǎn)換成森林F＝{T¬1,T2,…Tm}：
(1)若B為空，則F為空。
(2)若B非空，則F中第一棵樹T1的根ROOT(T1)即為二叉樹B的根root; T1中根節(jié)點(diǎn)的子樹森林Fl是由B的左子樹LB轉(zhuǎn)換而成的；F中除T1之外其余樹組成的森林Fˊ＝ {T¬1,T2,…Tm}是由B的右子樹RB轉(zhuǎn)換而成的。
考點(diǎn)15二叉樹和樹的周游
周游(或稱遍歷)是樹型結(jié)構(gòu)的一種重要運(yùn)算，是其他運(yùn)算的基礎(chǔ)。周游一棵樹就是按一定的次序訪問樹中聽有節(jié)點(diǎn)，并且每個(gè)節(jié)點(diǎn)僅被訪問一次的過程。
1.周游二叉樹
二又樹的周游主要有以下3種方式。
(1)前序法(NLR)。訪問根，按前序周游左子樹，按前序周游右子樹。
(2)后序法(LRN)。按后序周游左子樹，按后序周游右子樹，訪問根。
(3)對稱序法(LNR)。按對稱序周游左子樹，訪問根，按對稱序周游右子樹。
2.周游樹和樹林
對樹和樹林的周游分為按深度優(yōu)先和按廣度優(yōu)先兩種方式進(jìn)行。
按深度優(yōu)先方式又可分為按先根次序和按后根次序周游兩種方式。
(1)先根次序周游訪問第一棵樹的根，按先根次序周游第一棵樹的根子樹，按先根次序周游其他的樹。
(2)后根次序周游按后根次序周游第一棵樹的子樹，訪問第一棵樹的根，按后根次序周游其他的樹。
比較一下樹與一又樹之間的對應(yīng)關(guān)系，可以看出，按先根次序周游樹正好與按前序法周游樹對應(yīng)的二叉樹等同，后根次序周游樹正好與按對稱序法周游對應(yīng)的二叉樹等同。
按廣度優(yōu)先方式可以做層次次序周游，首先依次訪問層數(shù)為0的節(jié)點(diǎn)，然后依次訪問下一層的節(jié)點(diǎn)，直至訪問完最后一層的節(jié)點(diǎn)。
考點(diǎn)16二叉樹的存儲(chǔ)和線索
l二叉樹的llink一rlink法存儲(chǔ)表示
二叉樹的存儲(chǔ)通常采用鏈接方式，即每個(gè)節(jié)點(diǎn)除存儲(chǔ)節(jié)點(diǎn)自身的信息外再設(shè)置兩個(gè)指針域llink和 rlink，分別指向節(jié)點(diǎn)的左子女和右子女。當(dāng)節(jié)點(diǎn)的某個(gè)子女為空時(shí)，則相應(yīng)的指針值為空。再加上一個(gè)指向
樹根的指針t，就構(gòu)成了二叉樹的存儲(chǔ)表示。這種存儲(chǔ)表示法被稱為llink - rlink表示法。
2.線索二叉樹
在有n個(gè)節(jié)點(diǎn)的二叉樹的且ink - rlink法存儲(chǔ)表示中，必定有n+1個(gè)空指針域，將這些指針位置利用起來，存儲(chǔ)節(jié)點(diǎn)在指定周游次序F的前驅(qū)、后繼節(jié)點(diǎn)指針，則得到線索二叉樹。
考點(diǎn)17哈夫曼樹
哈夫曼樹是樹型結(jié)構(gòu)的一種應(yīng)用二哈夫曼(Huffman)樹又稱樹，是一類帶權(quán)路徑長度最短的樹，這種樹在信息檢索中經(jīng)常用到。所謂路徑長度就是從一個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)所經(jīng)過的分支總數(shù)。樹的路徑長度是從樹的根到每個(gè)節(jié)點(diǎn)的路徑長度之和。完全二叉樹就是這種路徑長度最短的二叉樹。節(jié)點(diǎn)的帶權(quán)路徑長度為從該節(jié)點(diǎn)到樹根之間的路徑長度與節(jié)點(diǎn)上權(quán)的乘積。樹的帶權(quán)路徑長度為樹中所有葉子節(jié)點(diǎn)的帶權(quán)路徑長度之和，WPL最小的不是完全二叉樹，而是權(quán)大的葉子離根最近的二叉樹。
2.5“查找
查找是數(shù)據(jù)結(jié)構(gòu)中一種很常用的基本運(yùn)算。
查找就是在數(shù)據(jù)結(jié)構(gòu)中找出滿足某種條件的節(jié)點(diǎn)。所給的條件可以是關(guān)鍵碼字段的值，也可以是非關(guān)鍵碼字段的值，本節(jié)只考慮基于關(guān)鍵碼值的查找
考點(diǎn)18順序查找
順序查找是線性表的最簡單、最基本的查找方法順序查找的優(yōu)點(diǎn)是對線性表節(jié)點(diǎn)的邏輯次序無要求，對線性表存儲(chǔ)結(jié)構(gòu)也無要求
順序查找的缺點(diǎn)是速度較慢，平均檢索長度與表中節(jié)點(diǎn)個(gè)數(shù)和n成正比，查找成功最多需比較n次，平均查找長度為(n +1 )/2次，約為表長的，半，查找失敗需比較n+l次順序查找算法的時(shí)間復(fù)雜度為O(n)。
考點(diǎn)19二分法查找
二分法查找是一種效率比較高的查找方法，在進(jìn)行二分法查找時(shí)，線性表節(jié)點(diǎn)必須按關(guān)鍵碼值排序，且 線性表是以順序存儲(chǔ)方式存儲(chǔ)的。
二分法查找的優(yōu)點(diǎn)是比較次數(shù)少，查找速度快，平均檢索長度小，經(jīng)過｛＿loge n次比較就可以完成查找過程。缺點(diǎn)是在查找之前要為建立有序表付出代價(jià)，同時(shí)對有序表的插人和刪除都需要平均比較和移動(dòng)表中 的一半元素。一般情況下，二分查找適應(yīng)于數(shù)據(jù)相對固定的情況，且二分法查找只適用于線性表的順序存儲(chǔ)。
考點(diǎn)20分塊查找
分塊查找又稱索引順序查找，是介于線性查找和二分法查找之間的一種查找方法。它要求把線性表分 成若干塊，每一塊中的節(jié)點(diǎn)不必有序，但塊與塊之間必須排序，不妨設(shè)每一塊中各節(jié)點(diǎn)的關(guān)鍵碼都大于前一塊的關(guān)鍵碼值。另外，還要求將各塊中的關(guān)鍵碼值組成一個(gè)有序的索引表。滿足上述條件的線性 表稱做分塊有序表。它的分塊檢索的過程分以下兩步進(jìn)行。
(I)先查索引表(可以用線性檢索或二分法檢索)，確定要找的記錄在哪一塊。
(2)在相應(yīng)的塊中線性檢索待查記錄。