黑客技術(shù)點擊右側(cè)關(guān)注，了解黑客的世界！
Java開發(fā)進階點擊右側(cè)關(guān)注，掌握進階之路！
Python開發(fā)點擊右側(cè)關(guān)注，探討技術(shù)話題！
作者 |? 小鹿
來源 |? 小鹿動畫學(xué)編程（Web_Coding）
題目
給定一棵二叉樹和其中的一個的節(jié)點，如何找出中序遍歷的下一節(jié)點。樹中的節(jié)點除了有兩個分別指向左、右子樹的指針，還有一個指向父節(jié)點的指針。
如：中序遍歷序列為 {d,b,h,e,i,a,f,c,g}。
問題分析
我們根據(jù)題目進行分析，要想求出其中一個樹節(jié)點中序遍歷的下一節(jié)點是什么，我們需要對每個單獨的情況分別進行分析。
根據(jù)中序遍歷的規(guī)律（先遍歷左子節(jié)點，然后遍歷根節(jié)點，最后遍歷右子節(jié)點），下一節(jié)點可能存在的情況如下。
動畫實現(xiàn)
情況一：如果查找的節(jié)點有右子樹，則下一結(jié)點在它右子樹的最左子節(jié)點。如下圖中的 b 節(jié)點的下一節(jié)點為 h 節(jié)點
如果右子樹沒有左子節(jié)點，則下一節(jié)點為右子節(jié)點。如下圖中的 c 節(jié)點的下一節(jié)點為 g 節(jié)點
情況二：如果當(dāng)前節(jié)點沒有右子樹且是父節(jié)點的左子節(jié)點，則它的下一節(jié)點是它的父節(jié)點。如下圖中的 d 節(jié)點的下一節(jié)點為 b 節(jié)點。
情況三：如果當(dāng)前的節(jié)點沒有右子樹且是父節(jié)點的右子節(jié)點。對于這種情況，我們就一直向它的父節(jié)點遍歷，直到找到第一個是父節(jié)點的左子節(jié)點的節(jié)點。如果該節(jié)點的父節(jié)點存在，則父節(jié)點就是要查找的下一節(jié)點。如下圖中的 i 的下一節(jié)點為 a。
再比如沒有找到這樣的節(jié)點，下節(jié)點為空。如圖中的 g 節(jié)點的下一結(jié)點為空。
代碼實現(xiàn)
JavaScript
Java
Python
測試用例
- 普通測試 —— 完全二叉樹、非完全二叉樹
- 特殊測試 —— 只要左子節(jié)點的二叉樹、只有右子節(jié)點的二叉樹、只有一個結(jié)點
- 輸入測試 —— 空節(jié)點
?推薦↓↓↓?
長
按
關(guān)
注
?【16個技術(shù)公眾號】都在這里！
涵蓋：程序員大咖、源碼共讀、程序員共讀、數(shù)據(jù)結(jié)構(gòu)與算法、黑客技術(shù)和網(wǎng)絡(luò)安全、大數(shù)據(jù)科技、編程前端、Java、Python、Web編程開發(fā)、Android、iOS開發(fā)、Linux、數(shù)據(jù)庫研發(fā)、幽默程序員等。
萬水千山總是情，點個 “
在看” 行不行
