正文內容

第6章樹與二叉樹-資料下載頁

2025-10-15 15:07本頁面

【導讀】樹形結構是線性結構的拓廣。接后繼元素的個數也可以有多個。樹是包含N(N>0)個節點的有窮集合D，R來說沒有前驅，節點e0稱作樹的根。,em)，其中e0就是樹根，樣的節點序列稱為從根到節點e的一條路徑。交的有限集T1，T2，…，Tm，其中每個集。合本身又是一棵樹，稱T1，T2，…體現樹形結構中分支和層次的特性。若D為空集,則稱為空樹;它在關系H下無前驅;Ф,存在D-{r}的一個劃分。素xi∈Di有<r,xi>∈H;,<r,xm>}有惟一的一個劃分。parent的第order個子節點，樹和右子樹構成，同時這兩棵子樹亦是二叉樹。二叉樹可以有5種基本形態，只含根結點二叉樹右子樹為空的二叉樹左、右子樹非空空的二叉樹左子樹為空的二叉樹。性質：在二叉樹的第i層上至多有2i-1. 的子孫的最大層次不小于k。二叉樹不一定是滿二叉樹。二叉樹的深度為?

　　

【正文】，可使用剪枝函數把不需要的子樹剪去；使用限界函數剪去得不到最優解的子樹 ,從而提高回溯法的搜索效率。具體到 01背包問題：預處理：按各物品單位重量所包含的價值從大到小進行排列物品。設計預估函數，其返回值說明右子樹中是否存在一個比當前解更優的解決方案。以此作為剪枝的依據。預估函數的作用：能夠估計出最優解的上界。 01背包問題的回溯法效率分析：預估函數需要 O(N)時間，其中 N為物品種類的數量。在最壞情況下，有 O(2N)個右子節點都需要進行預估，故求解 01背包問題的回溯法時間復雜度為 O(N*2N)。哈夫曼樹與貪心算法 ? 相關概念：從樹中一個節點到另一個節點之間的分支構成這兩個節點之間的路徑；路徑上的分支數目稱作路徑長度。考慮節點帶權的樹：節點的帶權路徑長度為從該節點到樹根之間的路徑長度與節點上權的乘積。樹的帶權路徑長度為樹中所有葉子節點的帶權路徑長度之和，記作： )0,1(N1NklwW P L kNkk ????? ??11 4 2311 4232 3114(a)WPL=(11+4+3+2)*2=40 (b)WPL=(11+4)*3+3*2+2*1=53 (c)WPL=(2+3)*3+4*2+11*1=34 3 具有不同帶權路徑長度的二叉樹試構造一棵有 N個葉子結點的二叉樹，則其中帶權路徑長度 WPL最小的二叉樹稱作最優二叉樹或哈夫曼（ Huffman）樹。構造哈夫曼樹思想： (1)根據給定的 N個權值 {w1,w2,…,wN}構成 N棵二叉樹的集合 F ={T1,T2,…,TN}，其中每棵二叉樹 Ti中只有一個帶權為 wi的根節點，其左右子樹均空； (2)在 F中選取兩棵根節點權值最小的子樹，分別做為左右子樹來構造一棵新的二叉樹，且置新的二叉樹的根節點的權值為其左右子樹上根節點的權值之和； (3)在 F中刪除這兩棵樹，同時將新得到的二叉樹加入 F中； (4)重復 (2)、 (3)，直到 F僅含一棵樹為止。－－－－貪心算法 C DABA B DCC DA BC DBA11 4 3 23 211 41143 243 2115959520C DAB( a ) 初始集合含4 棵樹 ( b ) 集合含3 棵樹 ( c ) 集合含2 棵樹 ( d ) 集合中只含1 棵樹 ( e ) 哈夫曼樹的前綴編碼111 000A:0B:10C:110D:111圖6 . 1 4 哈夫曼樹的構造過程及哈夫曼編碼貪心算法并不從整體最優的角度來考慮問題。它所做出的選擇只是在某種意義上的局部最優選擇。 ?哈夫曼樹應用：哈夫曼編碼－－電文的二進制前綴編碼本章小結 ? 基本內容： 1. 樹的基本概念 2. 二叉樹的定義、性質和存儲結構；二叉樹的遍歷和線索化以及遍歷算法的各種描述形式； 3. 樹和森林與二叉樹的轉換、樹和森林的遍歷；典型應用；回溯法與貪心算法。 ? 基本要求：熟練掌握二叉樹的結構特性，了解相應的證明方法。熟悉二叉樹的各種存儲結構的特點及適用范圍。熟練掌握各種遍歷策略的遞歸算法，了解遍歷過程中 “ 棧 ” 的作用和狀態，而且能靈活運用遍歷算法實現二叉樹的其他操作。層次遍歷是按另一種搜索策略進行的遍歷。熟悉樹的各種存儲結構及其特點，掌握樹和森林與二叉樹的轉換方法。掌握各種建立二叉樹和樹的存儲結構的方法。學會編寫實現樹的各種操作的算法。掌握建立哈夫曼編碼的方法。學習并使用貪心算法與回溯法的思想。

點擊復制文檔內容

教學課件相關推薦

第6章樹與二叉樹-資料下載頁

[工學]ch6樹和二叉樹-資料下載頁

樹的定義和基本術語62二叉樹63遍歷二叉樹和線索二叉-資料下載頁

數據結構4樹與二叉樹-資料下載頁

c語言二叉樹-資料下載頁

奇妙的二叉樹-資料下載頁

作業樹和二叉樹-資料下載頁

算法與數據結構第4章樹與二叉樹ppt-資料下載頁

樹和二叉樹ppt課件(2)-資料下載頁

第六章樹和二叉樹-資料下載頁

數據結構---樹和二叉樹-資料下載頁

特殊二叉樹ppt課件-資料下載頁

二叉樹期權定價模型-資料下載頁

二叉樹的建立與遍歷與二叉樹的線索化與線索化遍歷-資料下載頁

樹和森林與二叉樹的轉換-資料下載頁

樹和二叉樹實驗報告-資料下載頁

第6章樹與二叉樹(編輯修改稿)

第6章樹與二叉樹-wenkub.com

第6章樹與二叉樹(已改無錯字)

第6章樹與二叉樹-資料下載頁

第6章樹與二叉樹(參考版)