26线索二叉树的构造

1、 线索二叉树的构造：对于二叉树的线索化，实质就是遍历一次二叉树，只是在遍历的过程中，检查当前节点左、右指针域是否为空，若为空，将它们改为指向前驱结点或后继结点的线索。

2、 通过中序遍历对二叉树线索化的递归算法如下： Void InThread(ThreadTree &p,ThreadTree &pre){ If(p!=NULL){ InThread(p->lchild,pre);//递归，线索化左子树 If(p->lchildNULL){//左子树为空，建立前驱 p->lchild=pre; p->ltag=1; } If(pre!=NULL&&pre->rchildNULL){ pre->rchild=p; //建立前驱结点的后继线索 pre->rtag=1; } pre=p; InThread(p-rchild,pre); }//if(p!=NULL) } 3、 通过中序遍历建立中序线索二叉树的主过程描述代码 Void createInThread(ThreadTree T){ ThreadTree pre=NULL; If(T!=NULL){ //非空二叉树，线索化 InThread(T,pre); //线索化二叉树 Pre->rchild=NULL;//处理遍历的最后一个结点 Pre->rtag=1; } }