计算树的深度和后代

Question

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

深度是从根到底部叶子的边数，所以每次移动时，深度都会加1？类似的事情？

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

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

Answer 1

这是家庭作业的问题吗？我的回答假设这是为了家庭作业。

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

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

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

用于计算后代计数：

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

我鼓励您提出澄清问题。

Answer 2

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

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

对于任一情况，为空指针返回 0 都会结束递归。