按照中序排序,求二叉樹的下一個(gè)結(jié)點(diǎn)。
分析下一個(gè)結(jié)點(diǎn):
(1)如果當(dāng)前結(jié)點(diǎn)存在右結(jié)點(diǎn)嗜傅, 那么它的下一個(gè)結(jié)點(diǎn)就是它的右子樹的最左子結(jié)點(diǎn);
(2)如果當(dāng)前結(jié)點(diǎn)不存在右結(jié)點(diǎn)檩赢,并且它還是它父結(jié)點(diǎn)的左結(jié)點(diǎn)吕嘀,那么下一個(gè)結(jié)點(diǎn)是 父結(jié)點(diǎn) ;
(3)如果他是它父結(jié)點(diǎn)的右子結(jié)點(diǎn)贞瞒,那么我們就需要往上找币他,直到找到是它父結(jié)點(diǎn)的左子結(jié)點(diǎn),如果這個(gè)結(jié)點(diǎn)存在憔狞,那么這個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)就是我們要找的結(jié)點(diǎn)蝴悉。
參考代碼