java - ADT 树 - 是节点的祖先/后代吗？

Question

我会开始说，Stack Overflow 上还有一个关于此问题的问题，但我找不到真正的答案，因为与该问题相关的所有答案都彼此不同，这真的让我感到困惑我已经是。我的问题是这样的，谈论抽象数据类型 - 树(正常的不是二叉树，在 Java 编程中，以防万一它有所不同)。

1) 树的节点是其自身的祖先/后代吗？

假设我查找了祖先的定义，结果是这样的变体:

“通过重复从子节点到父节点可到达的节点”

“节点的祖先是:它自己，它的父节点，或者它的父节点本身的祖先”

“只有在以下情况下，节点 U 才是节点 V 的祖先: U = V 或 U 是 V parent 的祖先”

2)“祖先”是否有一个通用的定义，或者两个定义(包括节点本身或不包括节点本身)都是正确的？

3)如果节点本身不被视为自身的祖先，那么节点深度的定义是否等于其祖先的数量？

Answer 1

您可以从定义极其明确的 XPath 中使用的轴命名法中获得灵感。推荐:

给定树中的一个节点(即上下文节点)，规范定义轴，即相对于上下文节点的节点集:

• 子轴包含上下文节点的子节点
• 后代轴包含上下文节点的后代；后代是 child 或 child 的 child 等等；
• 父轴包含上下文节点的父节点(如果有)
• 祖先轴包含上下文节点的祖先；上下文节点的祖先由上下文节点的父节点和父节点的父节点组成，依此类推；因此，祖先轴将始终包含根节点，除非上下文节点是根节点

由于有时对后代或祖先(包括上下文节点)进行操作很有用，因此它还定义了:

• 后代或自身轴包含上下文节点和上下文节点的后代

• ancestor-or-self 轴包含上下文节点和上下文节点的祖先；因此，祖先轴将始终包含根节点

此模型可以回答您的问题 1。其他模型可能有所不同。Q2:无法回答。 Q3:仅仅取决于深度是如何定义的。