數(shù)據(jù)結構中的樹

1樹與二叉樹2樹和森林的概念兩種樹：自由樹與有根樹。

自由樹： 一棵自由樹Tf

可定義為一個二元組Tf

=(V,E)

其中V={v1,...,vn}

是由n(n＞0)個元素組成的有限非空集合，稱為頂點集合。E={(vi,vj)|vi,vj

V,1≤i,j≤n}

是n-1個序對的集合，稱為邊集合，E

中的元素(vi,vj）稱為邊或分支。3自由樹有根樹： 一棵有根樹T，簡稱為樹，它是n(n≥0)

個結點的有限集合。當n=0時，T稱為空樹；否則，T

是非空樹，記作

4r是一個特定的稱為根(root)的結點，它只有直接后繼，但沒有直接前驅；根以外的其他結點劃分為m(m

0)個互不相交的有限集合T1,T2,…,Tm，每個集合又是一棵樹，并且稱之為根的子樹。每棵子樹的根結點有且僅有一個直接前驅，但可以有0個或多個直接后繼。5樹的基本術語子女：若結點的子樹非空，結點子樹的根即為該結點的子女。雙親：若結點有子女，該結點是子女雙親。1層2層4層3層depth=4DACBIJHGFEMLK6兄弟：同一結點的子女互稱為兄弟。度：結點的子女個數(shù)即為該結點的度；樹中各個結點的度的最大值稱為樹的度。分支結點：度不為0的結點即為分支結點，亦稱為非終端結點。葉結點：度為0的結點即為葉結點，亦稱為終端結點。祖先：某結點到根結點的路徑上的各個結點都是該結點的祖先。子孫：某結點的所有下屬結點，都是該結點的子孫。7結點的層次：規(guī)定根結點在第一層，其子女結點的層次等于它的層次加一。以下類推。深度：結點的深度即為結點的層次；離根最遠結點的層次即為樹的深度。1層2層4層3層depth=4DACBIJHGFEMLK8高度：規(guī)定葉結點的高度為1，其雙親結點的高度等于它的高度加一。有序樹：樹中結點的各棵子樹T0,T1,…是有次序的，即為有序樹。無序樹：樹中結點的各棵子樹之間的次序是不重要的，可以互相交換位置。森林：森林是m（m≥0）棵樹的集合。

9樹的抽象數(shù)據(jù)類型template<classT>classTree{//對象:樹是由n(≥0)個結點組成的有限集合。在//類界面中的position是樹中結點的地址。在順序//存儲方式下是下標型,在鏈表存儲方式下是指針//型。T是樹結點中存放數(shù)據(jù)的類型,要求所有結//點的數(shù)據(jù)類型都是一致的。public:Tree();

~Tree();

10BuildRoot(constT&value);

//建立樹的根結點

positionFirstChild(positionp);

//返回

p第一個子女地址,無子女返回0 positionNextSibling(positionp);

//返回p下一兄弟地址,若無下一兄弟返回0 positionParent(positionp);

//返回

p雙親結點地址,若

p為根返回0TGetData(positionp);

//返回結點

p中存放的值

boolInsertChild(positionp,T&value);

//在結點

p下插入值為

value的新子女,若插

//入失敗,函數(shù)返回false,否則返回true11

boolDeleteChild(positionp,inti);

//刪除結點p

的第

i

個子女及其全部子孫結

//點,若刪除失敗,則返回false,否則返回true

voidDeleteSubTree(positiont);

//刪除以t

為根結點的子樹

boolIsEmpty();

//判樹空否,若空則返回true,否則返回false

voidTraversal(positionp);

//遍歷以

p

為根的子樹};

12二叉樹的五種不同形態(tài)LLRR二叉樹(BinaryTree)二叉樹的定義

一棵二叉樹是結點的一個有限集合，該集合或者為空，或者是由一個根結點加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成。13二叉樹的性質性質1

若二叉樹結點的層次從1開始,則在二叉樹的第i層最多有

2i-1

個結點。(i≥1)

[證明用數(shù)學歸納法]性質2

深度為k

的二叉樹最少有k

個結點，最多有2k-1個結點。(k≥1)

因為每一層最少要有1個結點，因此，最少結點數(shù)為k。最多結點個數(shù)借助性質1：用求等比級數(shù)前k項和的公式20+21+22+…+2k-1=2k-114性質3

對任何一棵二叉樹，如果其葉結點有n0個,度為2的非葉結點有n2個,則有n0＝n2＋1

若設度為1的結點有n1個，總結點數(shù)為n， 總邊數(shù)為e，則根據(jù)二叉樹的定義，

n=n0+n1+n2

e

=2n2+n1=n-1

因此，有2n2+n1=n0+n1+n2-1

n2=n0-1n0=n2+115定義1

滿二叉樹(FullBinaryTree)

定義2

完全二叉樹(CompleteBinaryTree)─若設二叉樹的深度為k，則共有k層。除第k層外，其它各層(1～k-1)的結點數(shù)都達到最大個數(shù)，第k層從右向左連續(xù)缺若干結點，這就是完全二叉樹。16性質4

具有n(n≥0)個結點的完全二叉樹的深度為log2(n+1)

設完全二叉樹的深度為k，則有

2k-1-1<n

≤2k-1

變形2k-1<n+1≤2k

取對數(shù)

k-1<log2(n+1)≤k

有

log2(n+1)=k上面k-1層結點數(shù)包括第k層的最大結點數(shù)23-124-117性質5

如將一棵有n個結點的完全二叉樹自頂向下，同一層自左向右連續(xù)給結點編號1,2,…,n，則有以下關系：

若i=1,則i無雙親若i>1,則i的雙親為i／2若2*i<=n,則i的左子女為

2*i， 若2*i+1<=n,則i的右子女為2*i+1若i為奇數(shù),且i!=1,

則其左兄弟為i-1,若若

i為偶數(shù),且i!=n,

則其右兄弟為i+11234856791018二叉樹的抽象數(shù)據(jù)類型template<classT>classBinaryTree{//對象:結點的有限集合,二叉樹是有序樹public:

BinaryTree(); //構造函數(shù)

BinaryTree(BinTreeNode<T>*lch,

BinTreeNode<T>*rch,Titem);

//構造函數(shù),以item為根,lch和rch為左、右子

//樹構造一棵二叉樹

intDepth(); //求樹深度

intSize(); //求樹中結點個數(shù)19

boolIsEmpty(); //判二叉樹空否？

BinTreeNode<T>*Parent(BinTreeNode<T>*t);

//求結點t的雙親

BinTreeNode<T>*LeftChild

(BinTreeNode<T>*t);

//求結點t的左子女

BinTreeNode<T>*RightChild(BinTreeNode<T>*t);

//求結點t的右子女

boolInsert

(Titem); //在樹中插入新元素

boolRemove(Titem); //在樹中刪除元素

boolFind(T&item); //判斷item是否在樹中

boolgetData(T&item); //取得結點數(shù)據(jù)20

BinTreeNode<T>*getRoot(); //取根

voidpreOrder(void(*visit)(BinTreeNode<T>*t)); //前序遍歷,visit是訪問函數(shù)

voidinOrder(void(*visit)(BinTreeNode<T>*t));

//中序遍歷,visit是訪問函數(shù)

voidpostOrder(void(*visit)(BinTreeNode<T>*t));

//后序遍歷,(*visit)是訪問函數(shù)

voidlevelOrder(void(*visit)(BinTreeNode<T>*t));

//層次序遍歷,visit是訪問函數(shù)};21完全二叉樹一般二叉樹的順序表示的順序表示二叉樹的順序表示1123456789

10

1412346789

12

14248910567312376489125101113221371531極端情形:只有右單支的二叉樹137153123二叉樹結點定義：每個結點有3個數(shù)據(jù)成員，data域存儲結點數(shù)據(jù)，leftChild和rightChild分別存放指向左子女和右子女的指針。leftChilddatarightChilddataleftChildrightChild二叉鏈表二叉樹的鏈表表示24leftChilddataparentrightChildparentdataleftChildrightChild三叉鏈表二叉樹的鏈表表示每個結點增加一個指向雙親的指針parent，使得查找雙親也很方便。25二叉樹鏈表表示的示例AAABBBCCCDDDFFFEEErootrootroot26二叉樹遍歷二叉樹的遍歷就是按某種次序訪問樹中的結點，要求每個結點訪問一次且僅訪問一次。設訪問根結點記作

V

遍歷根的左子樹記作

L

遍歷根的右子樹記作

R則可能的遍歷次序有

前序VLR

鏡像VRL

中序

LVR

鏡像RVL

后序LRV

鏡像RLV27中序遍歷二叉樹算法的框架是：若二叉樹為空，則空操作；否則中序遍歷左子樹(L)；訪問根結點(V)；中序遍歷右子樹(R)。遍歷結果

a+b*c

-

d

-

e/f中序遍歷(InorderTraversal)--/+*abcdef28二叉樹遞歸的中序遍歷算法template<classT>voidBinaryTree<T>::InOrder(BinTreeNode<T>*subTree,void(*visit)(BinTreeNode<T>*t)){if(subTree!=NULL){

InOrder(subTree->leftChild,visit);

//遍歷左子樹

visit(subTree); //訪問根結點

InOrder(subTree->rightChild,visit);

//遍歷右子樹

}};29前序遍歷二叉樹算法的框架是：若二叉樹為空，則空操作；否則訪問根結點(V)；前序遍歷左子樹(L)；前序遍歷右子樹(R)。遍歷結果

-+a*b

-

cd/ef前序遍歷(PreorderTraversal)--/+*abcdef30二叉樹遞歸的前序遍歷算法template<classT>voidBinaryTree<T>::PreOrder(BinTreeNode<T>*subTree,void(*visit)

(BinTreeNode<T>*t)){if(subTree!=NULL){

visit(subTree); //訪問根結點

PreOrder(subTree->leftChild,visit);

//遍歷左子樹

PreOrder(subTree->rightChild,visit);

//遍歷右子樹

}};31后序遍歷二叉樹算法的框架是：若二叉樹為空，則空操作；否則后序遍歷左子樹(L)；后序遍歷右子樹(R)；訪問根結點(V)。遍歷結果

abcd

-*+ef/-后序遍歷(PostorderTraversal)--/+*abcdef32二叉樹遞歸的后序遍歷算法template<classT>voidBinaryTree<T>::PostOrder(BinTreeNode<T>*subTree,void(*visit)(BinTreeNode<T>*t){if(subTree!=NULL){

PostOrder(subTree->leftChild,visit);

//遍歷左子樹

PostOrder(subTree->rightChild,visit); //遍歷右子樹

visit(subTree); //訪問根結點

}};33template<classT>intBinaryTree<T>::Size(BinTreeNode<T>*

subTree)const{//私有函數(shù)：利用二叉樹后序遍歷算法計算二叉//樹的結點個數(shù)

if(subTree==NULL)return0; //空樹

elsereturn1+Size(subTree->leftChild)

+

Size(subTree->rightChild);};應用二叉樹遍歷的事例34template<classT>intBinaryTree<T>::Height(BinTreeNode<T>*subTree)const{//私有函數(shù)：利用二叉樹后序遍歷算法計算二叉//樹的高度或深度

if(subTree==NULL)return0; //空樹高度為0 else{ inti=Height(subTree->leftChild);intj=Height(subTree->rightChild); return(i<j)?j+1:i+1; };35利用二叉樹前序遍歷建立二叉樹以遞歸方式建立二叉樹。輸入結點值的順序必須對應二叉樹結點前序遍歷的順序。并約定以輸入序列中不可能出現(xiàn)的值作為空結點的值以結束遞歸,此值在RefValue中。例如用“@”或用“-1”表示字符序列或正整數(shù)序列空結點。36層次序遍歷二叉樹就是從根結點開始，按層次逐層遍歷，如圖：遍歷順序abcdef--+/*層次序遍歷二叉樹的算法37這種遍歷需要使用一個先進先出的隊列，在處理上一層時，將其下一層的結點直接進到隊列（的隊尾）。在上一層結點遍歷完后，下一層結點正好處于隊列的隊頭，可以繼續(xù)訪問它們。算法是非遞歸的。38abcdeQa訪問a,進隊Qa出隊訪問b,進隊訪問c,進隊bcQb出隊訪問d,進隊cdQc出隊訪問e,進隊deQd出隊eQe出隊39層次序遍歷的（非遞歸）算法template<classT>voidBinaryTree<T>::levelOrder(void(*visit)(BinTreeNode<T>*t)){if(root==NULL)return;

Queue<BinTreeNode<T>*>Q;

BinTreeNode<T>*p=root;

visit(p);Q.EnQueue(p);

while(!Q.IsEmpty()){Q.DeQueue(p);if(p->leftChild!=NULL){

40visit(p->leftChild);

Q.EnQueue(p->leftChild);}if(p->rightChild!=NULL){visit(p->rightChild);

Q.EnQueue(p->rightChild);}}};41由二叉樹的前序序列和中序序列可唯一地確定一棵二叉樹。例,前序序列{ABHFDECKG}

和中序序列{HBDFAEKCG

},構造二叉樹過程如下：HBDFEKCGAEKCGABHDF42前序序列{ABHFDECKG}KCGEKCGABHDFEKCGABHFDEABHFDEABHFDCKG43如果前序序列固定不變，給出不同的中序序列，可得到不同的二叉樹。固定前序排列，選擇所有可能的中序排列，可能構造多少種不同的二叉樹？61234578961237584944例如,有3個數(shù)據(jù){1,2,3

}，可得5種不同的二叉樹。它們的前序排列均為

123，中序序列可能是321，231，213，132，123。前序序列為123，中序序列為

312

的二叉樹不存在。12312312312312345線索化二叉樹

(ThreadedBinaryTree)又稱為穿線樹。通過二叉樹的遍歷，可將二叉樹中所有結點的數(shù)據(jù)排列在一個線性序列中，可以找到某數(shù)據(jù)在這種排列下它的前驅和后繼。希望不必每次都通過遍歷找出這樣的線性序列。只要事先做預處理，將某種遍歷順序下的前驅、后繼關系記在樹的存儲結構中，以后就可以高效地找出某結點的前驅、后繼。46線索(Thread)增加前驅Pred指針和后繼Succ指針的二叉樹predleftChilddatarightChildsuccabcdepredpredpredsuccsuccsuccD∧∧AE∧∧B∧∧C∧∧rootpredpredpredpredsuccsuccsuccsucc47這種設計的缺點是每個結點增加兩個指針，當結點數(shù)很大時存儲消耗較大。改造樹結點，將pred指針和succ指針壓縮到leftChild和rightChild的空閑指針中，并增設兩個標志ltag和rtag，指明指針是指示子女還是前驅／后繼。后者稱為線索。ltag(或rtag)=0，表示相應指針指示左子女（或右子女結點）；當ltag(或rtag)=1,表示相應指針為前驅（或后繼）線索。leftChildltagdatartagrightChild

48leftChildltagdatartagrightChild

abcdepredpredpredsuccsuccsuccDAEB∧C∧rootpredpredsuccsucc0000111111線索化二叉樹及其鏈表表示49線索化二叉樹的類定義template<classT>structThreadNode{ //線索二叉樹的結點類

intltag,rtag; //線索標志

ThreadNode<T>*leftChild,*rightChild;

//線索或子女指針

Tdata; //結點數(shù)據(jù)

ThreadNode(constTitem)//構造函數(shù)

:data(item),leftChild(NULL),rightChild(NULL),ltag(0),rtag(0){} };50template<classT>classThreadTree{ //線索化二叉樹類protected:

ThreadNode<T>*root; //樹的根指針

voidcreateInThread(ThreadNode<T>*current,

ThreadNode<T>*&pre);

//中序遍歷建立線索二叉樹

ThreadNode<T>*parent(ThreadNode<T>*t);

//尋找結點t的雙親結點public:

ThreadTree():root(NULL){} //構造函數(shù)51voidcreateInThread();//建立中序線索二叉樹

ThreadNode<T>*First(ThreadNode<T>*current);

//尋找中序下第一個結點

ThreadNode<T>*Last(ThreadNode<T>*current);

//尋找中序下最后一個結點

ThreadNode<T>*Next(ThreadNode<T>*current);

//尋找結點在中序下的后繼結點

ThreadNode<T>*Prior(ThreadNode<T>*current);

//尋找結點在中序下的前驅結點

……… };52通過中序遍歷建立中序線索化二叉樹0A00B00C00D00E0rootpre==NULLcurrent530A0

1B00C00D00E0rootpre==NULLcurrent540A0

1B00C0

1D00E0rootprecurrent550A0

1B00C0

1D1

0E0rootprecurrent560A0

1B00C0

1D1

1E0rootprecurrent570A0

1B00C0

1D1

1E1

rootprecurrent580A0

1B00C1

1D1

1E1

rootpre后處理59樹的存儲表示A(B(E,F),C,D(G))

結點的utype域沒有畫出ABCDEFGABEFCDG1、廣義表表示60ABCDEFGdataparentABCDEFG-100011301234562、雙親表示樹中結點的存放順序一般不做特殊要求，但為了操作實現(xiàn)的方便，有時也會規(guī)定結點的存放順序。例如，可以規(guī)定按樹的前序次序存放樹中的各個結點，或規(guī)定按樹的層次次序安排所有結點。

613、子女鏈表表示無序樹情形鏈表中各結點順序任意，有序樹必須自左向右鏈接各個子女結點。ABCDEFG123∧45∧6∧∧∧∧∧ABCDEFG0123456624、子女指針表示一個合理的想法是在結點中存放指向每一個子女結點的指針。但由于各個結點的子女數(shù)不同，每個結點設置數(shù)目不等的指針，將很難管理。為此，設置等長的結點，每個結點包含的指針個數(shù)相等，等于樹的度（degree）。這保證結點有足夠的指針指向它的所有子女結點。但可能產生很多空閑指針，造成存儲浪費。63等數(shù)量的鏈域ABCDEFG

datachild1child2child3childdABCDEFG空鏈域2n+1個645、子女-兄弟表示也稱為樹的二叉樹表示。結點構造為：firstChild指向該結點的第一個子女結點。無序樹時，可任意指定一個結點為第一個子女。nextSibling指向該結點的下一個兄弟。任一結點在存儲時總是有順序的。若想找某結點的所有子女，可先找firstChild,再反復用nextSibling沿鏈掃描。

datafirstChildnextSibling65樹的子女-

兄弟表示

datafirstChildnextSiblingABCDEFGABCDGFE66堆(Heap)template<classT,classE>classMinPQ{//最小優(yōu)先級隊列類的定義public:

VirtualboolInsert(E&d)=0;

VirtualboolRemove(E&d)=0;};

優(yōu)先級隊列每次出隊列的是優(yōu)先權最高的元素。用堆實現(xiàn)其存儲表示，能夠高效運作。67最小堆完全二叉樹順序表示

Ki≤K2i+1&&Ki≤K2i+2最大堆完全二叉樹順序表示Ki≥K2i+1&&Ki≥K2i+2090987877878454565653131532323531717堆的定義68堆的元素下標計算由于堆存儲在下標從0開始計數(shù)的一維數(shù)組中，因此在堆中給定下標為i

的結點時如果

i=0，結點i

是根結點，無雙親；否則結點i

的父結點為結點(i-1)/2)；如果2i+1＞n-1，則結點i

無左子女；否則結點i

的左子女為結點2i+1；如果2i+2＞n-1，則結點i無右子女；否則結點i的右子女為結點

2i+2。69自下向上逐步調整為最小堆currentPos=i=3currentPos=i=25353171778780923456587i0923456587i將一組用數(shù)組存放的任意數(shù)據(jù)調整成堆70currentPos=i=15353171778780923456587i0923456587i71currentPos=i=05353171778780923456587i0923456587i09725353171778780923456587i0923456587i1773樹的應用例子---決策樹74樹的應用例子---文件系統(tǒng)搜索樹7576二叉搜索樹(BinarySearchTree)定義

二叉搜索樹或者是一棵空樹，或者是具有下列性質的二叉樹：每個結點都有一個作為搜索依據(jù)的關鍵碼(Key)，所有結點的關鍵碼互不相同。左子樹（如果非空）上所有結點的關鍵碼都小于根結點的關鍵碼。右子樹（如果非空）上所有結點的關鍵碼都大于根結點的關鍵碼。左子樹和右子樹也是二叉搜索樹。77351545504025102030二叉搜索樹例結點左子樹上所有關鍵碼小于結點關鍵碼；右子樹上所有關鍵碼大于結點關鍵碼；注意：若從根結點到某個葉結點有一條路徑，路徑左邊的結點的關鍵碼不一定小于路徑上的結點的關鍵碼。78如果對一棵二叉搜索樹進行中序遍歷，可以按從小到大的順序，將各結點關鍵碼排列起來，所以也稱二叉搜索樹為二叉排序樹。二叉搜索樹的類定義#include<iostream.h>#include<stdlib.h>template<classE,classK>structBSTNode{ //二叉樹結點類

Edata; //數(shù)據(jù)域

BSTNode<E,K>*left,*right;//左子女和右子女79BSTNode(){left=NULL;right=NULL;

}

//構造函數(shù)

BSTNode(constEd,BSTNode<E,K>*L=NULL,

BSTNode<E,K>*R=NULL){data=d;left=L;right=R;}

//構造函數(shù)～BSTNode(){} //析構函數(shù)

voidsetData(Ed){data=d;} //修改

EGetData(){returndata;} //提取

booloperator<(constE&x)

//重載：判小于

{returndata.key<x.key;}80booloperator>(constE&x)

//重載：判大于

{returndata.key>x.key;}booloperator==(constE&x)

//重載：判等于

{returndata.key==x.key;}};template<classE,classK>classBST{ //二叉搜索樹類定義public:BST(){root=NULL;

} //構造函數(shù)

BST(Kvalue); //構造函數(shù)

～BST(){}; //析構函數(shù)

81boolSearch(constKx)const //搜索

{returnSearch(x,root)!=NULL;}

BST<E,K>&operator=(constBST<E,K>&R); //重載：賦值

voidMakeEmpty()

//置空

{MakeEmpty(root);root=NULL;}voidPrintTree()const{PrintTree(root);}//輸出

EMin(){returnMin(root)->data;} //求最小

EMax(){returnMax(root)->data;} //求最大

boolInsert(constE&e1)

//插入新元素

{returnInsert(e1,root);}82boolRemove(constKx){returnRemove(x,root);} //刪除含x的結點private:

BSTNode<E,K>*root; //根指針

KRefValue; //輸入停止標志

BSTNode<E,K>* //遞歸：搜索

Search(constKx,BSTNode<E,K>*ptr);voidmakeEmpty(BSTNode<E,K>*&ptr); //遞歸：置空

voidPrintTree(BSTNode<E,K>*ptr)const; //遞歸：打印

BSTNode<E,K>* //遞歸：復制

Copy(constBSTNode<E,K>*ptr); 83BSTNode<E,K>*Min(BSTNode<E,K>*ptr);

//遞歸：求最小

BSTNode<E,K>*Max(BSTNode<E,K>*ptr);

//遞歸：求最大

boolInsert(constE&e1,BSTNode<E,K>*&ptr);

//遞歸：插入

boolRemove(constKx,BSTNode<E,K>*&ptr);

//遞歸：刪除};二叉搜索樹的類定義用二叉鏈表作為它的存儲表示，許多操作的實現(xiàn)與二叉樹類似。84二叉搜索樹的搜索算法在二叉搜索樹上進行搜索，是一個從根結點開始，沿某一個分支逐層向下進行比較判等的過程。它可以是一個遞歸的過程。假設想要在二叉搜索樹中搜索關鍵碼為x

的元素，搜索過程從根結點開始。如果根指針為NULL，則搜索不成功；否則用給定值

x

與根結點的關鍵碼進行比較：若給定值等于根結點關鍵碼，則搜索成功，返回搜索成功信息并報告搜索到結點地址。85若給定值小于根結點的關鍵碼，則繼續(xù)遞歸搜索根結點的左子樹；否則。遞歸搜索根結點的右子樹。搜索45搜索成功搜索28搜索失敗35154550402510203086搜索過程是從根結點開始，沿某條路徑自上而下逐層比較判等的過程。搜索成功，搜索指針將停留在樹上某個結點；搜索不成功，搜索指針將走到樹上某個結點的空子樹。設樹的高度為h，最多比較次數(shù)不超過h。87二叉搜索樹的插入算法為了向二叉搜索樹中插入一個新元素，必須先檢查這個元素是否在樹中已經存在。在插入之前，先使用搜索算法在樹中檢查要插入元素有還是沒有。如果搜索成功，說明樹中已經有這個元素，不再插入；如果搜索不成功，說明樹中原來沒有關鍵碼等于給定值的結點，把新元素加到搜索操作停止的地方。8835154550402510203028插入新結點28二叉搜索樹的插入每次結點的插入，都要從根結點出發(fā)搜索插入位置，然后把新結點作為葉結點插入。89輸入數(shù)據(jù)

{53,78,65,17,87,09,81,15}535378537865537865175378658717537865091