樹與二叉樹基本操作樹得基本概念空樹:不含結點得樹。非空樹:至少含一個節(jié)點得樹。只有一個根結點,其余結點分為m棵互不相交得子樹,每棵子樹又都就是一棵樹。(遞歸定義)ABCDEFGHIAABACBACBACBACBACBAGCBAFGCBAEFGCBADEFGCBADEFGCBADEFGCBAHDEFGCBAIHDEFGCBA樹得二元組定義K={A,B,C,D,E,F,G,H,I}R={<A,B>,<A,C>,<B,D>,<B,E>,<B,F>,<C,G>,<F,H>,<F,I>}IHDEFGCBA例2、表達式樹a*b+(c-d/e)*f/cab-f**+ed樹得表示方法:1、樹形圖2、二元組3、目錄結構4、集合圖5、凹入表6、廣義表樹得基本術語結點得度:結點得兒子數(shù)(注意不包括孫子)樹得度:樹中所有結點得度得最大值分支結點(非終端結點):度大于0得結點葉子結點(終端結點):度為0得結點孩子結點:某結點得后繼叫該結點得孩子。雙親結點(父結點):某結點得前驅(qū)叫該結點得父親。顯然,根結點沒有雙親,葉結點沒有孩子。結點得層數(shù):根為第一層,其兒子為第二層,孫子為第三層,以此類推。樹得深度(高度):結點得最大層數(shù)。森林:互不相交得樹得集合。對于每個分支結點,其子樹得集合就就是森林。IHDEFGCBA二叉樹得定義

樹得度不超過2得有序樹,非常重要得數(shù)據(jù)結構。IHDFGCBA二叉樹得性質(zhì)性質(zhì)1:二叉樹第i層上至多有2^(i-1)個結點(i≥1)性質(zhì)2:深度為h得二叉樹至多有2^h-1個結點。滿二叉樹:各層結點均達到2^(i-1)完全二叉樹:除最后一層外,其余各層均滿,且最后一層得結點集中在左邊。 給完全二叉樹得結點從上到下,從左到右依次標號,則完全二叉樹得標號性質(zhì)有:性質(zhì)1:若i<=(ndiv2),則i為分支結點,否則為葉子結點。性質(zhì)2:在N個結點得完全二叉樹中,若ｎ為奇數(shù),則,所有分支都有左右兒子,若ｎ為偶數(shù),則n/2得結點只有左兒子,沒有右兒子。其她結點有左右兒子。性質(zhì)3:標號為i得結點,其左兒子為2i,右兒子為2i+1性質(zhì)4:若標號為i得結點有雙親,則i>1且其雙親結點為(idiv2)二叉樹得性質(zhì)完全二叉樹得深度性質(zhì):N個結點得完全二叉樹,其深度為trunc(log2n)+1

理想平衡樹:二叉樹中,除最后一層外,其余層都就是滿得,則稱此樹為理想平衡樹。 滿二叉樹就是特殊得完全二叉樹,完全二叉樹就是特殊得理想平衡樹。FDEGCBADECBAEGCBA滿二叉樹完全二叉樹理想平衡樹完全二叉樹理想平衡樹理想平衡樹二叉樹得存儲結構1、線性存儲 順序存儲二叉樹,首先將二叉樹按照完全二叉樹中對應得位置進行標號,然后,以每個結點得標號為下標,將對應得值存儲到一個一維數(shù)組中。i1234567891011TABCDFGHIIHDFGCBA可見:完全二叉樹用順序存儲極好,但一般二叉樹容易造成空間浪費。大家有疑問的，可以詢問和交流可以互相討論下，但要小聲點二叉樹得存儲結構2、動態(tài)鏈接存儲,三個域得節(jié)點:leftdataright12345678DIBDGAFCHL03002800R06007140或者再添加一個指向父親得指針。Typepnode=^tnode;tnode=recorddata:elementtype;left,right:pnode;end;3、靜態(tài)鏈接存儲Typetnode=recorddata=elementtype;left,right:integer;end;Vara:array[1、、maxl]oftnode;IHDFGCBA存放得順序就是任意得1、建立一棵二叉樹Procedurepre_crt(Varbt:tree);

{按先序次序輸入二叉樹中結點得值,begin生成二叉樹得單鏈表存儲結構}read(ch);

ifch=‘’Thenbt:=Nil{’’表示空樹}elsebeginNew(bt);{建根結點}bt^、data:=ch;

pre_crt(bt^、lchild);{建左子樹}pre_crt(bt^、rchild);{建右子樹}end;end;2、刪除二叉樹Proceduredis(Varbt:tree);beginIfbt<>Nilthenbegindis(bt^、lchild);{刪左子樹}dis(bt^、rchild);{刪右子樹}dispose(bt);{釋放父結點}end;end;3、插入一個結點到二叉樹中procedureinsert(varbt:tree;n:Integer);beginifbt=Nilthenbegin{空樹,則為根結點}new(bt);

bt^、data:=n;

bt^、lchild:=Nil;

bt^、rchild:=Nil;

endelseIfn<bt^、dataTheninsert(bt^、lchild,n){<,左}elseIfn>bt^、datatheninsert(bt^、rchild,n);{>,右}end;4、在二叉樹中查找一個數(shù),找到返回該結點,否則返回nilFunctionfind(bt:tree;n:Integer):tree;BeginIfbt=NilThenfind:=NilElseIfn<bt^、dataThenfind(bt^、lchild,n)ElseIfn>bt^、dataThenfind(bt^、rchild,n)Elsefind:=bt;End;5、用嵌套括號表示法輸出二叉樹Procedureprint(bt:tree);BeginIfbt<>NilThenBeginWrite(bt^、data);If(bt^、lchild<>nil)Or(bt^、rchild<>nil)ThenBeginWrite(‘(’);print(bt^、lchild);

Ifbt^、rchild<>NilThenWrite(‘,’);

print(bt^、rchild);Write(‘)’);

End;

End;End;由廣義表生成二叉樹該二叉樹得廣義表表示:A(B,C)A(B(D,F),C(,G))A(B(D,F(H,I)),C(,G))算法思想:1、依次輸入廣義表中每個字符。2、若遇到字母,則為其新建一個結點,若就是第一個字母,則作為根節(jié)點,若就是孩子節(jié)點,則將其連接到它得父節(jié)點上。3、若遇到左括號,則先將其前面字母得指針進棧,以便后面得結點連接到父節(jié)點上。并記下將要插入節(jié)點得孩子為左孩子(k=1)4、若遇到逗號,則表明左子樹以處理完,標記將要處理得子節(jié)點為右節(jié)點(k=2)、5、若遇到右括號,則表明子樹處理完畢,則退棧。這樣處理直至結束,通常用“”表明廣義表結束。IHDFGCBA算法偽代碼:Procedurebuildtree;Begin

輸入一個字符chwhilech<>’’dobegincasechof‘A’、、’Z’:新建節(jié)點,值域賦為ch,左右子樹指針置空;若為首結點,則就是根節(jié)點,否則若k=1,則當前節(jié)點為棧頂節(jié)點得左子樹,否則k=2則將當前節(jié)點當做棧頂節(jié)點得右子樹?！?’:當前節(jié)點插入棧頂,k=1;‘,’:k=2;‘)’:棧頂元素出棧;

end;

輸入下一字符

end;End;二叉樹得運算1、二叉樹得遍歷2、二叉樹得輸出3、求二叉樹得深度二叉樹得遍歷二叉樹常用得存儲結構

typebitree=^nodenode=recorddata:datatype;lchild,rchild:bitree;end;1、先序遍歷:根左右Procedurepreorder(bt:bitree);Beginifbt<>nilthenbeginvisit(bt^);preorder(bt^、lchild);preorder(bt^、rchild);end;End;二叉樹得遍歷2、中序遍歷:左根右Procedurepreorder(bt:bitree);Beginifbt<>nilthenbeginpreorder(bt^、lchild);visit(bt^);preorder(bt^、rchild);end;End;3、后續(xù)遍歷:左右根Procedurepreorder(bt:bitree);Beginifbt<>nilthenbeginpreorder(bt^、lchild);preorder(bt^、rchild);visit(bt^);end;End;輸出二叉樹

如何將一棵二叉樹輸出為廣義表得形式。Procedureprint(bt:bitree);Beginifbt<>nilthenwrite(bt^、data);if(bt^、lchild<>nil)or(bt^、rchild<>nil)thenbeginwrite(‘(’);print(bt^、lchild);ifbt^、rchild<>nilthenbeginwrite(‘,’);print(bt^rchild);end;write(‘)’);