對樹的遍歷迭代方法

Question

有人能幫助我的算法遍歷一個二叉樹反覆，而無需使用任何其他數據結構就像一個堆棧

我讀的地方，我們可以有一個名爲參觀了每一個節點的標誌如果訪問節點但我的BinaryTreeNode類沒有定義訪問變量，則開啓。所以我不可能做一些像node.left.visited = false

是否有任何其他方式來遍歷迭代？

Answer 1

一個選項是thread二叉樹。當某個節點指向NULL（無論是左還是右）時，使該節點指向其遍歷中的下一個節點（預定單，後期定單等）。通過這種方式，您可以在一次迭代中遍歷整個樹。

樣品線索二叉樹：

注意左側的每個節點分節點小於它的最大價值。每個節點的右邊節點指向的最大值比它大。所以這給出了一個有序的遍歷。