我想知道计算机科学背景下对“祖先”定义的共识是什么。
我问只是因为在算法简介 http://en.wikipedia.org/wiki/Introduction_to_Algorithms，第二版，第 14 页。第259章 有算法的描述Tree-Successor(x)这看起来很奇怪。在寻找节点的后继者时x,
[...]如果节点的右子树x是空的并且x有继任者y, then y是最低祖先x谁的左孩子也是x.
在二叉搜索树中，根具有键2和孩子们1 and 3, 的继承者1是它的父级2。在这种情况下，x是的左孩子x的继任者，y。那么根据书上的定义，x一定是它自己的祖先，除非我错过了什么。
我还没有找到任何东西errata http://www.cs.dartmouth.edu/~thc/clrs-bugs/bugs.php对这个。
这只是一个定义问题，但在这种情况下，yes。 CLRS 将 x 的祖先定义为从根到 x 的唯一路径上的任何节点，根据定义，该路径包括 x。
您引用的句子片段首先提到下一页的练习 12.2-6，其中指定了这一点：
（回想一下，每个节点都是它自己的祖先。）
:-)
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
