1 / 9
文档名称:

课题B7:二叉树的中序线索化及其非栈非递归遍历.doc

格式:doc   大小:22KB   页数:9页
下载后只包含 1 个 DOC 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

课题B7:二叉树的中序线索化及其非栈非递归遍历.doc

上传人:Seiryu 2022/1/18 文件大小:22 KB

下载得到文件列表

课题B7:二叉树的中序线索化及其非栈非递归遍历.doc

相关文档

文档介绍

文档介绍:课题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;
}
// 以递归方式