代码之家 › 专栏 › 技术社区 › kostmo

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

clrs binary-search-tree algorithm

kostmo · 技术社区 · 14 年前

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

我只问因为在 Introduction to Algorithms 第二版,第259页,对算法进行了描述。 Tree-Successor(x) 这似乎很奇怪。在查找节点的后续节点时 X ,

[…]如果节点的右子树 X 是空的 X 有接班人 Y 然后 Y 是的最低祖先 X 他的左孩子也是 X .

在根具有键的二进制搜索树中 2 和孩子们 1 和 3 ,的继承人 一 是它的父母 二 . 在这种情况下, X 是的左边的孩子 X 继任者, Y . 根据这本书的定义, X 一定是它自己的祖先,除非我错过了什么。

我没有在 errata 关于这个。

3 回复 | 直到 13 年前

ShreevatsaR 14 年前

这只是一个定义问题,但在这种情况下, 对 . CLR将X的祖先定义为从根到X的唯一路径上的任何节点,根据定义,其中包括X。

你引用的句子片段从下一页的练习12.2-6开始,它规定了这一点:

(请记住,每个节点都是自己的祖先。)

Stephen C 14 年前

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

不正常,阿法克。例如,在维基百科网页上 binary trees , 祖先定义如下:

如果存在从节点p到节点q的路径,其中节点p比q更靠近根节点,那么p是q的祖先,q是p的后代。

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

-1

Ravi Gupta 14 年前

不,节点不是它自己的祖先。我认为应该是:如果X节点的右子树是空的,X有一个继承者Y,那么Y是X的左子树的最低祖先。 either x or an ancestor of x. 但书中给出的代码被认为是处理此类案件的代码。

推荐文章

mourinho · Python中按顺序遍历树返回列表

6 年前

Dongho Han · 用C语言中的二叉搜索树查找合计

6 年前

Richard Cooper · 使用递归的C++二叉搜索树

6 年前

Pranshu · 无法删除二进制搜索树中的根节点

6 年前

user2411290 · BST Delete函数不删除目标节点(Java)

6 年前

Shuklaswag · 为什么我们要通过堆而不是二进制搜索树进行排序?

7 年前

Vanshaj · 给定的数字序列是否有唯一的二进制搜索树?

7 年前

M.Hamra · 如何编写递归函数来返回BST中的最小值?

7 年前

Matt · 二进制搜索树遍历方法,以便字符串

7 年前

I.Klein · 递归获取二叉搜索树的高度[闭合]

7 年前