效益線索二叉樹

Question

的螺紋二叉樹的文檔，我讀

兩個二叉樹遍歷的遞歸和非遞歸程序要求指向所有的自由節點上堆棧暫時保持。這可以通過使用螺紋二叉樹

我的問題是可以避免的

1-如何以及何時指針保存在棧中的普通二叉樹？

2-如何不在螺紋二叉樹中的堆棧中添加指針？

Answer 1

1）他們正在談論走樹。您可以使用recusrive算法（使用CPU堆棧爲您跟蹤事物），也可以使用迭代方法並保留數據結構堆棧並管理需要訪問的節點。後者可能執行得更好，因爲您可以消除函數調用的開銷，但在概念上往往難以理解。

2）一個線程樹會保存如何在樹中本身行走樹的信息（而不是指向樹中下一個位置的NULL指針，它們必須返回它們的行走路徑），這可以讓您「直線行」樹，因此不需要堆疊。

的wiki page確實顯示這一點做得非常好。

-A