线索二叉树解析-CSDN博客

本文链接：https://blog.csdn.net/code_mzh/article/details/107265142

                    
                    在二叉链表中，每个结点都带有leftChild和rightChild,两个指针，而除根结点外，每个结点只被一个指针所对应，要么是leftChild,要么是rightChild.而总共有2n个指针，n是总的节点数，也就是说，**有2n-(n-1)个空指针**，从这个角度，也说明了线索二叉树的必要性。
二叉树是一种非线性结构，对二叉树的遍历实际上是将二叉树这种非线性结构按某种需要转化为线性序列，因为遍历就可以变成数组了。
以便以后在对二叉树进行某种处理时直接使用。因此如何保存遍历二叉树后得到的线性序列，以避免对二叉树的重复遍历，是一个需要解决的问题。
线索二叉树来了，加了前驱和后继的概念，也就是像双向链表一样可以往回找。
 数据结构没有好坏之分，适用场景不同，比如：当路由器使用CIDR，选择下一跳的时候，或者转发分组的时候，通常会用最长前缀匹配（最佳匹配）来得到路由表的一行数据，为了更加有效的查找最长前缀匹配，使用了一种层次的数据结构中，通常使用的数据结构为二叉线索。

为什么要有线索二叉树？