树中的节点是否被视为其自己的祖先？
我想知道计算机科学背景下对“祖先”定义的共识是什么。
我之所以这么问，是因为在算法简介，第二版，第 14 页中。 259 有一个关于算法Tree-Successor(x)的描述看起来很奇怪。在寻找节点x的后继者时，
[...] 如果节点 x 的右子树为空且 x 有后继 y，则 y 是 x 的最低祖先，其左孩子也是 x 的祖先。
在根具有键 2 以及子元素 1 和 3 的二叉搜索树中，1 的后继是它的父级 2。在本例中，x 是x 的后继者y 的左子级。根据这本书的定义，那么，x一定是它自己的祖先，除非我遗漏了一些东西。
我在勘误表中没有找到任何关于此的内容。
I'm wondering what the consensus is on the definition of "ancestor" in a computer science context.
I only ask because in Introduction to Algorithms, Second Edition, p. 259 there is a description of the algorithm Tree-Successor(x) that seems odd. In finding the successor of node 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.
In a binary search tree with a root having key 2 and children 1 and 3, the successor of 1 is its parent 2. In this case, x is the left child of x's successor, y. According to the book's definition, then, x must be its own ancestor, unless I'm missing something.
I haven't found anything in the errata about this.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
这只是一个定义问题，但在本例中，是。 CLRS 将 x 的祖先定义为从根到 x 的唯一路径上的任何节点，根据定义，该路径包括 x。
您引用的句子片段首先提到下一页的练习 12.2-6，其中指定了这一点：
:-)
It's merely a matter of definition, but in this case, yes. CLRS define an ancestor of x as any node on the unique path from the root to x, which by definition includes x.
The sentence fragment you quoted begins by mentioning exercise 12.2-6 on the next page, which specifies this:
:-)
通常情况下不会，据我所知。例如，在二叉树的维基百科页面中，祖先定义如下：
但显然，教科书对祖先的定义是节点是它自己的祖先。这个定义并不完全直观，但是教科书可以自由地为其使用的术语引入自己的定义。也许这个定义简化了一些相关的描述/定理/等。
Not normally, AFAIK. For example, in the Wikipedia page on binary trees, ancestor is defined thus:
But apparently that text book's definition of ancestor is such that a node is its own ancestor. This definition is not exactly intuitive, but a textbook is free to introduce its own definitions for the terminology that it uses. Maybe this definition simplifies some of the related descriptions / theorems / etc.
不，节点不是其自身的祖先。根据我的说法，它应该是：如果节点 x 的右子树为空并且 x 有后继 y，则 y 是 x 的最低祖先，其左孩子是 x 或 x 的祖先。但书中给出的代码据说可以处理此类情况。
No, a node is not ancestor of itself. According to me it should be: 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
either x or an ancestor of x.but the code given in the book supposedly handling such type of cases.