算法合集之樹的枚舉-在線瀏覽
2024-12-03 20:32本頁面
【正文】 和最后一棵樹的形態(tài)是容易確定的，如下： ? 現(xiàn)在問題就轉(zhuǎn)化為，根據(jù)上述的大小定義，能否找到一種變換的規(guī)則，使根據(jù)這種規(guī)則，可以從最小的一棵樹開始，連續(xù)地、不遺漏不重復(fù)地生成接下來的所有不同形態(tài)的樹？ ? 首先，從樹的序列中的一個形態(tài)變換到另一個形態(tài)，是一個變小的過程。 變換過程 ? 它們會適當(dāng)?shù)刈兇螅欢捎谒鼈冊谟邢驑浯笮”容^的過程中的地位比先前被變小的那棵子樹要低，于是，總的說來，整個有向樹就被變小了。 ?過程 I 尋找被刪去結(jié)點 ?過程 II 將被刪的結(jié)點重組到后面的子樹中 過程 I 尋找被刪去結(jié)點 ? 在選擇被刪去的結(jié)點時，其所在子樹的變小對于整棵樹的影響必須盡量小。所以： ? 首先，這個被奪取的結(jié)點必然為葉結(jié)點。 過程 I 算法 ? 從根出發(fā)，在子結(jié)點中從后向前找到第一個非葉結(jié)點的結(jié)點，繼續(xù)搜索直到到達(dá)一個子結(jié)點均為葉子的結(jié)點為止。所以，在選擇待刪除結(jié)點時，應(yīng)該 盡量選擇刪除后不影響子樹深度的結(jié)點 優(yōu)先處理。 過程 I 算法 如果將 A從 B斷開 ， 則以 B、C為根的子樹的深度都會受到影響 。在建立新樹的時候要強調(diào)的一點就是，“要使整棵樹變小，但變小的幅度必須達(dá)到最小”。 下面就對這兩種情況分別進(jìn)行討論。 刪除結(jié)點 ， 使子樹變小 將后面的子樹重組 （ 最大化 ） 變換完成 過程 II 算法 刪除結(jié)點后子樹深度變小 ? 對于刪除結(jié)點后子樹深度改
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1