C语言数据结构之线索二叉树及其遍历

线索二叉树是在普通二叉树的基础上，对每个结点增加了两个指针，分别指向该结点的前驱和后继。这两个指针被称为线索，构成了线索二叉树的主要特征。

线索化的过程可以在遍历二叉树的过程中同时完成，这样就避免了对整个二叉树进行多次遍历的麻烦。具体的线索化方法，可以根据不同的遍历方式而有所不同。

前序线索化二叉树的实现方法:

1.若结点的左指针为空，则将其左指针指向其前驱结点；

2.若前驱结点的右指针为空，则将其右指针指向该结点；

3.对于右子树结点，需要先将其左子树线索化，然后再将其右子树线索化。

前序线索化的特点是，当指针为空时，无需递归处理左子树和右子树，因此代码的实现比较简单。同时，前序线索化后， 个访问的结点是左下角的叶子结点。因此，可以通过该结点的线索链接，访问整个线索化二叉树。 

中序线索化二叉树的实现方法：

1.对于线索化结点的左子树，在递归下降时，需要将其左指针修改为指向前驱结点，同时在返回时将其右指针修改为指向后继结点。

2.对于后继结点，同样需要在递归上升时，将其右指针指向后继结点。

3.在二叉树的结构发生变化时，需要同时更新其前驱结点和后继结点的右指针。

中序线索化的特点是，线索化后可以方便地实现中序遍历。在访问完一个结点后，直接跳到其后继结点即可。同时，因为线索化后，左子树的左指针和右子树的右指针都指向了前驱结点和后继结点，因此可以方便地实现查找任意结点的前驱和后继。

后序线索化二叉树的实现方法：

1.在递归下降时，需要先将右子树线索化，然后再将左子树线索化。

2.对于线索化结点的左子树，需要将其左指针指向前驱结点。

3.对于线索化结点的右子树，需要将其右指针指向后继结点。

后序线索化的特点是，可以实现后序遍历。在访问完一个结点后，跳转到其前驱结点，即可继续遍历。同时，线索化后可以方便地实现查找任意结点的前驱和后继。

通过对线索二叉树的学习，我们可以看到，线索化遍历可以较为方便地遍历二叉树，同时，线索化后也方便了对其他操作的实现。线索化的过程可以在遍历的基础上同时完成，因此也避免了多次遍历二叉树的麻烦。因此，在二叉树的遍历和其他操作中，线索二叉树都有非常重要的应用。