樹(shù)與二叉樹(shù)基本操作

1、樹(shù)樹(shù)的的基基空樹(shù)：不含結(jié)點(diǎn)的樹(shù)。非空樹(shù)：至少含一個(gè)節(jié)點(diǎn)的樹(shù)。只有一個(gè)根結(jié)點(diǎn)，其余結(jié)點(diǎn)分為m棵互不相交的子樹(shù)，每棵子樹(shù)又都是一棵樹(shù)。（遞歸定義）abcdefghia abacbacbacbacbacbagcbafgcbaefgcbadefgcbadefgcbadefgcbahdefgcbaihdefgcba樹(shù)樹(shù)的的二二k=a,b,c,d,e,f,g,h,ir=,ihdefgcba例例2、表表a*b+(c-d/e)*f/cab-f*+ed1、樹(shù)形圖 2、二元組 3、目錄結(jié)構(gòu) 4、集合圖 5、凹入表 6、廣義表樹(shù)樹(shù)的的基基結(jié)點(diǎn)的度：結(jié)點(diǎn)的兒子數(shù)（注意不包括孫子）樹(shù)的度：樹(shù)中所有結(jié)點(diǎn)的度的最大值分支結(jié)

2、點(diǎn)（非終端結(jié)點(diǎn)）：度大于0的結(jié)點(diǎn)葉子結(jié)點(diǎn)（終端結(jié)點(diǎn)）：度為0的結(jié)點(diǎn)孩子結(jié)點(diǎn)：某結(jié)點(diǎn)的后繼叫該結(jié)點(diǎn)的孩子。雙親結(jié)點(diǎn)（父結(jié)點(diǎn)）：某結(jié)點(diǎn)的前驅(qū)叫該結(jié)點(diǎn)的父親。顯然，根結(jié)點(diǎn)沒(méi)有雙親，葉結(jié)點(diǎn)沒(méi)有孩子。結(jié)點(diǎn)的層數(shù)：根為第一層，其兒子為第二層，孫子為第三層，以此類推。樹(shù)的深度（高度）：結(jié)點(diǎn)的最大層數(shù)。森林：互不相交的樹(shù)的集合。對(duì)于每個(gè)分支結(jié)點(diǎn)，其子樹(shù)的集合就是森林。ihdefgcba二二叉叉樹(shù)樹(shù)樹(shù)的度不超過(guò)2的有序樹(shù)，非常重要的數(shù)據(jù)結(jié)構(gòu)。ihdfgcba二二叉叉樹(shù)樹(shù)性質(zhì)性質(zhì)1：二叉樹(shù)第：二叉樹(shù)第i層上至多有層上至多有2(i-1)個(gè)結(jié)點(diǎn)（個(gè)結(jié)點(diǎn)（i1）性質(zhì)性質(zhì)2：深度為：深度為h的二叉樹(shù)至多有的二叉樹(shù)至多有2

3、h-1個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。滿二叉樹(shù)：各層結(jié)點(diǎn)均達(dá)到2(i-1)完全二叉樹(shù)：除最后一層外，其余各層均滿，且最后一層的結(jié)點(diǎn)集中在左邊。給完全二叉樹(shù)的結(jié)點(diǎn)從上到下，從左到右依次標(biāo)號(hào)，則完全二叉樹(shù)的標(biāo)號(hào)性質(zhì)有：性質(zhì)1：若i1且其雙親結(jié)點(diǎn)為（i div 2）二二叉叉樹(shù)樹(shù)完全二叉樹(shù)的深度性質(zhì)：n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，其深度為trunc(log2n)+1理想平衡樹(shù)理想平衡樹(shù)：二叉樹(shù)中，除最后一層外，其余層都是滿的，則稱此樹(shù)為理想平衡樹(shù)。滿二叉樹(shù)是特殊的完全二叉樹(shù)，完全二叉樹(shù)是特殊的理想平衡樹(shù)。fdegcbadecbaegcba滿二叉樹(shù)完全二叉樹(shù)理想平衡樹(shù)完全二叉樹(shù)理想平衡樹(shù)理想平衡樹(shù)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的存儲(chǔ)結(jié)

4、構(gòu)1、線性存儲(chǔ)順序存儲(chǔ)二叉樹(shù)，首先將二叉樹(shù)按照完全二叉樹(shù)中對(duì)應(yīng)的位置進(jìn)行標(biāo)號(hào)，然后，以每個(gè)結(jié)點(diǎn)的標(biāo)號(hào)為下標(biāo)，將對(duì)應(yīng)的值存儲(chǔ)到一個(gè)一維數(shù)組中。ihdfgcba可見(jiàn)：完全二叉樹(shù)用順序存儲(chǔ)極好，但一般二叉樹(shù)容易造成空間浪費(fèi)。二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)2、動(dòng)態(tài)鏈接存儲(chǔ)，三個(gè)域的節(jié)點(diǎn)：或者再添加一個(gè)指向父親的指針。type pnode=tnode; tnode=record data:elementtype; left,right:pnode; end;3、靜態(tài)鏈接存儲(chǔ)type tnode=record data=elementtype; left,right:integer; end;var a

5、:array1.maxlof tnode;ihdfgcba存放的順序是任意的1建建立立一一procedure pre_crt(var bt:tree)； 按先序次序輸入二叉樹(shù)中結(jié)點(diǎn)的值，begin 生成二叉樹(shù)的單鏈表存儲(chǔ)結(jié)構(gòu) read(ch)； if ch= then bt:=nil 表示空樹(shù) else begin new(bt)； 建根結(jié)點(diǎn) bt.data:=ch； pre_crt(bt.lchild)； 建左子樹(shù) pre_crt(bt.rchild)； 建右子樹(shù) end；end； 2刪刪procedure dis(var bt:tree)； begin if btnil then begi

6、n dis(bt.lchild)； 刪左子樹(shù) dis(bt.rchild)； 刪右子樹(shù) dispose(bt)； 釋放父結(jié)點(diǎn) end；end；3插插入入一一個(gè)個(gè)procedure insert(var bt:tree；n:integer)； begin if bt=nil then begin 空樹(shù)，則為根結(jié)點(diǎn) new(bt)； bt.data:=n； bt.lchild:=nil； bt.rchild:=nil； end else if nbt.data then insert(bt.lchild,n) bt.data then insert(bt.rchild,n)； ，右 end；4在在

7、二二叉叉樹(shù)樹(shù)中中查查找找一一個(gè)個(gè)數(shù)，數(shù)，找找function find(bt:tree；n:integer):tree； begin if bt=nil then find:=nil else if nbt.data then find(bt.rchild,n) else find:=bt；end；5用用嵌嵌套套括括號(hào)號(hào) procedure print(bt:tree)； begin if btnil then begin write(bt.data)； if (bt.lchildnil) or (bt.rchildnil) then begin write()；print(bt.lchild

8、)； if bt.rchildnil then write(,)； print(bt.rchild)；write()； end； end； end；由由廣廣義義表表該二叉樹(shù)的廣義表表示：a(b,c)a(b(d,f),c(,g)a(b(d,f(h,i),c(,g)算法思想：1、依次輸入廣義表中每個(gè)字符。2、若遇到字母，則為其新建一個(gè)結(jié)點(diǎn)，若是第一個(gè)字母，則作為根節(jié)點(diǎn)，若是孩子節(jié)點(diǎn)，則將其連接到它的父節(jié)點(diǎn)上。3、若遇到左括號(hào)，則先將其前面字母的指針進(jìn)棧，以便后面的結(jié)點(diǎn)連接到父節(jié)點(diǎn)上。并記下將要插入節(jié)點(diǎn)的孩子為左孩子（k=1）4、若遇到逗號(hào)，則表明左子樹(shù)以處理完，標(biāo)記將要處理的子節(jié)點(diǎn)為右節(jié)點(diǎn)（k=2

9、）.5、若遇到右括號(hào)，則表明子樹(shù)處理完畢，則退棧。這樣處理直至結(jié)束，通常用“”表明廣義表結(jié)束。ihdfgcba算算法法procedure buildtree;begin 輸入一個(gè)字符ch while ch do begin case ch of a.z:新建節(jié)點(diǎn)，值域賦為ch，左右子樹(shù)指針置空；若為首結(jié)點(diǎn)，則是根節(jié)點(diǎn)，否則若k=1,則當(dāng)前節(jié)點(diǎn)為棧頂節(jié)點(diǎn)的左子樹(shù)，否則k=2則將當(dāng)前節(jié)點(diǎn)當(dāng)做棧頂節(jié)點(diǎn)的右子樹(shù)。 (：當(dāng)前節(jié)點(diǎn)插入棧頂，k=1; , :k=2; ):棧頂元素出棧； end; 輸入下一字符 end;end;二二叉叉樹(shù)樹(shù)1、二叉樹(shù)的遍歷2、二叉樹(shù)的輸出3、求二叉樹(shù)的深度二二叉叉樹(shù)樹(shù)二叉樹(shù)常

10、用的存儲(chǔ)結(jié)構(gòu) type bitree=node node=record data :datatype; lchild,rchild:bitree; end;1、先序遍歷：根左右、先序遍歷：根左右procedure preorder(bt:bitree);begin if btnil then begin visit(bt); preorder(bt.lchild); preorder(bt.rchild); end;end;二二叉叉樹(shù)樹(shù)2、中序遍歷：左根右procedure preorder(bt:bitree);begin if btnil then begin preorder(bt.lc

11、hild); visit(bt); preorder(bt.rchild); end;end;3、后續(xù)遍歷：左右根procedure preorder(bt:bitree);begin if btnil then begin preorder(bt.lchild); preorder(bt.rchild); visit(bt); end;end;輸輸出出如何將一棵二叉樹(shù)輸出為廣義表的形式。procedure print(bt:bitree);begin if btnil then write(bt.data); if (bt.lchildnil) or(bt.rchildnil) then b

12、egin write(); print(bt.lchild); if bt.rchildnil then begin write(,); print(btrchild); end; write(); end;end;求求二二叉叉 若二叉樹(shù)空，則深度為0，否則其深度=子樹(shù)的最大深度+1。function depth(bt:bitree):integer;begin if bt=nil then depth:=0; depth1:=depth(bt.lchild); depth2:=depth(bt.rchild); if depth1depth2 then depth:=depth1+1 els

13、e depth:=depth2+1;end; 問(wèn)題描述 輸入一棵二叉樹(shù)的先序和中序遍歷序列，輸出其后序遍歷序列。 輸入格式 輸入文件為tree.in，共兩行，第一行一個(gè)字符串，表示樹(shù)的先序遍歷，第二行一個(gè)字符串，表示樹(shù)的中序遍歷。樹(shù)的結(jié)點(diǎn)一律用小寫字母表示。 輸出格式 輸出文件為tree.out，僅一行，表示樹(shù)的后序遍歷序列。 樣例輸入 abdec dbeac 樣例輸出 debcaprogram tree_1(input, output)；var s1, s2 : string；procedure try(l1, r1, l2, r2 : integer)； 遞歸、后序var m : integer；begin m := pos(s1l1, s2)； 求l1的第一個(gè)字符在l2中的位置 if m l2 then try(l1 + 1, l1 + m - l