計算樹的深度和後裔

Question

你們可以幫我用算法來做這些事嗎？我已經執行了前序，中序和後序，並且我得到了用這些命令之一遍歷樹的提示。我使用dotty標籤（或「訪問」）節點。

深度是從根部到底部葉子的邊緣數量，所以每次移動時，我都會向深度添加+1？像那樣的東西？

不知道後代的算法。他們詢問特定節點自身的節點數量。

這些是正常的樹木btw。

Answer 1

depth(tree) = 1+ max(depth(tree.left), depth(tree.right)); 

descendants(tree) = descendants(tree.left) + descendants(tree.right); 

對於任一情況，返回0代表空指針會結束遞歸。

Answer 2

這是一個家庭作業的問題？我的回答假設它是作業。

樹是遞歸數據結構，所以對它們進行操作的算法通常是遞歸的。遞歸算法需要基礎案例和歸納案例。對於樹，基本情況將是您在訪問葉節點時（即沒有孩子的節點）所做的事情。歸納情況將是您在訪問內部節點時（即至少有一個孩子的節點）所做的事情。

爲了計算深度（或樹的「高度」）：

• 基本情況：什麼是沒有孩子的節點的深度？
• 歸納情況：鑑於您的所有孩子的深度（可能不同），您所訪問的當前節點的深度是多少？

爲了計算後代計數：

• 基本情況：有多少後代也沒有孩子的節點有哪些？
• 歸納情況：鑑於您知道所有孩子的後代數，您訪問的當前節點的後代數是多少？

我鼓勵你提出澄清問題。