數據結構習題課4ppt課件.ppt

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