是树的一个节点认为自己的祖先？ [英] Is a node in a tree considered its own ancestor?

问题描述

我想知道的共识是在计算机科学方面的始祖的定义是什么。

I'm wondering what the consensus is on the definition of "ancestor" in a computer science context.

我只问，因为在算法导论，第二版，页。 259有算法树后继（X）这似乎很奇怪的描述。在发现节点的继任者的 X 的

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,

[...]如果将节点的 X 的右子树是空的， X 的有后继的是的，然后的ÿ 的是 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 的继任者是它的父 2 。在这种情况下，的 X 的是 X 的的继任者，是的左侧子。按照书上的定义，那么，的 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.

推荐答案

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

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.

这句话片段你报一开始就提到运动12.2-6下一个页面，它指定该上：

The sentence fragment you quoted begins by mentioning exercise 12.2-6 on the next page, which specifies this:

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

(Recall that every node is its own ancestor.)

： - ）

这篇关于是树的一个节点认为自己的祖先？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！