如何求一個二叉排序樹兩個節(jié)點(diǎn)的公共祖先？搜索二叉樹的特點(diǎn)：任意一個節(jié)點(diǎn)的左子樹中所有節(jié)點(diǎn)的值都小于該節(jié)點(diǎn)的值，右子樹中所有節(jié)點(diǎn)的值都大于該節(jié)點(diǎn)的值。要解決此問題：從樹的根節(jié)點(diǎn)開始，比較兩個節(jié)點(diǎn)。如果當(dāng)

如何求一個二叉排序樹兩個節(jié)點(diǎn)的公共祖先？

搜索二叉樹的特點(diǎn)：任意一個節(jié)點(diǎn)的左子樹中所有節(jié)點(diǎn)的值都小于該節(jié)點(diǎn)的值，右子樹中所有節(jié)點(diǎn)的值都大于該節(jié)點(diǎn)的值。

要解決此問題：

從樹的根節(jié)點(diǎn)開始，比較兩個節(jié)點(diǎn)。如果當(dāng)前節(jié)點(diǎn)的值大于兩個節(jié)點(diǎn)的值，則兩個節(jié)點(diǎn)最近的共同祖先節(jié)點(diǎn)必須在該節(jié)點(diǎn)的左子樹中，則下一步是遍歷當(dāng)前節(jié)點(diǎn)的左子樹；

如果當(dāng)前節(jié)點(diǎn)的值小于兩個節(jié)點(diǎn)的值，則最近的共同祖先節(jié)點(diǎn)兩個節(jié)點(diǎn)的節(jié)點(diǎn)必須在該節(jié)點(diǎn)的左子樹中祖先節(jié)點(diǎn)必須在該節(jié)點(diǎn)的右子樹中，下一步是遍歷當(dāng)前節(jié)點(diǎn)的右子樹，直到找到第一個值為2為止

二叉排序樹也稱為二叉搜索樹

算法步驟：[S1:如果樹為空（第一個元素到達(dá)），根節(jié)點(diǎn)用該元素建立

S2:二進(jìn)制搜索到葉節(jié)點(diǎn)

S2.1:如果葉節(jié)點(diǎn)關(guān)鍵字大于待插入節(jié)點(diǎn)關(guān)鍵字，則將待插入節(jié)點(diǎn)的關(guān)鍵字設(shè)為其左子項(xiàng)

否則，成為它的右子級

S3:重復(fù)步驟S2，直到所有節(jié)點(diǎn)都被插入

時(shí)間復(fù)雜度：通過二進(jìn)制搜索找到要插入位置的每個節(jié)點(diǎn)的復(fù)雜度為O（LGN），因此總復(fù)雜度為O（nlgn）]//希望對您有用