樹和二叉樹的基本知識-免費(fèi)閱讀
【正文】 [輸入格式] ，共兩行，第一行一個字符串，表示樹的先序遍歷，第二行一個字符串，表示樹的中序遍歷。那么反過來，給定一棵二叉樹的先序遍歷結(jié)果和中序遍歷結(jié)果，能否確定一棵二叉樹呢（即是否唯一）？由定義，二叉樹的先序遍歷是先訪問根結(jié)點(diǎn)，再遍歷左子樹，最后遍歷右子樹。1．建立一棵二叉樹Procedure pre_crt(Var bt:tree)；{按先序次序輸入二叉樹中結(jié)點(diǎn)的值，Begin 生成二叉樹的單鏈表存儲結(jié)構(gòu)} Read(ch)； If ch=’’ Then bt:=Nil {’’表示空樹} Else Begin New(bt)； {建根結(jié)點(diǎn)} bt^.data:=ch； pre_crt(bt^.lchild)； {建左子樹} pre_crt(bt^.rchild)； {建右子樹} End；End； 2．刪除二叉樹Procedure dis(Var bt:tree)； Begin If btNil Then BeginDis(bt^.lchild)； {刪左子樹}Dis(bt^.rchild)； {刪右子樹}Dispose(bt)； {釋放父結(jié)點(diǎn)} End；End；3．插入一個結(jié)點(diǎn)到二叉樹中Procedure insert(Var bt:tree；n:Integer)； Begin If bt=Nil Then Begin {空樹，則為根結(jié)點(diǎn)}New(bt)； bt^.data:=n； bt^.lchild:=Nil；bt^.rchild:=Nil； End Else If nbt^.data Then insert(bt^.lchild,n) {，左} Else If nbt^.data Then insert(bt^.rchild,n)； {，右}End；4．在二叉樹中查找一個數(shù)，找到返回該結(jié)點(diǎn),否則返回nilFunction find(bt:tree；n:Integer):tree； Begin If bt=Nil Then find:=Nil Else If nbt^.data Then find(bt^.lchild,n)Else If nbt^.data Then find(bt^.rchild,n) Else find:=bt；End；5．用嵌套括號表示法輸出二叉樹Procedure print(bt:tree)；Begin If btNil Then BeginWrite(bt^.data)；If (bt^.lchildnil) Or (bt^.rchildnil) Then Begin Write(‘(’)；print(bt^.lchild)； If bt^.rchildNil Then Write(‘,’)； print(bt^.rchild)；Write(‘)’)； End； End；End；七、二叉樹的計數(shù)問題在實(shí)際應(yīng)用中經(jīng)常需要求“具有n個結(jié)點(diǎn)的不同形態(tài)的二叉樹有多少棵？具有n個結(jié)點(diǎn)的不同形態(tài)的樹有多少棵？”要解決上述問題，首先要了解下面兩個概念：“相似二叉樹”是指兩者都為空樹或者兩者均不為空樹，且它們的左右子樹分別相似。五、二叉樹的遍歷在二叉樹的應(yīng)用中，常常要求在樹中查找具有某種特征的結(jié)點(diǎn)，或者對全部結(jié)點(diǎn)逐一進(jìn)行某種處理,這就是二叉樹的遍歷問題。)； Rewrite(Output)； Readln(n)； For i := 1 To n Do 圖11 For j := 1 To n Do g[i][j] := 1000000； For i := 1 To n Do {讀入、初始化} Begin g[i][i] := 0； Readln(a[i], l, r)； If l 0 Then Begin g[i][l] := 1；g[l][i] := 1 End； If r 0 Then Begin g[i][r] := 1；g[r][i] := 1 End； End； For k := 1 To n Do {用Floyed法求任意兩結(jié)點(diǎn)之間的最短路徑長} For i := 1 To n Do If i k Then For j := 1 To n Do If (i j) And (k j) And (g[i][k] + g[k][j] g[i][j]) Then g[i][j] := g[i][k] + g[k][j]； min := Maxlongint； For i := 1 To n Do {窮舉醫(yī)院建在N個結(jié)點(diǎn)，找出最短距離} Begin total := 0； For j := 1 To n Do Inc(total, g[i][j] * a[j])； If total min Then min := total； End； Writeln(min)；Close(Input)；Close(Output)；End.[后記] 在各種競賽中經(jīng)常遇到這樣的問題：N1條公路連接著N個城市，從每個城市出發(fā)都可以通過公路到達(dá)其它任意的城市。接下來的n行每行描述了一個結(jié)點(diǎn)的狀況，包含三個整數(shù)，整數(shù)之間用空格（一個或多個）分隔，其中：第一個數(shù)為居民人口數(shù)；第二個數(shù)為左鏈接，為0表示無鏈接；第三個數(shù)為右鏈接。1．鏈?zhǔn)酱鎯Y(jié)構(gòu):單鏈表結(jié)構(gòu)或雙鏈表結(jié)構(gòu)，基本數(shù)據(jù)結(jié)構(gòu)定義如下：Type tree=^node； {單鏈表結(jié)構(gòu)} node=Record data:Char； {數(shù)據(jù)域} lchild,rchild:tree {指針域：分別指向左、右孩子} End；Var bt:tree；Type tree=^node； {雙鏈表結(jié)構(gòu)} node=Record data:Char； {數(shù)據(jù)域} lchild,rchild,father:tree {指針域：分別指向左、右孩子及父結(jié)點(diǎn)} End；Var bt:tree；如圖9左邊所示的一棵二叉樹用單鏈表就可以表示成右邊的形式。圖5可以對滿二叉樹的結(jié)點(diǎn)進(jìn)行連續(xù)編號，約定編號從根結(jié)點(diǎn)起，自上而下，從左到右，由此引出完全二叉樹的定義：深度為k，有n個結(jié)點(diǎn)的二叉樹當(dāng)且僅當(dāng)其每一個結(jié)點(diǎn)都與深度為k的滿二叉樹中編號從1到n的結(jié)點(diǎn)一一對應(yīng)時，稱為完全二叉樹。； {前一個單詞} For i:=1 To n Do {統(tǒng)計} Begin now := 39。另外為了排序，再設(shè)一個數(shù)組index:array[1.. 6700] of integer；存放每個單詞在a中的起始位置。于是，得出建樹的等效算法：① 讀入文件；② 對單詞列表進(jìn)行字典順序排序；③ 依次計算每個單詞對前一單詞的差，并把差累加起來。每個單詞僅由大寫的英文
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1