【正文】 集約蜂酪汁聾喝恰汪際倫釉規(guī)首蓄noip復(fù)習(xí)資料!!!noip復(fù)習(xí)資料!!! 樹的度：樹內(nèi)各結(jié)點度的最大值。例如： (b)樹的度是 3。 有序樹和無序樹：如果將樹中的各子樹看成是從左到右有次序的（即不能互換），則稱該樹為有 序樹，否則稱為無序樹。 結(jié)點的孩子：結(jié)點的子樹的根稱為該結(jié)點的孩子，相應(yīng)地，該結(jié)點稱為孩子的雙親。 A M L K J I H G F E D C B 結(jié)點 A的孩子 孩子 {B， C， D}的雙親 結(jié)點 D的孩子 孩子 {H， I， J}的雙親 結(jié)點的層次：根為第一層；若某結(jié)點在第 P層，則其子樹的根就在第 P+1層。 樹的高度 (或深度 ):樹中結(jié)點的最大層次稱為樹的高度（或深度）。例如： (b)樹的高度為 4。 例如：結(jié)點 A的度是 3，結(jié)點 C的度是 1，結(jié)點 E的度是 2 結(jié)點 K， L， F， G， M， I， J為葉子結(jié)點，結(jié)點 A， B， C， D， E， H為非終端結(jié)點。 例如：結(jié)點 B， C， D是結(jié)點 A的孩子，結(jié)點 A是 B， C， D的雙親；結(jié)點 E， F是結(jié)點 B的孩子，結(jié)點 B是 E， F的雙親。 棲擴吏嚴(yán)署痹器卑氫惺狽烴膩郝彩差汰請票搬販固虧胞魔爾蚊暇鄖輕忍戀noip復(fù)習(xí)資料!!!noip復(fù)習(xí)資料!!! （ 1）哪個是根結(jié)點？ A （ 2）哪些是葉子結(jié)點？哪些是非終端 結(jié)點？ D、 M、 N、 F、 J、 K、 L。 A、 B、 C、 E、 G、 H、 I。 （ 3）哪個是結(jié)點 G的雙親？ C （ 4）哪些是結(jié)點 G的孩子？ J、 K。 練習(xí) 14個結(jié)點的樹，請回答下面問題： A C L F G H J K B D E I N M （ 5）結(jié)點 B和 N的層次號分別是什么？ 5。 （ 6）結(jié)點 C和 E的度分別是什么？樹的度是 什么？ 1。 3。 （ 7）樹的高度是多少？ 5。 系焉礁惹誰紅案親嘆隱華擦膠耶薔蹭息時池裙絡(luò)很待穢小準(zhǔn)仁這段廠就信noip復(fù)習(xí)資料!!!noip復(fù)習(xí)資料!!! 2.（填空）有一棵樹如圖所示，回答下面的問題： K1 K2 K4 K7 K3 K6 K5 （ 1）這棵樹的根結(jié)點是 _______。 （ 2）這棵樹的葉子結(jié)點是 _______________。 （ 3）結(jié)點 K3的度是 _______。 （ 4）這棵樹的度是 _______。 （ 5）這棵樹的深度是 _______。 （ 6）結(jié)點 K3的孩子是 _______。 （ 7）結(jié)點 K3的雙親是 _______。 K1 K2,K4,K5,K7 2 3 4 K5,K6 K1 二叉樹（重點） 一、二叉樹的定義： 二叉樹（ Binary Tree）是另一種樹型結(jié)構(gòu)，它的特點是每個結(jié)點至多只有二棵子樹（即二叉 樹中不存在度大于 2的結(jié)點），并且，二叉樹的子樹有左右之分，分別稱為左子樹和右子樹，其 次序不能任意顛倒。 (a) 1 3 4 5 6 2 7 1 2 3 4 6 5 (b) 燦剝僑墨素龐焉姑殖甲借戳滁百腦育澤侵紙稱尿娶耘義逛幢斗布賃再況拳noip復(fù)習(xí)資料!!!noip復(fù)習(xí)資料!!! 1 3 7 15 14 6 13 12 5 11 10 9 8 4 2 (c) 1 3 7 6 12 5 11 10 9 8 4 2 (d) 特殊形態(tài)的二叉樹 二、二叉樹具有下列重要性質(zhì)： 性質(zhì) 1 在二叉樹的第 i層至多有 個結(jié)點。 2i1 (i≥1) 性質(zhì) 2 高度為 k的二叉樹至多有 個結(jié)點。 2k1 性質(zhì) 3 對任何一棵二叉樹，若葉子結(jié)點數(shù)為 n0，度為 2的結(jié)點數(shù)為 n2，則 n0=n2+1。（二叉樹的葉 子結(jié)點數(shù)總比度為 2的結(jié)點數(shù)多 1） 證明：設(shè) n1為二叉樹 T中度為 1的結(jié)點數(shù)，因為二叉樹中所有結(jié)點的度均 ≤2，所以其結(jié)點總數(shù)為 n=n0+n1+n2 (1) 再看二叉樹的分支數(shù)，除了根結(jié)點外，其余結(jié)點都有一個分支進(jìn)入，設(shè) B為分支總數(shù)，則 n=B+1，由于這些分支是由度為 1或 2的結(jié)點射出的，所以 B=n1+2n2。于是得： n=n1+2n2+1 (2) 由（ 1）和（ 2）得： n0=n2+1 陶鰓亦窟戴程旦菱醇倦齡厭謝稻肯百何悸析又絞卜頓讀復(fù)錨祈她網(wǎng)抵膿痕noip復(fù)習(xí)資料!!!noip復(fù)習(xí)資料!!! 滿二叉樹：一個高度為 k且有 2k1個結(jié)點的二叉樹稱為滿二叉樹。 1 3 7 15 14 6 13 12 5 11 10 9 8 4 2 滿二叉樹 可以對滿二叉樹的結(jié)點進(jìn)行連續(xù)編號，約定編號從根結(jié)點 起，自上而下，從左至右。從而引出： 完全二叉樹：高度為 k，有 n個結(jié)點的二叉樹，當(dāng)且僅當(dāng) 其每一個結(jié)點都與高度為 k的滿二叉樹中編號從 1至 n的 結(jié)點一一對應(yīng)時，稱之為完全二叉樹。 完全二叉樹的另一個定義：再一棵二叉樹中，除最后一層 外，若其余各層都是滿的，并且最后一層或者是滿的，或 者是在右邊缺少若干連續(xù)結(jié)點，則此二叉樹稱為完全二叉樹。 1 3 7 6 12 5 11 10 9 8 4 2 完全二叉樹 性質(zhì) 4：具有 n個結(jié)點的完全二叉樹的高度為 log2 n +1 ( x 表示不大于 x的最大整數(shù)） 性質(zhì) 5：如果對一棵有 n個結(jié)點的完全二叉樹的結(jié)點編號 （根為 1，然后自上而下，從左到右），則對任一結(jié)點 i (1≤i≤n），有 : (1)如果 i=1，則結(jié)點 i是二叉樹的根，無雙親；如果 i大于 1，則其雙親結(jié)點為 。 （ 2）結(jié)點 i的左孩子是 2i，右孩子是 2i+1；如果 2i＞ n，則 i無左孩子；若 2i=n，則 i無右孩子。 i/2 樹的存儲結(jié)構(gòu)包括： 靜態(tài)結(jié)構(gòu)：用一個數(shù)組按完全二叉樹的結(jié)構(gòu)存放。 動態(tài)存儲：利用指針類型實現(xiàn)。 暈皋惟沾離隆守諾店巢昨彼峽紳謂骯妒竭肯騙換髓結(jié)疆況凌蜘叁羚宜簍蓮noip復(fù)習(xí)資料!!!noip復(fù)習(xí)資料!!! h的二叉樹上只有度為 0和度為 2的結(jié)點，則此類二叉樹中包含的結(jié)點至少為 _____。 +1 +1 B ，具有 3個結(jié)點的二叉樹有 _____種。 C C A 練習(xí)（單項選擇題） 3. 如圖所示的 4棵二叉樹中， _____不是完全二叉樹， _____是滿二叉樹。 (D) (C) (A) (B) 5的二叉樹至多有 _____個結(jié)點。 C _______。 ，有 m個樹葉， n個結(jié)點，深度為 h，則 _______。 =h+m +m=2n =h1 =2h1 C D 如 h=1 h=2 h=3 h=4 未汛厚衍耕鑿夠傳滋榴夜花牙館澀食閻篆循佑躊擰扶委淑曼韶剮甄虧剎癌noip復(fù)習(xí)資料!!!noip復(fù)習(xí)資料!!! 回答： k的完全二叉樹至少有多少個結(jié)點？至多有多少個結(jié)點？若按自上而下、從左到右的次序給 結(jié)點編號（從 1開始），則第 k層編號最小的葉子結(jié)點的編號是多少？ 答： 2k 2k 2k1 填空： ，度為零的結(jié)點個數(shù)為 n0，度為 2的結(jié)點個數(shù)為 n2，則有 n0=_______。 n2+1 13的完全二叉樹共有 _______個葉子結(jié)點。 7 二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu) 用二重鏈表表示一般的二叉樹，可以采用動態(tài)數(shù)據(jù)結(jié)構(gòu)（指針）。由于二叉樹中每個結(jié)點通常包括數(shù) 據(jù)元素和兩個分支，因此，二叉樹對應(yīng)的二重鏈表中每個結(jié)點應(yīng)有三個域： 值域： ： data 左指針域 : lch 右指針域 : rch 這種鏈表也稱為二叉鏈表。二叉鏈表頭指針 bt指向二叉樹的根結(jié)點： Type bitreptr=^benode。 benode=record data:datatype。 lch,rch:bitreptr。 end。 Var bt:bitreptr。 例如：用下圖（ b）所示的二叉鏈表存儲二叉樹 （ a） : 匯肄畸厚撒圍毯憎僻罪殊乒轎俯旺怎咸掏鮑意覓炬邪限姨菊番臨第柬桶崔noip復(fù)習(xí)資料!!!noip復(fù)習(xí)資料!!! 二叉樹的遍歷 按照一定的規(guī)律不重復(fù)地訪問二叉樹中的每一個結(jié)點。在訪問到每個結(jié)點時，可以取出結(jié)點中的信 息，亦可對結(jié)點作其它處理。 如果用 L、 D、 R分別表示遍歷左子樹，訪問根結(jié)點，遍歷右子樹，則對二叉樹的遍歷有如下六種組 合： LDR、 LRD、 DLR、 DRL、 RDL、 RLD 若再限定先左后右的次序，則只剩下三種組合： LDR、 LRD、 DLR 這三種遍歷規(guī)則分別稱為：中（根）序遍歷、后（根）序遍歷、先（根）序遍歷。 Lch data rch a b c d e f g (a) a b ^ c ^ ^ d e f ^ ^ ^ g ^ ^ (b) 醉焊粕鈾附喀筋漣酥辜橇銻鮑既夕湛勉旺釉成泅錦兔嚎礬當(dāng)疹廁頓桿刺石noip復(fù)習(xí)資料!!!noip復(fù)習(xí)資料!!! 復(fù)習(xí)題選講 一、選擇題部分 第一套 (2022) 參閱 《 數(shù)據(jù)結(jié)構(gòu) 》 P~43“順序 隊列”。 1因為 29=1000=210， 所以選 B。 1先觀察右圖： 然后總結(jié)規(guī)律。 SA SA+1 SA+2 SA+3 SA+4 占 30 個 字 節(jié) SA+30 SA+120 …… A[1,1] A[1,2] A[1,10] A[2,1] …… A[2,10] …… A[5,1] …… A[5,8] SA+141 占 120 個 字 節(jié) 1正確答案是 B。這題可以通過 歸納的方法來得出結(jié)論，假定在 這根兩端停著相同小鳥 A： A——————B 線段為不同小鳥的線段數(shù) A——A———A 0 A——B———A 2 A—A—B——A