樹中的節點是否被認爲是自己的祖先？

Question

我想知道在計算機科學背景下對「祖先」的定義有何共識。

我只問，因爲在Introduction to Algorithms，第二版， 259有一個看起來很奇怪的算法Tree-Successor(x)的描述。在找到節點X的後繼者，

[...]如果節點的右子樹X是空的並且X具有後繼ÿ，然後ÿ是最低祖先x其左子女也是x的祖先。

在具有關鍵2和兒童1和3根二叉搜索樹的1的繼任者是其母公司2。在這種情況下，x是x的繼任者y的左孩子。根據該書的定義，那麼，x必須是它自己的祖先，除非我失去了一些東西。

我還沒有在errata中發現任何內容。

Answer 1

這僅僅是一個定義的問題，但在這種情況下，是的。 CLRS將x的祖先定義爲從根到x的唯一路徑上的任何節點，其根據定義包括x。

你報的句子片段開始下一個頁面，其中指定該上提的練習12.2-6：

（回想一下，每個節點都是自己的祖先。）

:-)

Answer 2

樹中的節點是否被認爲是自己的祖先？

不正常，AFAIK。例如，在上binary trees Wikipedia頁面，祖先被這樣定義：

如果路徑從節點p存在到節點q，其中節點p是接近小於q根節點，則p是一個q和q的祖先是p的後代。

但顯然祖先的是教科書的定義是這樣的：一個節點是自己的祖先。這個定義並不完全直觀，但教科書可以自由地爲其使用的術語介紹自己的定義。也許這個定義簡化了一些相關的描述/定理等。

Answer 3

不，節點不是它自己的祖先。根據我的觀點，它應該是：如果節點x的右側子樹爲空，並且x具有後繼y，則y是x的最低祖先，其左側孩子是either x or an ancestor of x.，但本書中給出的代碼應該處理這種類型的情況。