第章樹教學內容

第5章樹大連東軟信息學院計算機系課前導學[內容提要]樹和森林二叉樹的定義、性質二叉樹的遍歷；樹、森林與二叉樹的轉換；線索二叉樹二叉樹的應用2考綱要求第1節(jié)樹和森林了解：樹和森林的基本概念和術語。掌握：樹和森林的存儲結構定義。重點掌握：樹與森林的遍歷第2節(jié)二叉樹了解：二叉樹的定義。掌握：二叉樹的基本性質及存儲結構定義。重點掌握：二叉樹的存儲結構。第3節(jié)二叉樹的遍歷了解：二叉樹的遍歷的機制。掌握：二叉樹的遍歷的四種算法、遞歸算法的非遞歸轉化。重點掌握：二叉樹的遍歷的遞歸算法。3第4節(jié)樹、森林與二叉樹的轉換了解：樹、森林與二叉樹的關系。掌握：樹、森林與二叉樹的轉換方法。第5節(jié)線索二叉樹了解：線索二叉樹的概念。掌握：線索二叉樹的存儲結構定義。重點掌握：線索二叉樹的創(chuàng)建和遍歷算法。第6節(jié)二叉樹的應用了解：二叉樹的應用范圍。掌握：二叉樹的幾種應用算法，如表達式求值、堆排序樹、哈夫曼樹。重點掌握：二叉樹的遍歷應用。46A只有根結點的樹ABCDEFKHIJ有子樹的樹根子樹樹的表示法G樹的基本術語結點（node）：表示樹中的元素，包括數(shù)據(jù)項及若干指向其子樹的分支。結點的度（degree）：是指結點擁有的子樹個數(shù)。樹的度：一棵樹中最大的結點度數(shù)。分支結點（branch）：度大于0的結點稱為分支結點或者非終端結點。葉子結點（leaf）：度為0的結點稱為葉子結點或者終端結點。7樹的基本術語孩子結點（child）：結點子樹的根稱為該結點的孩子。雙親結點（parents）：孩子結點的上層結點叫該結點的雙親結點。兄弟結點（sibling）：同一雙親的孩子互稱為兄弟結點。堂兄弟結點（cousin）：雙親在同一層上的結點互稱為堂兄弟結點。祖先結點（ancestor）：從根到該結點的所經(jīng)路徑上的所有結點均稱為祖先結點。子孫結點：以某結點為根的子樹中任一結點都稱為該結點的子孫結點。8樹的基本術語結點的層次（level）：樹具有層次結構。從根結點算起，根為第一層，它的孩子為第二層，……，依此類推。樹的深度（depth）：樹中結點的最大層次數(shù)稱為樹的深度或高度。有序樹和無序樹：如果樹中各結點的子樹是按照從左到右或者從右到左確定的，也就是說是有次序的，那么該樹稱為有序樹，否則稱為無序樹。例如，家族樹就是一棵有序樹。森林（forest）：m(m≥0)棵互不相交的樹的集合。由0棵樹組成的森林成為空森林。910結點A的度：結點B的度：結點K的度：葉子：結點A的孩子：結點B的孩子：結點I的雙親：結點K的雙親：結點B，C，D為兄弟結點I，J為兄弟樹的度：結點A的層次：結點K的層次：樹的深度：結點F，G為堂兄弟結點A是結點F，G的祖先320B，C，DE，F(xiàn)3F，H，I，J，KEG144樹的存儲結構雙親表示法孩子表示法多重鏈表表示法孩子鏈表表示法孩子兄弟表示法11樹的存儲結構結點的一般形式為:12DataPointers樹的標準存儲結構結點的數(shù)據(jù)類型定義如下：structnode{chardata;structnode*child[m];}typedefstructnodeNODE;NODE*root1;13結點的一般形式為:Datachild0，child1，…樹的逆形式存儲結構結點的數(shù)據(jù)類型定義如下：structr_node{chardata;structr_node*parent;}typedefstructr_nodeR_NODE;R_NODE*root1;14結點的一般形式為:DataParent樹的擴充標準形式存儲結構結點的數(shù)據(jù)類型定義如下：structe_node{chardata;structe_node*child[m];structe_node*parent;}typedefstructe_nodeNODE;NODE*root2;15結點的一般形式為:Datachild0，child1，…Parent16171819樹和森林的遍歷通常有3種遍歷樹的方法:前序(先根)遍歷：:首先訪問根結點。然后，若根結點有子樹，則按從左至右的次序前序遍歷根結點的各棵子樹;若根結點沒有子樹，則遍歷結束。后序(后根)遍歷：若根結點有子樹，則先按從左至右的次序后序遍歷根結點的各棵子樹，然后訪問根結點;若根結點沒有子樹，則直接訪問根結點。層次遍歷：首先訪問處于第一層上的根結點，然后按從左至右的次序訪問處于第二層上的各個結點，依此類推……20樹的遍歷算法遞歸實現(xiàn)voidTreePreOrder(NODE*t，intm)//前序遍歷{inti;if(t!=NULL){printf("%c",t->data);for(i=0;i<m;i++)TreePreOrder(t->child[i],m);}}后續(xù)遍歷類似，見書P97.21遍歷森林森林也有前序和后序兩種遍歷方法。森林的前序遍歷：若森林為空，則遍歷結束;否則，訪問森林的第1棵樹的根結點，然后前序遍歷第1棵樹的根結點的各子樹所構成的森林，接著遍歷除森林的第1棵樹以外的其他各樹所構成的森林。森林的后序遍歷：若森林為空，則遍歷結束;否則，后序遍歷森林的第1棵樹的根結點的各子樹所構成的森林，然后訪問森林中第1棵樹的根結點，最后后序遍歷除森林的第1棵樹以外的其他各樹所構成的森林。225.2二叉樹二叉樹的定義：

二叉樹是n(n≥0)個結點的有限集，它或為空樹(n=0)，或由一個根結點和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構成。

二叉樹的特點：

1）每個結點至多有二棵子樹(即不存在度大于2的結點) 2）二叉樹的子樹有左、右之分，且其次序不能任意顛倒23二叉樹的五種基本形態(tài)24（a） （b） （c） （d） （e）（a）空二叉樹（b）只有根結點的二叉樹（c）只有左子樹的二叉樹（d）只有右子樹的二叉樹（e）有左、右子樹的二叉樹滿二叉樹定義：

在一棵二叉樹中，如果所有分支結點都存在左子樹和右子樹，并且所有葉子結點都在同一層上，這樣的一棵二叉樹稱作滿二叉樹。 25擬滿樹（完全二叉樹）定義：一棵深度為k的有n個結點的二叉樹，對樹中的結點按從上至下、從左到右的順序進行編號，如果編號為i（1≤i≤n）的結點與滿二叉樹中編號為i的結點在二叉樹中的位置相同，則這棵二叉樹稱為完全二叉樹。26豐滿樹假設T是一棵高度為h的二叉樹，若將T的第h層的結點全部去掉，得到二叉樹T'，若T'是滿二叉樹，則稱二叉樹T為豐滿樹。滿樹一定是擬滿樹，擬滿樹一定是豐滿樹。反之無效。27281231145891213671014151231145891267101234567123456二叉樹的性質性質1

在二叉樹第i層上至多有２i-1

個結點（i≥1）。

證明：用歸納法證明之。當i=1時，二叉樹的第1層只有一個根結點。2i-1=21-1=20=1成立。假設該命題對所有j（1<j<i）成立，即第j層上至多有2j-1個結點，那么第i-1層至多有2i-2個結點。因為二叉樹每個結點的度不超過2，因此，第i層的結點個數(shù)最多是第i-1層結點個數(shù)的2倍，即最多不超過2*2i-2=2i-1。命題得證。29二叉樹的性質：性質2深度為k（k≥1）的二叉樹至多有２k－1個結點。證明：由性質1可知，深度為k（k≥1）的二叉樹的最大結點個數(shù)為每層的最大結點個數(shù)之和，即命題得證。

30二叉樹的性質：性質3

對任何一顆二叉樹T，如果其終端結點數(shù)為n0，度為2的結點數(shù)為n2,則n0=n2+1。證明：假設n1為二叉樹T中度為1的結點數(shù)，因為二叉樹中所有結點的度均小于或等于2，所以，二叉樹的結點總數(shù)

n=n0+n1+n2 （公式4.1）又知二叉樹中，除根結點外，其余結點都只有一個分支進入。設B為分支總數(shù)，則二叉樹的結點總數(shù)

n=B+1 （公式4.2）又知所有分支均由度為1和度為2的結點射出，因此分支總數(shù)

B=n1+2n2 （公式4.3）由公式4.2和公式4.3可以得到

n=n1+2n2+1 （公式4.4）由公式4.1和公式4.4可以得到n0=n2+131二叉樹的性質：性質4

具有n個結點的完全二叉樹的深度為

log2n

+1。證明：由完全二叉樹的定義可知，假設具有n個結點的完全二叉樹的深度為k（k≥1），則從第1層都第k-1層都是滿的，第k層結點個數(shù)為1＜n≤2k-1，則根據(jù)性質2和完全二叉樹的定義，有2k-1-1＜n≤2k-1，則有

2k-1＜n+1≤2k或2k-1≤n＜2k得到

k-1≤log2n＜k或

log2n＜k≤log2n+1因為k為整數(shù)，所以k=

log2n+1。32二叉樹的性質：

性質5如果對一棵有n個結點的完全二叉樹的結點按層序編號，則對任一結點i（1≤i≤n），有：(1)如果i=1，則結點i是二叉樹的根，無雙親；如果i>1，則其雙親是

i/2

；(2)如果2i>n，則結點i無左孩子；如果2i≤n，則其左孩子是2i；(3)如果2i+1>n，則結點i無右孩子；如果2i+1≤n，則其右孩子是2i+1。33證明：當i＝1時，由完全二叉樹的定義知其左孩子是結點2。若2>n，即不存在結點2，此時結點i無左孩子。結點i的右孩子也只能是結點3，若結點3不存在，即3>n，此時結點i無右孩子。結論成立。當i=k（1<k<

log2n

）時，第k層的第一個結點的編號為i（由二叉樹的定義和性質2可知i＝2k-1），則其左孩子必為第i+1層的第一個結點，其編號為2k＝2*2k-1＝2i，若2i>n，則編號為2i的結點不存在，即結點i無左孩子；其右孩子必為第i+1層的第二個結點，其編號為2k+1＝2i+1。若2i+1>n，則編號為2i+1的結點不存在，即結點i無右孩子。又若2i+1<n，則其左孩子為2i，右孩子為2i+1。結論成立。34二叉樹的存儲結構 二叉樹的存儲結構順序存儲結構二叉鏈表三叉鏈表35二叉樹的順序存儲結構首先要該樹中每個結點進行編號，然后以各結點的編號為下標，把各結點的值對應存儲到一維數(shù)組中。完全二叉樹的順序存儲結構：

36二叉樹的順序存儲結構(續(xù))非完全二叉樹的順序存儲結構：37二叉鏈表一般的二叉樹使用順序存儲結構存儲在數(shù)組中浪費的空間比較多。可以使用鏈表來存儲二叉樹，并使用兩個指針分別指向二叉樹的左子樹和右子樹，這樣就形成了二叉鏈表。在二叉鏈表中，每個結點包含三個域：數(shù)據(jù)域、左指針域和右指針域。38二叉鏈表二叉鏈表的類型定義：typedefstructBTNode{TElemTypedata;structBTNode*lchild,*rchild;}BTNode;BTNode*bt;39二叉鏈表非完全二叉樹的二叉鏈表存儲結構40三叉鏈表有時需要查找某個結點的雙親結點，這時使用二叉鏈表很不方便。因此，人們想到了在結點中再設一個指針域，用來指向結點的雙親結點，這就是三叉鏈表。三叉鏈表中每個結點包括四個域：數(shù)據(jù)域、左指針域、右指針域和雙親指針域。41三叉鏈表三叉鏈表的定義：typedefstructBTNode{TElemTypedata;structBTNode*lchild,*rchild,*parent;}BTNode;BTNode*bt;42三叉鏈表非完全二叉樹的三叉鏈表存儲結構43二叉樹的遍歷1)二叉樹的前序遍歷:若二叉樹為空，則遍歷結束;否則，①先訪問根結點，②再前序遍歷根結點的左子樹，③最后前序遍歷根結點的右子樹。2)二叉樹的中序遍歷:若二叉樹為空，則遍歷結束;否則，①先中序遍歷根結點的左子樹，②再訪問根結點，③最后中序遍歷根結點的右子樹。3)二叉樹的后序遍歷:若二叉樹為空，則遍歷結束;否則，①先后序遍歷根結點的左子樹，②再后序遍歷根結點的右子樹，③最后訪問根結點。4)二叉樹層次遍歷:若二叉樹為空，則遍歷結束:否則，首先訪問處于第1層上的根結點，然后按從左至右的次序訪問處于第二層上的各個結點，......，依此類推，按從左至右的次序依次訪問處于以后各層上的結點。5.4樹、森林向二叉樹的轉換樹向二叉樹的轉換森林向二叉樹的轉換45樹向二叉樹的轉換方法：樹中結點的孩子放在二叉樹的左子樹中，樹中結點的兄弟放在二叉樹的右子樹中，簡而言之就是，左孩子右兄弟。轉換步驟：（1）在兄弟節(jié)點之間連一條線；（2）每個結點僅保留其與最左孩子之間的連線，其余連線刪除；（3）以根為軸心將整棵樹順時針旋轉45度。46樹向二叉樹的轉換47思考：如何將一棵二叉樹轉換成樹？森林向二叉樹的轉換方法：先把森林中的每一棵樹轉換成二叉樹，然后從最后一棵樹開始，把后一棵樹作為前一棵樹的右孩子。485.4.2二叉樹還原為樹、森林假設T是一棵二叉樹，把T還原為森林F(T)=(T0，T1,…,Tm-1)的方法如下:1)如果T為空二叉樹，則F(T)為空;2)如果T為非空二叉樹，則F(T)中的第一棵樹T0的根結點為T的根結點;T0的根結點的子樹所組成的序列是由T的左子樹還原而成的森林F(T的左子樹);F中除T0以外的其余的樹所組成的序列(T1，T2，…，Tm-1)是由T的右子樹還原而成的森林F(T的右子樹)。49例5051線索二叉樹線索：指向前驅或后繼結點的指針稱為線索。線索二叉樹：加上了線索的二叉鏈表稱為線索鏈表，相應的二叉樹稱為線索二叉樹。對二叉樹以某種次序進行遍歷以使其變成線索二叉樹的過程，稱之為二叉樹的線索化。lchildlflagdatarflagrchild52其中：左標志lflag=0表示lchild是指向結點的左孩子的指針，否則，為指向結點的前驅的左線索。右標志rflag=0表示rchild是指向結點的右孩子的指針，否則，為指向結點的后繼的右線索。

線索二叉樹類型定義：typedefstructBTNode{ ElemTypedata;

intlflag,rflag; structBTNode*lchild,*rchild;}BTNode;根據(jù)遍歷的順序，線索二叉樹可以分為先序線索二叉樹、中序線索二叉樹和后序線索二叉樹。53二叉樹線索化的步驟（1）設兩個指針，分別指向當前結點和當前結點的前驅結點。（2）若前驅結點不為空，或者說根結點不是序列中的第一個結點，同時前驅結點rflag=1（即前驅結點沒有右孩子）時，則將根結點的指針賦給前驅結點的右指針域，即給前驅結點加右線索。（3）若根結點沒有左孩子，則令lflag=1，同時把前驅結點的指針賦給根結點的左指針域，即給根結點加左線索。（4）若根結點沒有右孩子，則令rflag=l，以便訪問到下一個結點時，給它加右線索。（5）將根結點指針賦給保存前驅結點指針的變量，以便當訪問下一個結點時，此根結點成為前驅結點。54中序線索二叉樹55中序線索鏈表565.5.2二叉樹的線索化P113-114InThread函數(shù)：線索化樹的函數(shù)。InOrderThread函數(shù)：調用InThread函數(shù)，完成整棵樹的線索化。575.5.3線索二叉樹的操作查找前驅節(jié)點算法：P114pre函數(shù)查找后繼節(jié)點算法：P115succ函數(shù)遍歷算法（非遞歸）：P115ThTreeInOrder函數(shù)58二叉樹的遍歷練習59先序遍歷：1,2,4,8,9,5,10,11,3,6,12,7中序遍歷：8,4,9,2,10,5,11,1,12,6,3,7后序遍歷：8,9,4,10,11,5,2,12,6,7,3,1二叉樹的遍歷練習60先序遍歷：1,2,4,8,9,5,10,11,3,6,12,13,7,14,15中序遍歷：8,4,9,2,10,5,11,1,12,6,13,3,14,7,15后序遍歷：8,9,4,10,11,5,2,12,13,6,14,15,7,3,1

61中序遍歷的非遞歸算法ABCDEFGpiP->A(1)ABCDEFGpiP->AP->B(2)ABCDEFGpiP->AP->BP->C(3)p=NULLABCDEFGiP->AP->B訪問：C(4)62pABCDEFGiP->A訪問：CB(5)ABCDEFGiP->AP->D訪問：CBp(6)ABCDEFGiP->AP->DP->E訪問：CBp(7)ABCDEFGiP->AP->D訪問：CBEp(8)63ABCDEFGiP->AP->DP->G訪問：CBEP=NULL(9)ABCDEFGiP->A訪問：CBEGDp(11)ABCDEFGiP->AP->F訪問：CBEGDp(12)ABCDEFGiP->AP->D訪問：CBEGp(10)64ABCDEFGiP->A訪問：CBEGDFp=NULL(13)ABCDEFGi訪問：CBEGDFAp(14)ABCDEFGi訪問：CBEGDFAp=NULL(15)二叉樹遍歷操作應用舉例求二叉樹中以值為x的結點為根的子樹深度在二叉樹中求指定結點的層數(shù)。按先序序列建立二叉樹的二叉鏈表。求二叉樹的葉子數(shù)65二叉樹的應用（1）用二叉樹表示表達式的運算假定有表達式a+b*(c-d)-e/f，則可以用二叉樹表示如下：66二叉樹的應用（2）用二叉樹表示雙人比賽的所有可能結局。假定要舉行個人乒乓球比賽，比賽規(guī)則為三局兩勝制，則運動員A與運動員B的比賽的所有可能結局如圖67應用實例算術表達式的中綴、前綴和后綴表示法如果用一棵二叉樹表示一個表達式，那么使用先序、中序和后序遍歷二叉樹就分別得到表達式的前綴表示、中綴表示和后綴表示。68應用實例例1要求使用遞歸方法建立表達式（4*8+6/2）的二叉樹，并分別以先序、中序、后序的遞歸遍歷算法輸出表達式的前綴表示、中綴表示和后綴表示，最后計算該表達式的值。69分析：圖中的二叉樹使用中序遍歷得到的遍歷序列為：4*8+6/2；使用先序遍歷得到的遍歷序列為：+*48/62；使用后序遍歷得到的遍歷序列為：48*62/+。要建立表達式二叉樹，可以先建立根結點，然后遞歸建立左子樹和右子樹。要輸出表達式的前綴表示、中綴表示和后綴表示，只需要前序、中序和后序遍歷二叉樹并輸出遍歷結點的值。要計算表達式的值，需要遞歸計算左子樹和右子樹的值，然后利用根結點的運算符將這兩個值進行運算。704.7哈夫曼樹哈夫曼樹的基本概念構造哈夫曼樹哈夫曼編碼71哈夫曼樹的基本概念路徑：從樹中一個結點A到另一個結點B的分支構成這兩個結點之間的路徑。注意：這兩個結點之間必須存在前后繼關系，也就說，從結點A到結點B的路徑上所有結點都是結點B的祖先結點。路徑長度：從一個結點到另一個結點所經(jīng)過的分支個數(shù)，稱為路徑長度。結點的權：在實際應用中，很多結點都帶有一個有意義的（表示自己的地位）數(shù)，稱該數(shù)為結點的權。帶權路徑長度：從根節(jié)點到該結點的路徑長度乘以該結點的權，就得到該結點的帶權路徑長度。72哈夫曼樹的基本概念樹的帶權路徑長度：樹的帶權路徑長度是樹中所有葉子結點的帶權路徑長度之和，通常記作其中，n是樹中結點的個數(shù)，wk和lk分別是葉子結點的權和帶權路徑長度。哈夫曼樹：又稱最優(yōu)二叉樹，是指帶權路徑長度最小的二叉樹。它最早是在1952年由Haffman提出的，因此稱為哈夫曼樹。73哈夫曼樹的基本概念從結點B到結點G的路徑是結點序列B、E、G，路徑長度為2。假設結點D和結點G的權分別為3和4，則結點D的帶權路徑長度為2*3=6，結點G的帶權路徑長度為3*4=12。假設結點D、G、F的權分別為3、4、5，則樹的帶權路徑長度為3*2+4*3+5*2=28。74舉例假定有4個節(jié)點A、B、C、D，它們的權分別是8、6、3、1，則以這四個結點為葉子結點的二叉樹如圖。75（a）WPL=8*2+6*2+3*2+1*2=36（b）WPL=8*2+6*3+3*3+1*1=44（c）WPL=8*1+6*2+3*3+1*3=32舉例有些課程需要將最終的分數(shù)由百分制轉換成五級分制，語句如下：if(a<60) b="不及格";elseif(a<70) b="及格";elseif(a<80) b="中等";elseif(a<90) b="良好";else b="優(yōu)秀";76構造哈夫曼樹哈夫曼算法（1）根據(jù)給定的n個權值{w1,w2,…wn}，構成n棵二叉樹的集合F={T1,T2,…Tn}，其中每棵樹Ti都只有一個帶權為wi的根結點，其左右子樹為空。（2）在F中選兩個根結點的權最小的樹作為左右子樹構造一棵新的二叉樹，且設樹的根結點的權為左右子樹的根結點的權的和。（3）在F中刪除這兩個樹，把新得到的二叉樹加入F中。（4）重復第（2）步和第（3）步，直到F中只有一棵樹。得到的樹就是哈夫曼樹。77構造哈夫曼樹例進行五級分制轉換，概率分數(shù)0-5960-6970-7980-8990-100等級不及格及格中等良好優(yōu)秀概率0.050.150.400.300.1078構造哈夫曼樹構造過程79哈夫曼編碼8081

在遠程通訊中，要將待傳字符轉換成由二進制組成的字符串：設要傳送的字符為：ABACCDA若編碼為：A—00B—01 C—10D---11

00010010101100三、哈夫曼樹的應用(哈夫曼編碼)

若將編碼設計為長度不等的二進制編碼，即讓待傳字符串中出現(xiàn)次數(shù)較多的字符采用盡可能短的編碼，則轉換的二進制字符串便可能減少。8283設要傳送的字符為：ABACCDA若編碼為：A—0B—00 C—1D---01

關鍵：要設計長度不等的編碼，則必須使任一字符的編碼都不是另一個字符的編碼的前綴。這種編碼稱作前綴編碼。ABACCDA

000011010但：0000AAAAABABB重碼84設要傳送的字符為：ABACCDA若編碼為：A—0B—110 C—10D---111

0110010101110ACBD000111采用二叉樹設計二進制前綴編碼規(guī)定：左分支用“0”表示；右分支用“1”表示85譯碼過程：分解接收字符串：遇“0”向左，遇“1”向右；一旦到達葉子結點，則譯出一個字符，反復由根出發(fā)，直到譯碼完成。

0110010101110ACBD000111ABACCDA86求Huffman編碼：由葉子→根，若：（1）從左分支下去，則分支為“0”；（2）從右分支下去，則分支為“1”。

ACBD00011187例：已知某系統(tǒng)在通訊時，只出現(xiàn)C，A，S，T，B五種字符，它們出現(xiàn)的頻率依次為2，4，2，3，3，試設計Huffman編碼。

W（權）={2，4，2，3，3}，葉子結點個數(shù)n=5148464220001113301構造的Huffman樹TBACS88例：已知某系統(tǒng)在通訊時，只出現(xiàn)C，A，S，T，B五種字符，它們出現(xiàn)的頻率依次為2，4，2，3，3，試設計Huffman編碼。

由Huffman樹得Huffman編碼為：TBACS000110110111148464220001113301TBACS出現(xiàn)頻率越大的字符，其Huffman編碼越短。堆和堆排序堆排序在最壞情況下時間復雜度是O(nlog2n)，空間復雜性是O(1)。堆排序是借助于擬滿二叉樹來進行的。若擬滿二叉樹滿足條件:任意結點的值均不小于它的左子結點和右子結點的值(如果左子結點或右子結點存在)，則稱該擬滿樹為大堆。堆適合用順序存儲結構存儲。8990大堆例:(96，83，27，38，11，9)小堆例：(13，38，27，50，76，65，49，97)962791138831327384965765097可將堆序列看成完全二叉樹，則堆頂元素（完全二叉樹的根）必為序列中n個元素的最大或最小值堆的定義91

堆排序的基本思路：對一組待排序的