线索二叉树在遍历上的胜势到底在哪
线索二叉树在遍历上的优势到底在哪？
刚刚看到书上说，如果二叉树需要经常遍历，则采用线索二叉树是不错的选择，但是我发现直接中序遍历和中序线索化后遍历线索二叉树的时间复杂度都是O(n)，那么感觉在遍历上面没什么很大区别，只是在查找前驱和后继上有很大的优势（无需重新遍历整个二叉树了）各位大大们告诉小弟一下在遍历上的优势究竟在哪里...
如果没有什么区别，那可不可以和一般的遍历一样，只不过左右孩子是否为NULL的判定改为rtag和ltag标志是否为1的判定，沿用递归算法
------解决方案--------------------
不要迷信书、考题、老师、回帖；
要迷信CPU、编译器、调试器、运行结果。
并请结合“盲人摸太阳”和“驾船出海时一定只带一个指南针。”加以理解。
任何理论、权威、传说、真理、标准、解释、想象、知识……都比不上摆在眼前的事实！
有人说一套做一套，你相信他说的还是相信他做的？
其实严格来说这个世界上古往今来所有人都是说一套做一套，不是吗？
不要写连自己也预测不了结果的代码！
无profiler不要谈效率！！尤其在这个云计算、虚拟机、模拟器、CUDA、多核 、多级cache、指令流水线、多种存储介质、……满天飞的时代！
------解决方案--------------------
看wiki吧
http://en.wikipedia.org/wiki/Threaded_binary_tree
实际上 O() 是一个很粗糙的复杂度定义，因为它表示的是最差情况下的开销，并且忽略了常数因子。它适用于理论讨论中还好些，对于实践应用有时候就会有很大的偏差。在实践应用场合，一个O(n^2)的算法快过O(n)都很正常。
刚刚看到书上说，如果二叉树需要经常遍历，则采用线索二叉树是不错的选择，但是我发现直接中序遍历和中序线索化后遍历线索二叉树的时间复杂度都是O(n)，那么感觉在遍历上面没什么很大区别，只是在查找前驱和后继上有很大的优势（无需重新遍历整个二叉树了）各位大大们告诉小弟一下在遍历上的优势究竟在哪里...
如果没有什么区别，那可不可以和一般的遍历一样，只不过左右孩子是否为NULL的判定改为rtag和ltag标志是否为1的判定，沿用递归算法
------解决方案--------------------
不要迷信书、考题、老师、回帖；
要迷信CPU、编译器、调试器、运行结果。
并请结合“盲人摸太阳”和“驾船出海时一定只带一个指南针。”加以理解。
任何理论、权威、传说、真理、标准、解释、想象、知识……都比不上摆在眼前的事实！
有人说一套做一套，你相信他说的还是相信他做的？
其实严格来说这个世界上古往今来所有人都是说一套做一套，不是吗？
不要写连自己也预测不了结果的代码！
无profiler不要谈效率！！尤其在这个云计算、虚拟机、模拟器、CUDA、多核 、多级cache、指令流水线、多种存储介质、……满天飞的时代！
------解决方案--------------------
看wiki吧
http://en.wikipedia.org/wiki/Threaded_binary_tree
实际上 O() 是一个很粗糙的复杂度定义，因为它表示的是最差情况下的开销，并且忽略了常数因子。它适用于理论讨论中还好些，对于实践应用有时候就会有很大的偏差。在实践应用场合，一个O(n^2)的算法快过O(n)都很正常。