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

Question

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

我只问，因为在Introduction to Algorithms，第二版， 259有一个看起来很奇怪的算法Tree-Successor(x)的描述。在找到节点X的后继者，

[...]如果节点的右子树X是空的并且X具有后继ÿ，然后ÿ是最低祖先x其左子女也是x的祖先。

在具有关键2和儿童1和3根二叉搜索树的1的继任者是其母公司2。在这种情况下，x是x的继任者y的左孩子。根据该书的定义，那么，x必须是它自己的祖先，除非我失去了一些东西。

我还没有在errata中发现任何内容。

Answer 1

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

你报的句子片段开始下一个页面，其中指定该上提的练习12.2-6：

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

:-)

Answer 2

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

不正常，AFAIK。例如，在上binary trees Wikipedia页面，祖先被这样定义：

如果路径从节点p存在到节点q，其中节点p是接近小于q根节点，则p是一个q和q的祖先是p的后代。

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

Answer 3

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