关于线索二叉树

一般的数据结构教材，不会有线索二叉树。

线索二叉树是一个很“专门”的数据结构，其主要作用是更加高速的做非递归遍历（尤其是中序遍历），以及更加高速的寻找节点的前驱或者后继（尤其是中序遍历的前驱或者后继）这样的操作。因为其主要目的是更加苛刻的高性能需求（要考虑递归的时间和空间消耗），所以主要应用于数据库底层的结构（数据量更大，但现代数据库的底层主要是 b 树），或者编译器底层的结构。（编译器对中序遍历需求较高）

我没有见过任何的软件工程相关面试会问到线索二叉树；对于各种机试网站（比如力扣），或者算法竞赛（比如 ACM），我也没见过需要一定使用线索二叉树的问题；对于近乎所有的语言提供的 sdk，甚至是更进一步的语言的拓展包，近乎都不会见到线索二叉树的影子。甚至通常面向研究生或者博士生的高级数据结构教程，都不会出现线索二叉树。比线索二叉树重要且应用更广泛的高级数据结构还有很多。

对于线索二叉树，远远超过了“计算机基础”的范畴，我的建议是，在实际项目或者具体的领域中，遇到这个需求，再做具体学习。其实，这本身也是学习算法与数据结构的核心目的。学习算法和数据结构的目的不是吧这个世界上所有的算法和数据结构都实现出来，而是掌握理解基础的算法和数据结构的思想。将来当你在更加具体的计算机领域遇到各种“奇奇怪怪”的数据结构的时候，可以有能力把它搞明白。

继续加油！：）