第6章樹與二叉樹(完整版)
【正文】 00 000圖6 . 1 2 0 1 背包問題的解空間樹( n = 3 )從根結(jié)點到葉節(jié)點的一個路徑就對應(yīng)著解空間的一個解 搜索最優(yōu)解：回溯法 1. 從開始節(jié)點（根節(jié)點）出發(fā)，以深度優(yōu)先方式搜索整個解空間。 ① 若 F為空 ， 即 m=0， 則 B為空二叉樹； ② 若 F非空，即 m?0，則 B的根 root即為森林中第一棵樹的根 root(T1)； B的左子樹 lb是從T1中根節(jié)點的子樹森林 F1={T11,T12,…,T1k}轉(zhuǎn)化而成的二叉樹；其右子樹 rb是從森林F’={T2,T3,…,Tm}轉(zhuǎn)化而成的二叉樹。 不足：一般的二叉樹也必須按完全二叉樹的形式來存儲，勢必會造成存儲的浪費。 特點：每一層上的節(jié)點數(shù)都達(dá)到了最大節(jié)點數(shù)。child) 遍歷樹 tree各元素，并用visit代表的操作處理元素數(shù)據(jù) 在樹 tree中求節(jié)點 elem的父節(jié)點，并將結(jié)果放入parent中 說明 :在樹 tree中求節(jié)點 parent的第 order個子節(jié)點，并將結(jié)果放入 child中 treeSetChild(tree,parent,order,child) } 在樹 tree中設(shè)置節(jié)點parent的第 order個子節(jié)點，待設(shè)置的值已經(jīng)放入 child中 二叉樹 二叉樹的定義與基本運算 二叉樹是一個集合 T；它可以是空集 ， 也可以是一個由節(jié)點組成的有限集 。 () 對應(yīng)于 D{r}的劃分 ,H{r,x1,r,x2,…,r,xm}有惟一的一個劃分H1,H2,…,Hm(m0),對任意 j?k(1≤ j,k≤ m)有Hj∩ Hk=Ф,且對任意的 i(1≤ i≤ m),Hi是 Di上的二元關(guān)系 ,(Di,{Hi})是一棵符合本定義的樹 ,稱為根 r的子樹。這樣的節(jié)點序列稱為從 根到節(jié)點 e的一條路徑 。 樹的定義與表示 ? 樹的定義 ： 樹的 邏輯結(jié)構(gòu) 可以這樣描述： 樹是包含 N(N0)個節(jié)點的 有窮集合 D，且在 D上定義了一個 關(guān)系 R，關(guān)系 R滿足以下條件： (1) 有且僅有一個 節(jié)點 e0?D， 它對于關(guān)系R來說 沒有前驅(qū) ， 節(jié)點 e0稱作樹的 根 。 (2) 若 D為非空集且僅含有一個數(shù)據(jù)元素 ,則 R為空集 ,樹只包含一個根節(jié)點 。tree,elem) treeDelete(amp。 ?性質(zhì) (3)：對任何一棵二叉樹 T，如果其葉節(jié)點數(shù)為 n0，度為 2的節(jié)點數(shù)為 n2，則n0=n2+1。 ② 如果 2i n， 則節(jié)點 i無左孩子 （ 節(jié)點 i是葉子節(jié)點 ） ；否則其左孩子 LCHILD(i)是節(jié)點 2i 。 第二種是孩子表示法 。 樹的典型應(yīng)用 ? 回溯法中的解空間樹與 01背包問題 01背包問題 : 給定 n種物品和一個背包 。 往回移動（回溯）至最近的活節(jié)點處，并使這個活節(jié)點成為當(dāng)前擴展節(jié)點。在最壞情況下，有 O(2N)個右子節(jié)點都需要進(jìn)行預(yù)估，故求解 01背包問題的回溯法時間復(fù)雜度為 O(N*2N)。 ? 基本要求： 熟練掌握二叉樹的 結(jié)構(gòu)特性 ， 了解相應(yīng)的 證明方法 。 學(xué)習(xí)并使用貪心算法與回溯法的思想 。 熟練掌握各種 遍歷策略 的遞歸算法 ，了解遍歷過程中 “ 棧 ” 的作用和狀態(tài) ， 而且能靈活運用遍歷算法實現(xiàn)二叉樹的其他操作 。 考慮節(jié)點帶權(quán)的樹： 節(jié)點的帶權(quán)路徑長度為從該節(jié)點到樹根之間的路徑長度與節(jié)點上權(quán)的乘積。 注 ： 為了避免無效搜索，可使用剪枝函數(shù)把不需要的子樹剪去；使用限界函數(shù)剪去得不到最優(yōu)解的子樹 ,從而提高回溯法的搜索效率。問：應(yīng)該如何選擇裝入背包的物品 ， 使得裝入背包中物品的總價值最大 ？ 要求： 對物品 i只有兩種選擇：要么全部裝入背包，要么全都不裝入背包
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1