算法合集之樹的枚舉(編輯修改稿)
2024-11-12 20:32 本頁面
【文章內(nèi)容簡介】 是否可認(rèn)為該結(jié)點的最后一個子結(jié)點為待刪除結(jié)點呢？事實上仍需進一步處理： 假如，找到的待刪除結(jié)點 A為其父親 B唯一的子結(jié)點，也就意味著如果將 A從它的父結(jié)點 B刪除，那么以 B為根的那棵子樹的深度將會減少 1…… ? 在對樹的大小定義中，深度比結(jié)點數(shù)更優(yōu)先。所以，在選擇待刪除結(jié)點時，應(yīng)該 盡量選擇刪除后不影響子樹深度的結(jié)點 優(yōu)先處理。 ? 因此，在找到 A結(jié)點后，必須沿其父親結(jié)點進行回溯，直到當(dāng)前結(jié)點以下的子樹的深度不因刪除 A而改變?yōu)橹梗ㄔ谏蠄D中直到 D結(jié)點），在回溯的過程中，如果經(jīng)過某一結(jié)點，它還有另一個子結(jié)點（比如上圖中的 C，它還有另一個子結(jié)點 E），那么就舍棄原來找到的結(jié)點 A，把 E定為待刪除的結(jié)點。 過程 I 算法 如果將 A從 B斷開 ， 則以 B、C為根的子樹的深度都會受到影響 。 C 有子結(jié)點 E ，E→ Target 回溯 找到 A ，A→ Target 過程 II 將被刪的結(jié)點重組到后面的子樹中 ? 在找到該結(jié)點并刪除之后，又需要進行一系列的處理以形成一棵新的樹。在建立新樹的時候要強調(diào)的一點就是，“要使整棵樹變小，但變小的幅度必須達到最小”。 刪除一個結(jié)點之后，會出現(xiàn)兩種情況： ? 當(dāng)前子樹深度不變，結(jié)點數(shù)變??； ? 或者子樹深度變小 。 下面就對這兩種情況分別進行討論。 過程 II 算法 刪除結(jié)點后子樹深度不變 ? 接下來，對排列在被改動的這棵子樹以后
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1