文档介绍：课题B7：二叉树的中序线索化及其非栈非递归遍历
/*
Author: corpio
E-mail: ******@, ******@
QQ: 1027690187
Address:上海;
else
p->rtag = 1;
p->rchild = q;
return p;
}
else
return NULL;
}
// 以递归方式对二叉树进行中序线索化
BiNode *InOrderThread(BiTree T, BiNode *pre, BiNode *rear)
{
//pre指向整个二叉树T的前驱，rear指向整个二叉树T的后继
if( NULL == T->lchild )
{
T->ltag = 0;
T->lchild = pre;
}
else
{
T->ltag = 1;
InOrderThread( T->lchild, pre, T);
}
if( NULL == T->rchild )
{
T->rtag = 0;
T->rchild = rear;
}
else
{
T->rtag = 1;
InOrderThread( T->rchild, T, rear);
}
return T;
}
// 以非栈非递归方式对线索二叉树进行中序遍历
void NoRecursionInOrder(BiTree T)
{
BiNode *p;
p = T;
if(p!=NULL)
{
// 1、先通过循环一直向左指，直到找到中序序列的第一个节点
while(p->lchild != NULL)
p = p->lchild;
// 2、先输出找到的中序序列第一个节点
printf("%3c", p->data);
// 3、找当前节点的后继:如果p所指的当前节点的右孩子存在，
// 则当前节点的后继为其右子树中最左边的节点，
// 反之，p所指当前节点的右指针所指即为后继
while(p->rchild != NULL)
{
if(p->rtag == 0) //右孩子不存在，p->rchild即为后继结点
p = p->rchild;
else //右孩子存在，则右子树最左边的结点即为后继结点
{
p = p->rchild;
while(p->ltag == 1)
p = p->lchild;
}
// 输出找到的后继结点
printf("%3c", p->data);
}
}
}
// 以递归方式对线索二叉树进行先序遍历
void PreOrder(BiTree T)
{
if( NULL != T )
{
printf("%3c",T->data);
if( 1 == T->ltag )
PreOrder( T->lchild );
if( 1 == T->rtag )
PreOrder( T->rchild );
}
else
return;
}
// 以递归方式