數(shù)據(jù)結(jié)構(gòu)習(xí)題課4ppt課件.ppt

數(shù)據(jù)結(jié)構(gòu)習(xí)題第4章 吉林大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院谷方明 1 第4章作業(yè) 4 2 4 3 4 5 4 6 4 7 4 8 4 10 4 12 4 13 2 作業(yè)4 2 題目描述由三個結(jié)點(diǎn)A B和C可以構(gòu)成多少棵不同的樹 可以構(gòu)成多少棵不同的二叉樹 3 樹有2種形態(tài) 6 3 9種二叉樹有5種形態(tài) 6 5 30種 4 作業(yè)4 3 判斷以下命題是否為真 若真 請證明之 否則 舉出反例 一棵二叉樹形的所有的葉結(jié)點(diǎn) 在先根次序 中根次序和后根次序下的排列都按相同的相對位置出現(xiàn) 5 先根 ABCEIFJDGHKL中根 EICFJBGDKHLA后根 IEJFCGKLHDBA 6 數(shù)學(xué)歸納法 令n等于二叉樹的高度 n 0時命題成立假設(shè)n k時命題成立 往證n k 1時命題也成立 當(dāng)n k 1時 對任意兩個葉結(jié)點(diǎn)l1 l2 有三種情況l1 l2都在根的左子樹中 l1 l2都在根的右子樹當(dāng)中 l1 l2不在根的同一個子樹當(dāng)中 7 作業(yè)4 5 編寫一算法 判別給定二叉樹是否為完全二叉樹 8 分析 完全二叉樹的葉子結(jié)點(diǎn)只能在層數(shù)最大兩層出現(xiàn) 并且連續(xù)出現(xiàn)在層次遍歷二叉樹時 增加一個標(biāo)志B B 1表示所有已掃描過的結(jié)點(diǎn)均有左 右孩子 B 0 表示遇到無左或右孩子的結(jié)點(diǎn) 此后的所有結(jié)點(diǎn)均應(yīng)為葉結(jié)點(diǎn) 層次遍歷時 空指針可以入隊 出隊遇到第一個空指針時 此后隊列里的都是空指針 對所有結(jié)點(diǎn)按完全二叉樹編號 記錄編號的最大值和結(jié)點(diǎn)數(shù)n 相等 則是完全二叉樹 設(shè)有一個指針數(shù)組 下標(biāo)代表編號 數(shù)組元素代表結(jié)點(diǎn) 出現(xiàn)空缺編號或編號大于n 則不是完全二叉樹 建立編號函數(shù) 遞歸記錄結(jié)點(diǎn)數(shù)和編號最大值 9 參考算法如下 為此 在層次遍歷二叉樹時 增加一個標(biāo)志B B 1表示所有已掃描過的結(jié)點(diǎn)均有左 右孩子 B 0 表示遇到無左或右孩子的結(jié)點(diǎn) 此后的所有結(jié)點(diǎn)均應(yīng)為葉結(jié)點(diǎn) 時間復(fù)雜性為T n 2n或O n 10 boolcompletetree BintreeNode t BoolB 1 QueueQ if t NULL Q Insert t while Q QueueEmpty 11 while Q QueueEmpty 處理剩余葉節(jié)點(diǎn) p Q Delete if p left NULL p right NULL returnfalse returntrue 12 4 6 編寫算法求任意二叉樹中一條最長的路徑 并輸出此路徑上各結(jié)點(diǎn)的值 13 分析 教材中 樹上的路徑定義 若樹T中存在結(jié)點(diǎn)序列Vm Vm 1 Vm k 1 k T的最大層數(shù) Vi 1是Vi的子結(jié)點(diǎn) 相當(dāng)于求根結(jié)點(diǎn)開始的最長路徑 可以根據(jù)左右子樹的高度確定下一步的結(jié)點(diǎn) 14 參考答案 intheight BinTreeNode t if t NULL return 1 return1 max height t left height t right voidpath BinTreeNode t while t coutdataleft height t right t t left elset t right 15 時間復(fù)雜度為O n2 或O n h 原因在于高度的重復(fù)計算 在每個結(jié)點(diǎn)中引入高度域 可以將時間復(fù)雜度為降為O n 樹上的路徑也有另一種理解 即圖論的理解 這時 最長路不一定是從根結(jié)點(diǎn)出發(fā)的 需要先確定路徑最長的結(jié)點(diǎn) 然后按前面的方法處理 也可以按第五章的方法處理 16 TreeNode lstp NULL intmaxl 1 voidLongest TreeNode t if t NULL returnNULL if height t left height t right 2 maxl maxl height t left height t right 2 maxl lstp t Longest t left Longest t right 17 其它方法 課后提示 非遞歸后根遍歷 當(dāng)i 2是 判斷是否為葉子節(jié)點(diǎn) 若是就與當(dāng)前記錄的最長路徑比較 大于就更新最大路徑值及最大路徑 回溯法 引入一個數(shù)組記錄路徑上的結(jié)點(diǎn) 遞歸出口是葉子結(jié)點(diǎn) 非葉子結(jié)點(diǎn)繼續(xù)嘗試和修改 18 4 7 編寫算法判斷兩棵二叉樹T和T 是否相似 兩棵二叉樹相似是指它們具有相同結(jié)構(gòu) 19 參考答案 算法Like t1 t2 判斷兩棵二叉樹是否相似 t1 t2表示兩棵樹的根節(jié)點(diǎn) 若相似 返回值為true 否則為false L1 遞歸出口 IFt1 NULLANDt2 NULLTHENRETURNtrue IFt1 NULLORt2 NULLTHENRETURNfalse L2 遞歸調(diào)用 RETURNLike left t1 left t2 ANDLike right t1 right t2 時間復(fù)雜度為O n1 n2 20 4 8 對于下圖所示的樹 a 對其進(jìn)行先根和后根遍歷 b 給出其在自然對應(yīng)下的二叉樹 21 參考答案 a 對其進(jìn)行先根和后根遍歷 先根遍歷 ABEKGJFCGDHI后根遍歷 KGJEFBGCHIDA b 給出其在自然對應(yīng)下的二叉樹 22 作業(yè)4 10 對以左兒子 右兄弟鏈接表示的樹 編寫計算樹的深度的算法 23 分析 解題思路1 對樹做層次遍歷 每遍歷一層樹的深度 1 關(guān)鍵 將隊列中的結(jié)點(diǎn)結(jié)構(gòu)變?yōu)?結(jié)點(diǎn) 該結(jié)點(diǎn)的層數(shù)i 24 算法Depth t d 解題思路1 對樹做層次遍歷 每遍歷一層樹的深度 1 D1 判斷t是否為NULL IFt NULLTHEN d 1 RETURN D2 創(chuàng)建輔助隊列 根結(jié)點(diǎn)入隊 CREATE Q Q t 0 D3 利用隊列Q遍歷第d層結(jié)點(diǎn) WHILENOT IsEmpty Q DO p d Q WHILEp NULLDO IFFirstChild p NULLTHENQ FirstChild p d 1 p NextBrother p 25 分析 解題思路2 樹的深度dept t max t的各子樹的深度 1 26 算法Depth t d 解題思路2 樹的深度dept t max t的各子樹的深度 1D1 遞歸出口 IFt NULLTHEN d 1 RETURN IF GFC t NULL THEN d 0 RETURN D2 遞歸調(diào)用 p GFC t Max 1 Max存儲各子樹的最大深度WHILE p NULL Depth p dp IF dp Max THENMax dp p GNB p d Max 1 RETURN 27 分析 解題思路3 基于對應(yīng)的二叉樹直接求樹的深度 dept t max 左子樹的深度 1 右子樹的深度 28 算法Depth t d 解題思路3 基于對應(yīng)的二叉樹直接求樹的深度D1 遞歸出口 IFt NULLTHEN d 1 RETURN D2 遞歸調(diào)用 Depth GFC t d1 Depth GNB t d2 d Max d1 1 d2 29 作業(yè)4 12 題目描述構(gòu)造權(quán)值為 5 13 21 7 18 30 41 的哈夫曼樹 30 首先 在森林中取權(quán)值最小的兩個根結(jié)點(diǎn)s和n 合成一棵二叉樹 新生成的結(jié)點(diǎn)T1 作為這兩個結(jié)點(diǎn)的父結(jié)點(diǎn) T1的權(quán)值是兩個子結(jié)點(diǎn)的權(quán)值之和 對新的森林重復(fù)上一步操作 直至森林中只有唯一的根結(jié)點(diǎn)時 終止操作 31 5 13 21 7 18 30 41 25 80 55 135 12 39 5 7 13 30 18 21 41 32 4 13 編寫算法計算二叉樹中邊的個數(shù) 33 分析 邊數(shù) 結(jié)點(diǎn)數(shù) 1 各種遍歷計算結(jié)點(diǎn)數(shù)直接計算邊數(shù) 時間復(fù)雜度都是O n 34 算法E t n 計算二叉樹t的邊數(shù) 結(jié)果放在n中 L1 遞歸出口 n 0 IFt NULLTHENRETURN L2 遞歸調(diào)用 IF left t NULL THEN E left t n1 n n 1