上一章我们讲解了二叉树的创建和遍历，这一章就可以放开手脚大干一场了
线索二叉树
什么是线索二叉树：二叉链表中有2n个指针域，其中n+1个指针域存放的都是NULL，我们要把这些指针域利用起来，存放节点的前驱和后继。
用处：对二叉树遍历的过程实质上是对一个非线性结构进行线性化的操作，以二叉链表为存储结构时,结点的左右孩子可以直接找到,但不能直接找到结点的前驱和后继,而结点的前驱和后继只有在遍历二叉树的过程中才能得到，效率低下。在后面的中序查找和平衡二叉树中会非常有用。
结点结构
我们在原有节点的基础上又添加了LeftThread和RightThread两个标志位，因为我们需要区分每个节点的指针域内的指针究竟是指向它的孩子还是指向它的前驱或者后继。虽然增加了空间，但是减少了时间
LeftThread=0, LeftChild指向左孩子
LeftThread=1, LeftChild指向前驱
RightThread=0, RightChild指向右孩子
RightThread=1, RightChild指向后继
//
typedef enum {Link,Thread} PointerTag;
typedef struct Node
{
char val;
struct Node *lChild,*rChild;
PointerTag lThread = Link,rThread = Link;//c11标准才允许初始化
} BiTreeNode,*BiTree;
//
二叉树线索化
不同的遍历顺序，每个节点的前驱和后继自然也不一样
中序线索化二叉树
后继：结点标志为1时，其右指针为其后继；结点标志为0时，其右子树最左下结点为其后继。
前驱：结点标志为1时，其左指针为其前驱；结点标志为0时，其左子树最右下结点为其前驱。
//
//pre是一个全局变量，时刻指向当前节点的前驱元素
void inThreadBiTree(BiTree T)
{
if(T == NULL) return;//空树返回
//中序线索化左子树
if(T->lChild)//可以不加，前面有判空
inThredBiTree(T->lChild);
//线索化根节点
if(!T->lChild)//该节点如果左孩子为NULL
{
T->lThread = Thread;//更改标志位
T->lChild = pre;//左指针指向前驱元素
}
if(!pre->rChild)//如果前驱元素的右孩子为NULL
{
pre->rThread = Thread;//更改标志位
pre->rChild = T;//右孩子指向后继元素
}
pre = T;//该节点成为下一个节点的前驱元素
//中序线索化右子树
if(T->rChild)
inThreadBiTree(T->rChild);
}
//
我们根据下图来看一下上面代码的思路，中序线索化和中序遍历思路一样一样的，我们其实只需要修改中序遍历中的visit也就是访问函数即可，具体来看一下 继续阅读
