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

Question

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

我只问是因为在《算法导论》，第二版，p。259 有一个算法的描述Tree-Successor(x)看起来很奇怪。在寻找节点x的后继者时，

[...] 如果节点x的右子树为空且x有后继y，则y是x的最低祖先，其左孩子也是x的祖先。

在一个根有 key2和 children的二叉搜索树1中3， 的后继1是它的 parent 2。在这种情况下，x是x的继任者y的左孩子。那么，根据本书的定义，x必须是它自己的祖先，除非我遗漏了什么。

我在勘误表中没有找到任何关于此的内容。

Answer 1

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

你引用的句子片段首先提到了下一页的练习 12.2-6，它具体说明了这一点：

（回想一下，每个节点都是它自己的祖先。）

:-)

Answer 2

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

不正常，AFAIK。例如，在二叉树的维基百科页面中，祖先是这样定义的：

如果存在从节点 p 到节点 q 的路径，其中节点 p 比 q 更接近根节点，则 p 是 q 的祖先，q 是 p 的后代。

但显然该教科书对祖先的定义是节点是它自己的祖先。这个定义并不完全直观，但教科书可以自由地为其使用的术语引入自己的定义。也许这个定义简化了一些相关的描述/定理/等。

Answer 3

不，节点不是它自己的祖先。根据我的说法，它应该是：如果节点 x 的右子树是空的并且 x 有一个后继 y，那么 y 是 x 的最低祖先，其左孩子是either x or an ancestor of x.但书中给出的代码应该处理这种类型的情况。