數據結構--二叉樹

《數據結構與算法》

廊坊師范學院數學與信息科學學院第五章二叉樹★★★★★樹型結構--實例:五子棋DEFBCA…...........…...........第五章二叉樹本章重點難點

重點：二叉樹的定義，性質，存儲結構以及相關的應用——遍歷，二叉搜索樹，堆優(yōu)先隊列，Huffman樹等

難點：二叉樹的遍歷算法及相關應用5.1二叉樹的概念●二叉樹遞歸定義：

由n(n>=0)個結點的有限集合，或為空集，或由一個根結點及兩棵互不相交的左右子樹組成，并且左右子樹都是二叉樹?！穸鏄涞奈宸N基本形態(tài)：空僅有根右子樹為空左子樹為空左右均非空5.1二叉樹的概念

相關概念根：二叉樹中唯一的起始結點父結點：非根結點的前驅結點孩子結點：二叉樹中，任何結點的后繼結點（左孩子，右孩子）兄弟結點：父結點相同的結點葉子結點：沒有子結點的結點內部結點：除葉子結點以外的非終端結點BDFEGCAABDFEGCA根BDA5.1二叉樹的概念

相關概念

度：一個結點的子樹數目

邊：父結點結點和子結點之間的連線

路徑：從一個結點到另外一個結點的邊的集合，邊的個數稱為路徑的長度

層數：從根結點到某個結點的路徑長度稱為結點的層數BDFEGCA二叉樹的度最多為20層1層2層3層5.1二叉樹的概念

兩種特殊形態(tài)的二叉樹---滿二叉樹，完全二叉樹BDFEGCA

滿二叉樹：所有層數的結點都達到最大值的二叉樹（與書中不同）1231145891213671014155.1二叉樹的概念

兩種特殊形態(tài)的二叉樹---滿二叉樹，完全二叉樹BDFEGCA

滿二叉樹：除最后一層外，每一層上的所有結點都有兩個子結點

1231145891213671014155.1二叉樹的概念

兩種特殊形態(tài)的二叉樹---滿二叉樹，完全二叉樹

完全二叉樹：樹中所含的n個結點和滿二叉樹中編號為1--n的結點一一對應1234567滿二叉樹12345完全二叉樹5.1二叉樹的概念

兩種特殊形態(tài)的二叉樹---滿二叉樹，完全二叉樹

完全二叉樹：樹中所含的n個結點和滿二叉樹中編號為1--n的結點一一對應1234567滿二叉樹12345完全二叉樹5.1二叉樹的概念

兩種特殊形態(tài)的二叉樹---滿二叉樹，完全二叉樹12345完全二叉樹

完全二叉樹特點：

只有最下面兩層的結點度數小于2

最下面一層的結點都集中在該層最左邊連續(xù)的位置上5.1二叉樹的概念

第三種特殊的二叉樹---正則二叉樹正則二叉樹

正則二叉樹：若二叉樹的所有結點，或者是樹葉，或者左右子樹均非空，即除了葉子結點就是度為2的結點12345675.1二叉樹的概念●二叉樹的主要性質

●性質1：二叉樹中第i層上最多有2i個結點0層1層2層BDFEGCA3層HGJILKNM數學歸納法證明：1.當i=0時：成立2.假設所有的j(0<j<i)層都成立3.j=i時也成立i-1層:2i-1i層：2×2i-1

=

2i

5.1二叉樹的概念●二叉樹的主要性質

●性質2：深度為k的二叉樹，至多有2k+1-1個結點深度：二叉樹中層數最大的葉結點的層數0層1層2層BDFEGCA3層HGJILKNM1+2+4+8+…..2k等比數列的求和公式：

a1-an*q1-2k*21-q1-22k+1-1==證明：由性質1可知：第i層的最大結點數為2i，因此：

∑2i=2k+1-1ki=05.1二叉樹的概念●二叉樹的主要性質

●性質3：任何一棵二叉樹，若其終端結點數為n0，度為2的結點數為n2，則n0=n2+1BDFGCAG證明：(1)總結點數為

n=n0+n1+n2(2)除根結點外，每個結點都有一個邊e進入

n=e+1(3)邊e又是由度為1或2的點射出，因此

e=n1+2n2(4)由（2）（3）

n=n1+2n2+1(5)由（4）-（1）可得

n0=n2+15.1二叉樹的概念●二叉樹的主要性質

●性質3：任何一棵二叉樹，若其終端結點數為n0，度為2的結點數為n2，則n0=n2+1BDFGCAG證明：(1)總結點數為

n=n0+n1+n2(2)除根結點外，每個結點都有一個邊e進入

n=e+1(3)邊e又是由度為1或2的點射出，因此

e=n1+2n2(4)由（2）（3）

n=n1+2n2+1(5)由（4）-（1）可得

n0=n2+15.1二叉樹的概念●二叉樹的主要性質

●性質3：任何一棵二叉樹，若其終端結點數為n0，度為2的結點數為n2，則n0=n2+1BDFGCAG證明：(1)總結點數為

n=n0+n1+n2(2)除根結點外，每個結點都有一個邊e進入

n=e+1(3)邊e又是由度為1或2的點射出，因此

e=n1+2n2(4)由（2）（3）

n=n1+2n2+1(5)由（4）-（1）可得

n0=n2+15.1二叉樹的概念●二叉樹的主要性質

●性質3：任何一棵二叉樹，若其終端結點數為n0，度為2的結點數為n2，則n0=n2+1BDFGCAG證明：(1)總結點數為

n=n0+n1+n2(2)除根結點外，每個結點都有一個邊e進入

n=e+1(3)邊e又是由度為1或2的點射出，因此

e=n1+2n2(4)由（2）（3）

n=n1+2n2+1(5)由（4）-（1）可得

n0=n2+15.1二叉樹的概念●二叉樹的主要性質

●性質3：任何一棵二叉樹，若其終端結點數為n0，度為2的結點數為n2，則n0=n2+1BDFGCAG證明：(1)總結點數為

n=n0+n1+n2(2)除根結點外，每個結點都有一個邊e進入

n=e+1(3)邊e又是由度為1或2的點射出，因此

e=n1+2n2(4)由（2）（3）

n=n1+2n2+1(5)由（4）-（1）可得

n0=n2+15.1二叉樹的概念●二叉樹的主要性質

●性質4：正則二叉樹定理：非空正則二叉樹樹葉數目等于其分支結點數加1證明：可由性質3直接推出性質3：n0=n2+1BDFEGCA5.1二叉樹的概念●二叉樹的主要性質

●性質5：正則二叉樹定理推論：一個非空二叉樹的空子樹數目等于其結點數加1證明：由性質4可推出BDGCAFE5.1二叉樹的概念●二叉樹的主要性質

●性質6：有n(n>0)個結點的完全二叉樹的高度為「log2(n+1),深度為「log2(n+1)-1

高度:二叉樹中最大葉結點的層數+1123450層1層2層高度=3,深度=2證明：由性質2（深度為k的二叉樹，至多有2k+1-1個結點）可知，高度為h(k+1)的二叉樹，其結點個數n滿足：

2h-1-1<n<=2h-12h-1<n+1<=2h取對數得到：

h-1<log2(n+1)<=h因為h是整數，所以

h=log2(n+1)

上取整：大于該數的最小整數3.4->45.1二叉樹的概念●二叉樹的主要性質

●性質7：具有n個結點的完全二叉樹，結點按層次由左到右編號，則對任一結點i（0<=i<=n-1)有：（2）2i+1<=n-1i的左孩子結點是2i+12i+2<=n-1i的右孩子結點是2i+2（1）i=0i是根結點

i>0其父結點=（i-1）/2（3）0<i<ni為偶數時，其左兄弟結點是i-1i+1<ni為奇數時，其右兄弟結點是i+101234562k-22i+22k-1i

2k+1-12k+12i+32i+4i+12k+1-22i+12k+2-32k+2-2K-1層K層K+1層………..………..………..………..5.2二叉樹的遍歷（周游）●二叉樹遍歷：

按照一定的順序依次訪問樹中的所有結點，并使得每個結點僅被訪問一次。

遍歷的目的：初始化一棵二叉樹在樹中查找具有某種特征的結點對樹中全部結點逐一進行某種處理。5.2二叉樹的遍歷（周游）遍歷分類：深度優(yōu)先：盡可能沿分支結點向深度方向遍歷廣度優(yōu)先：按二叉樹的層次進行遍歷

BDFGCAGTLR—先（根）序遍歷，LTR—中（根）序遍歷，LRT—后（根）序遍歷。尋找遍歷二叉樹的規(guī)律二叉樹基本組成單元：根結點T、左子樹Ｌ和右子樹Ｒ。遍歷二叉樹有TLR、LTR、LRT、TRL、RTL、RLT六種方案。規(guī)定先左后右，則只有三種：T左子樹右子樹根結點5.2二叉樹的遍歷（周游）深度優(yōu)先遍歷：DLR—先（根）序遍歷5.2二叉樹的遍歷（周游）深度優(yōu)先遍歷：

（1）訪問根結點；

（2）先序遍歷左子樹；

（3）

先序遍歷右子樹；ADBCDLRADLRDLR>B>>D>>CDLR先序遍歷序列：ABDC先序遍歷:ADBCLDRBLDRLDR>A>>D>>CLDR中序遍歷序列：BDAC中序遍歷:ADBCLRDLRDLRD>A>>D>>CLRD后序遍歷序列：DBCA后序遍歷:B第五章二叉樹內容回顧二叉樹的概念空僅有根右子樹為空左子樹為空左右均非空二叉樹的性質滿二叉樹，完全二叉樹，正則二叉樹0256134滿二叉樹完全二叉樹0213正則二叉樹02341第五章二叉樹內容回顧二叉樹的概念二叉樹的性質滿二叉樹，完全二叉樹，正則二叉樹012103478111256913140層1層2層3層2i2i+1-1n0=n2+1....「log2(n+1)2i+1;2i+2第五章二叉樹內容回顧二叉樹的概念二叉樹的性質滿二叉樹，完全二叉樹，正則二叉樹二叉樹的遍歷深度優(yōu)先廣度優(yōu)先BDFGCAG根二叉樹的深度優(yōu)先遍歷根：root左子樹：left右子樹：rightTLRTLR—先（根）序遍歷LTR—中（根）序遍歷LRT—后（根）序遍歷規(guī)定遍歷順序自左至右：創(chuàng)建、復制一棵二叉樹遍歷一棵二叉搜索樹可以得到有序序列求樹的高度，葉結點的數量BDFEGCA先序序列：二叉樹的遍歷練習ABCDEGFBDFEGCA先序序列：二叉樹的遍歷練習ABCDEGFBDFEGCA先序序列：二叉樹的遍歷練習ABCDEGFBDFEGCA先序序列：二叉樹的遍歷練習ABCDEGFBDFEGCA先序序列：二叉樹的遍歷練習ABCDEGFBDFEGCA先序序列：二叉樹的遍歷練習ABCDEGFBDFEGCA先序序列：二叉樹的遍歷練習ABCDEGFBDFEGCA先序序列：二叉樹的遍歷練習ABCDEGFBDFEGCA先序序列：二叉樹的遍歷練習ABCDEGF中序序列：CBEGDFABDFEGCA先序序列：二叉樹的遍歷練習ABCDEGF中序序列：CBEGDFABDFEGCA先序序列：二叉樹的遍歷練習ABCDEGF中序序列：CBEGDFABDFEGCA先序序列：二叉樹的遍歷練習ABCDEGF中序序列：CBEGDFABDFEGCA先序序列：二叉樹的遍歷練習ABCDEGF中序序列：CBEGDFABDFEGCA先序序列：二叉樹的遍歷練習ABCDEGF中序序列：CBEGDFABDFEGCA先序序列：二叉樹的遍歷練習ABCDEGF中序序列：CBEGDFABDFEGCA先序序列：二叉樹的遍歷練習ABCDEGF中序序列：CBEGDFABDFEGCA先序序列：二叉樹的遍歷練習ABCDEGF中序序列：CBEGDFA后序序列：CGEFDBABDFEGCA先序序列：二叉樹的遍歷練習ABCDEGF中序序列：CBEGDFA后序序列：CGEFDBABDFEGCA先序序列：二叉樹的遍歷練習ABCDEGF中序序列：CBEGDFA后序序列：CGEFDBABDFEGCA先序序列：二叉樹的遍歷練習ABCDEGF中序序列：CBEGDFA后序序列：CGEFDBABDFEGCA先序序列：二叉樹的遍歷練習ABCDEGF中序序列：CBEGDFA后序序列：CGEFDBABDFEGCA先序序列：二叉樹的遍歷練習ABCDEGF中序序列：CBEGDFA后序序列：CGEFDBABDFEGCA先序序列：二叉樹的遍歷練習ABCDEGF中序序列：CBEGDFA后序序列：CGEFDBABDFEGCA先序序列：二叉樹的遍歷練習ABCDEGF中序序列：CBEGDFA后序序列：CGEFDBA5.2二叉樹的遍歷（周游）廣度優(yōu)先遍歷：BDFEGCA廣度優(yōu)先遍歷序列：

ABCDEFG內存使用模擬：1.不同任務的數據申請使用內存2.部分程序結束，此時內存可用空間已經呈不連續(xù)狀態(tài)5.3二叉樹的存儲結構數據的物理存儲結構：連續(xù)存儲：占用一片連續(xù)的存儲區(qū)域優(yōu)點：隨機讀取，存儲密度大缺點：插入和刪除元素費時，不適合存儲數據量無法預知的數據5.3二叉樹的存儲結構數據的物理存儲結構：連續(xù)存儲：占用一片連續(xù)的存儲區(qū)域優(yōu)點：隨機讀取，存儲密度大缺點：插入和刪除元素費時，不適合存儲數據量無法預知的數據5.3二叉樹的存儲結構數據的物理存儲結構：連續(xù)存儲：占用一片連續(xù)的存儲區(qū)域優(yōu)點：隨機讀取，存儲密度大缺點：插入和刪除元素費時，不適合存儲數據量無法預知的數據5.3二叉樹的存儲結構數據的物理存儲結構：

鏈式存儲：使用不連續(xù)的存儲區(qū)域，使用附加的指針信息，體現其邏輯關系優(yōu)點：適于動態(tài)變化的數據結構缺點：隨機查找困難，存儲密度小5.3二叉樹的存儲結構數據域指針域數據的物理存儲結構：

鏈式存儲：使用不連續(xù)的存儲區(qū)域，使用附加的指針信息，體現其邏輯關系優(yōu)點：適于動態(tài)變化的數據結構缺點：隨機查找困難，存儲密度小5.3二叉樹的存儲結構5.3二叉樹的存儲結構二叉樹的順序存儲結構：

用一組地址連續(xù)的存儲單元，依次按滿二叉樹的結點編號位序，存儲二叉樹的結點。特點：適用于完全二叉樹。否則可能對存儲空間造成極大的浪費，比如單支樹。abcdefg5.3二叉樹的存儲結構順序存儲結構：完全二叉樹0a1b2c3d4e5f6g1234560順序方式是完全二叉樹存儲的最簡單，最節(jié)省空間的方式abcdefg5.3二叉樹的存儲結構順序存儲結構：非完全二叉樹abcgg‘/’‘/’‘/’cba1234560非完全二叉樹順序存儲時，會浪費一定的空間3’/’4’/’5’/’0a1b2c6g5.3二叉樹的存儲結構鏈式存儲結構：二叉鏈表：從任何一個結點都可找到其左右孩子結點lChilddata0rChildlChilddata1rChildlChilddata2rChildRoot缺點：很難獲取某個結點的父結點5.3二叉樹的存儲結構鏈式存儲結構：三叉鏈表：從任何一個結點都可找到其父結點和左右孩子結點lChildparentdatarChildlChildparentdatarChildlChildparentdatarChildnullRoot5.3二叉樹的存儲結構鏈式存儲結構的程序實現：結點類定義：//樹結點類的定義template<classT>classTreeNode{public：

Tdata;TreeNode*lchild;//左，右子樹

TreeNode*rchild;public:TreeNode(){ lchild=NULL; rchild=NULL;}};lChilddata0rChild5.3二叉樹的存儲結構鏈式存儲結構的程序實現：二叉樹類定義：//樹類的定義template<classT>classBinTree{private: TreeNode<T>*root;//樹的根結點public: BinTree() { root=NULL; } ~BinTree() { Destroy(root); }rootnull5.3二叉樹的存儲結構鏈式存儲結構的程序實現：二叉樹類定義：//樹類的定義template<classT>classBinTree{private: TreeNode<T>*root;//樹的根結點public: BinTree() { root=NULL; } ~BinTree() { Destroy(root); }BDCAroot//***************創(chuàng)建二叉樹,主過程

voidCreatTree(){

cout<<"請按前序遍歷輸入結點元素值，空節(jié)點用/代替:"<<endl; CreatTree(root);}//***************創(chuàng)建二叉樹,子過程voidCreatTree(TreeNode<T>*&p1){Tc; cin>>c; TreeNode<T>*point;point=newTreeNode<T>; if(c!='/') { p1=point;point->data=c;CreatTree(point->lchild);CreatTree(point->rchild); }}創(chuàng)建二叉樹BDCAroot‘/’‘/’‘/’‘/’‘/’

//先序遍歷二叉樹

voidPreTree(){ PreTree(root);}voidPreTree(TreeNode<T>*point){ if(point!=NULL) { cout<<""<<point->data;PreTree(point->lchild);PreTree(point->rchild); }}BDCAroot‘/’‘/’‘/’‘/’‘/’

//先序遍歷二叉樹

voidPreTree(){ PreTree(root);}voidPreTree(TreeNode<T>*point){ if(point!=NULL) { cout<<""<<point->data;PreTree(point->lchild);PreTree(point->rchild); }}BDCAroot‘/’‘/’‘/’‘/’‘/’//中序遍歷二叉樹voidInoTree(){ InoTree(root);}voidInoTree(TreeNode<T>*point){

if(point!=NULL)

{

InoTree(point->lchild);

cout<<""<<point->data;

InoTree(point->rchild);

}}BDCAroot‘/’‘/’‘/’‘/’‘/’//后序遍歷二叉樹

voidPosTree(){ PosTree(root);}voidPosTree(TreeNode<T>*point){if(point!=NULL){PosTree(point->lchild);

PosTree(point->rchild);cout<<""<<point->data;}}BDCAroot‘/’‘/’‘/’‘/’‘/’#include<iostream>#include"BinTree.h"usingnamespacestd;//主函數voidmain(){BinTree<char>BinTreeOPP;BinTreeOPP.CreatTree();cout<<"先序："<<endl;BinTreeOPP.PreTree();cout<<endl;cout<<"中序："<<endl;BinTreeOPP.InoTree();cout<<endl;cout<<"后序："<<endl;BinTreeOPP.levelorder();cout<<endl;}BDCAroot‘/’‘/’‘/’‘/’‘/’《數據結構與算法》

廊坊師范學院數學與信息科學學院授課教師：崔業(yè)勤第五章二叉樹★★★★★根二叉樹的遍歷TLRTLR—先（根）序遍歷LTR—中（根）序遍歷LRT—后（根）序遍歷規(guī)定遍歷順序自左至右：內容回顧根二叉樹的遍歷TLRTLR—先（根）序遍歷LTR—中（根）序遍歷LRT—后（根）序遍歷規(guī)定遍歷順序自左至右：內容回顧根LR二叉樹的遍歷TLR—先（根）序遍歷規(guī)定遍歷順序自左至右：根TL根LRBDFECALTR—中（根）序遍歷LRT—后（根）序遍歷ABDEFCBEDFACEFDBCA中序遍歷一棵二叉搜索樹可以得到所有結點的有序序列二叉搜索樹的用途：快速查找特定的元素5.4二叉搜索樹構造二叉樹搜索的過程就是給數據排序的過程，中序遍歷可得到有序序列二分法思想二叉搜索樹：其內部結點的左子樹上所有結點的值，均小于它的根結點，右子樹上所有結點的值，均大于它的根結點35403878942356515.4二叉搜索樹構造二叉搜索樹：從二叉樹的根結點開始創(chuàng)建比根節(jié)點小的值作為左子樹的根，比根結點大的值作為右子樹的根重復值不允許插入56,34,78,4,7,98,64563478479864練習5.4二叉搜索樹二叉搜索樹插入結點：（同創(chuàng)建）25二叉搜索樹刪除結點：若該結點無左子樹，則直接用該結點的右子樹的根代替該結點56347847986470765.4二叉搜索樹二叉搜索樹插入結點：（同創(chuàng)建）56347849864725二叉搜索樹刪除結點：若該結點無左子樹，則直接用該結點的右子樹的根代替該結點4若該結點有左子樹，則在左子樹中找到最大的結點代替它70765.4二叉搜索樹二叉搜索樹插入結點：（同創(chuàng)建）56347849864725二叉搜索樹刪除結點：若該結點無左子樹，則直接用該結點的右子樹的根代替該結點4若該結點有左子樹，則在左子樹中找到最大的結點代替它707856765.4二叉搜索樹二叉搜索樹插入結點：（同創(chuàng)建）56347849864725二叉搜索樹刪除結點：若該結點無左子樹，則直接用該結點的右子樹的根代替該結點4若該結點有左子樹，則在左子樹中找到最大的結點代替它70785676左子樹中的最大結點：1.該子樹中沒有右子樹，根既是最大2.該子樹中有右子樹，則順著右子樹分支找到的最后一個結點為最大5.4二叉搜索樹3422789864736刪除結點練習：6146992278687263365.4二叉搜索樹二叉搜索樹特點：是一種插入，刪除，檢索效率都較高的數據組織方法123456788490939901234567線性順序結構：檢索快，插入刪除效率低同其它數據組織方法的比較：

線性鏈式結構：插入刪除快，檢索效率低3456788490939912堆的用途：

在一組數據中快速查找最大值或最小值堆：是一種特殊的完全二叉樹，其內部結點的值均不大于（或小于）其左右結點的值5.5堆與優(yōu)先隊列42345345767899958最小堆9823451418339911最大堆

局部有序士兵1士兵3********公主***士兵2誰先救走了公主？構造最小堆：按層次結構放置各個元素，構造一棵完全二叉樹從最后一個非終端結點即無序序列中第

n/2

個元素開始，將該結點的左右子結點中較小的值與該結點互換位置。依次調整到根結點，在調整過程中，要注意維持最小堆的特性5.5堆與優(yōu)先隊列98234514183399119823451418339911構造最小堆：按層次結構放置各個元素，構造一棵完全二叉樹從最后一個非終端結點即無序序列中第

n/2

個元素開始，將該結點的左右子結點中較小的值與該結點互換位置。依次調整到根結點，在調整過程中，要注意維持最小堆的特性5.5堆與優(yōu)先隊列98234514183399119823451418339911構造最小堆：按層次結構放置各個元素，構造一棵完全二叉樹從最后一個非終端結點即無序序列中第

n/2

個元素開始，將該結點的左右子結點中較小的值與該結點互換位置。依次調整到根結點，在調整過程中，要注意維持最小堆的特性5.5堆與優(yōu)先隊列98234514183399119823451418339911構造最小堆：按層次結構放置各個元素，構造一棵完全二叉樹從最后一個非終端結點即無序序列中第

n/2

個元素開始，將該結點的左右子結點中較小的值與該結點互換位置。依次調整到根結點，在調整過程中，要注意維持最小堆的特性5.5堆與優(yōu)先隊列98234514183399119823451418339911構造最小堆：按層次結構放置各個元素，構造一棵完全二叉樹從最后一個非終端結點即無序序列中第

n/2

個元素開始，將該結點的左右子結點中較小的值與該結點互換位置。依次調整到根結點，在調整過程中，要注意維持最小堆的特性5.5堆與優(yōu)先隊列98234514183399119823451418339911構造最小堆：按層次結構放置各個元素，構造一棵完全二叉樹從最后一個非終端結點即無序序列中第

n/2

個元素開始，將該結點的左右子結點中較小的值與該結點互換位置。依次調整到根結點，在調整過程中，要注意維持最小堆的特性5.5堆與優(yōu)先隊列98234514183399119823451418339911構造最小堆：按層次結構放置各個元素，構造一棵完全二叉樹從最后一個非終端結點即無序序列中第

n/2

個元素開始，將該結點的左右子結點中較小的值與該結點互換位置。依次調整到根結點，在調整過程中，要注意維持最小堆的特性5.5堆與優(yōu)先隊列98234514183399119823451418339911堆插入結點：先將該元素排列到最后按堆性質調整元素到合適位置5.5堆與優(yōu)先隊列98234514183399116堆插入結點：先將該元素排列到最后按堆性質調整元素到合適位置5.5堆與優(yōu)先隊列98234514183399116堆插入結點：先將該元素排列到最后按堆性質調整元素到合適位置5.5堆與優(yōu)先隊列98234514183399116堆插入結點：先將該元素排列到最后按堆性質調整元素到合適位置5.5堆與優(yōu)先隊列98234514183399116堆刪除結點：先將最后一個元素調整到刪除元素位置按堆性質依次向下調整堆插入結點：先將該元素排列到最后按堆性質調整元素到合適位置5.5堆與優(yōu)先隊列982345143399116堆刪除結點：先將最后一個元素調整到刪除元素位置按堆性質依次向下調整18堆插入結點：先將該元素排列到最后按堆性質調整元素到合適位置5.5堆與優(yōu)先隊列98234514339911堆刪除結點：先將最后一個元素調整到刪除元素位置按堆性質依次向下調整18堆練習：5.5堆與優(yōu)先隊列18214724191339451845139194732124構造最小堆3451824191347921插入結點4堆練習：5.5堆與優(yōu)先隊列1821472419133945構造最小堆3451824191347921插入結點434518249134742119//創(chuàng)建二叉搜索樹voidcreatbst(){creatbst(root);}voidcreatbst(TreeNode<T>*&root){ Tn; cin>>n;TreeNode<T>*point=root;TreeNode<T>*newpoint; newpoint=newTreeNode<T>; newpoint->data=n; if(root==NULL) { root=newpoint;return；} while(point!=NULL){//關鍵字相同的元素不予處理 if(newpoint->data==point->data)

return; elseif(newpoint->data<point->data){

if(point->lchild==NULL){

point->lchild=newpoint;

return;