计算树的深度和后代

Question

你们能帮我用算法来做这些事情吗？我已经实现了前序、中序和后序，并且我得到了使用这些命令之一遍历树的提示。我正在使用 dotty 来标记（或“访问”）节点。

深度是从根到底部叶子的边数，所以每次移动时，我都会在深度上加+1？类似的东西？

不知道后代的算法。他们正在询问特定节点在其自身下的节点数。

顺便说一句，这些是普通的树。

Answer 1

这是家庭作业的问题吗？我的回答假设它是用于家庭作业。

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

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

• 基本情况：没有子节点的节点的深度是多少？
• 归纳案例：假设您拥有所有子节点的深度（可能不同），那么您正在访问的当前节点的深度是多少？

计算后代计数：

• 基本情况：没有子节点的节点有多少个后代？
• 归纳案例：假设您知道所有孩子的后代计数，那么您正在访问的当前节点的后代计数是多少？

我鼓励你提出澄清问题。