线索二叉树的构造

首先明确线索二叉树的概念，线索二叉树是原本二叉树n个节点中未分配的n-1个孩子指针改为线索指针，左孩子指向前驱结点，右孩子指向后继节点。

中序线索二叉树的构造就要明确中序遍历：

#include<iostream>
using namespace std;
struct BiTree{
    int date;
    BiTree*lchild,*rchild;
    int ltag,rtag;//如果左孩子是线索则ltag为1
};
void visit(BiTree*t){//visit函数
    cout<<t->date;
}
void InOrder(BiTree*T){//中序遍历
    if(T){
        InOrder(T->lchild);
        visit(T);
        InOrder(T->rchild);
    }
}

以上代码将输入中序遍历的序列，修改添加以下代码：

void InOrder(BiTree*&T,BiTree*&pre){//既然要修改指针的指向，那就一定要用指针的引用
    if(T){
        InOrder(T->lchild,pre);
        if(T->lchild==NULL)//表示指向左子树的指针没有使用，可以用于指向前驱结点
        {
            T->lchild=pre;//改为指向其前驱结点
            T->ltag=1;
        }
        if(pre!=NULL&&pre->rchild==NULL){
            pre->rchild=T;
            pre->rtag=1;
        }
        pre=T;
        visit(T);
        InOrder(T->rchild,pre);
    }
}

函数只是对没有使用的指针做了修改，结果仍然输出的是中序序列，所以函数对二叉树的线索化也是沿着中序遍历的顺序进行的。同理可以写出先序遍历和后序遍历的线索化。

注意：对于最后一个节点，并没有对其线索化，在主函数中要单独修改。