树中的节点是否被视为自己的祖先?
我想知道在计算机科学背景下对“祖先”定义的共识是什么。
我只是问,因为在算法导论,第二版,p。 259有一个看似奇怪的算法
Tree-Successor(x)
的描述。在寻找节点x的后继者时,
[...]如果节点x的右子树为空并且x具有后继y,则y是x的最低祖先,其左子节点也是x的祖先。
在具有键2
和子1
和3
的根的二叉搜索树中,1
的后继是其父2
。在这种情况下,x是x的后继者y的左子。根据这本书的定义,x必须是它自己的祖先,除非我遗漏了什么。
关于这一点,我没有在勘误表中找到任何内容。
没有找到相关结果
已邀请:
3 个回复
车料
宦哨抹存胳
氏脑
但是书中给出的代码据称处理这种类型的情况。