二叉树链表中有很多空指针，比如叶子节点，会有左右孩子两个空指针。如何把这些空指针利用起来呢？那就是线索二叉树

在这些节点上，可以存储按照二叉树某种遍历顺序的前后节点，这样就不需要每次都遍历二叉树，从而快速点位节点。

哪一种遍历顺序是最有效的呢？要求是最好有两个空指针的节点在非空节点的中间，这样就可以记录前前驱后继节点。 这个遍历方法叫中序遍历方法。这样包含线索的二叉树，叫做线索二叉树

线索二叉树节点

因为不是所有的节点都包含两个空指针，如果只含有一个空指针的时候，就无法判断，另一个非空指针是指向前驱或者后继或者是孩子节点，所以，在节点结构中增加2bit，用于指示是指针的类型。

线索二叉树的实现

首先定义数据类型

定义节点：注意枚举的使用，默认从0开始

只有构建了线索二叉树，才能使用非迭代的方法，通过前驱和后继的方法，通过迭代遍历二叉树 。

线索二叉树其实是一个线性双循环链表，里面有一个很关键的头结点，这个是线性表中的结构，不同于根节点