algorithm - 树中的节点是否被视为其自己的祖先？

Question

我想知道在计算机科学背景下对“祖先”定义的共识是什么。

我问是因为在Introduction to Algorithms , 第二版, p. 259 算法 Tree-Successor(x) 的描述看起来很奇怪。在寻找节点x的后继者时，

[...] if the right subtree of node x is empty and x has a successor y, then y is the lowest ancestor of x whose left child is also an ancestor of x.

在一个二叉搜索树中，其根具有键 2 和子节点 1 和 3，1 的后继者code> 是它的父级 2。在这种情况下，x 是 x 的后继者 y 的左 child 。那么，根据书中的定义，x 一定是它自己的祖先，除非我遗漏了什么。

我在 errata 中没有找到任何内容关于这个。

Answer 1

这只是一个定义问题，但在这种情况下，是。 CLRS 将 x 的祖先定义为从根到 x 的唯一路径上的任何节点，根据定义，它包括 x。

您引用的句子片段开头提到下一页的练习 12.2-6，具体说明:

(Recall that every node is its own ancestor.)

:-)