计算树的深度和后裔

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

这是一个家庭作业的问题？我的回答假设它是作业。

树是递归数据结构，所以对它们进行操作的算法通常是递归的。递归算法需要基础案例和归纳案例。对于树，基本情况将是您在访问叶节点时（即没有孩子的节点）所做的事情。归纳情况将是您在访问内部节点时（即至少有一个孩子的节点）所做的事情。

为了计算深度（或树的“高度”）：

• 基本情况：什么是没有孩子的节点的深度？
• 归纳情况：鉴于您的所有孩子的深度（可能不同），您所访问的当前节点的深度是多少？

为了计算后代计数：

• 基本情况：有多少后代也没有孩子的节点有哪些？
• 归纳情况：鉴于您知道所有孩子的后代数，您访问的当前节点的后代数是多少？

我鼓励你提出澄清问题。