线索二叉数中序非递归求助
【求助帖】请及时确认最佳答案，下次提问时可以得到更多关注，问题可以更快解决
include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR -1
typedef char TElemType;#
typedef int Status;
//线索存储标志位
//Link(0):表示指向左右孩子结点的指针
//Thread(1):表示指向前驱后继的线索
typedef enum {Link,Thread} PionterTag;
typedef struct BiThrNode
{
TElemType data;
struct BiThrNode *lchild,*rchild;
PionterTag ltag;
PionterTag rtag;
}BiThrNode,*BiThrTree;
Status CreateBiThrTree(BiThrTree &T);
void InThreading(BiThrTree T);
void Visist(char ch);
void InOrderThreading(BiThrTree &p,BiThrTree T);
void InOrderTraverse_Thr(BiThrTree T);
//全局变量，始终指向刚刚访问过的结点
BiThrTree pre;
//创建一棵二叉树，预定前序遍历输入数据
Status CreateBiThrTree(BiThrTree &T)
{
char ch;
scanf("%c",&ch);
if('@' == ch)
{
T = NULL;
}
else
{
if(!(T = (BiThrNode*)malloc(sizeof(BiThrNode))))
return ERROR;
T->data = ch;
//初始化
T->ltag = Link;
T->rtag = Link;
//递归调用创建子树
CreateBiThrTree(T->lchild);
CreateBiThrTree(T->rchild);
}
return OK;
}
//中序遍历线索化
void InThreading(BiThrTree T)
{
if( T )
{
InThreading(T->lchild);//递归左孩子线索化
/*
结点处理
*/
Visist(T->data);
if( !T->lchild )//没有左孩子时让它指向前驱(即刚访问过的结点)
{
T->ltag = Thread; //标志tag为线索
T->lchild = pre;
}
if( !pre->rchild )//前驱没有右孩子的时候，让它指向它的后继即当前这个结点
{
pre->rtag = Thread;
pre->rchild = T;
}
pre = T;//更新结点
InThreading(T->rchild);//递归右孩子线索化
}
}
//中序遍历线索化
void InOrderThreading(BiThrTree &p,BiThrTree T)
{
/*
p为头结点，指向根结点
*/
p = (BiThrTree)malloc(sizeof(BiThrNode));
p->ltag = Link;//指向头结点的指针
p->rtag = Thread;//作为线索
p->lchild = p;
p->data = '%';
if( !T )
{
p->lchild = p;
}
else
{
p->lchild = T;
//初始化pre
pre = p;
InThreading(T);
/*
收尾工作，
即若
前序遍历结果为：A B C D E F
中序遍历结果为: C B D A E F
在中序的线索化遍历结束后F要指向我们的p(头结点)
*/
pre->rchild = p;
pre->rtag = Thread;
p->rchild = pre;
}
}
void Visist(char ch)
{
printf("%c ",ch);
}
//中序遍历二叉树，非递归
void InOrderTraverse_Thr(BiThrTree T)
{
//T 为头结点
BiThrTree p;
p = T->lchild;
while( p != T)
{
// printf("111\n");
while(p->ltag == Link)
{
p = p->lchild;
}
Visist(p->data);
while(p->rtag == Thread && p->rchild !=T)
{
p = p->rchild;
Visist(p->data);
}
p = p->rchild;
}
}
int main()
{
BiThrTree p=NULL,T = NULL;
CreateBiThrTree(T);
printf("中序遍历,并且线索化该二叉树：\n");
InOrderThreading(p,T);
printf("\n\n\n");
printf("中序遍历(非递归实现)结果为：\n");
InOrderTraverse_Thr(p);
printf("\n\n\n");
return 0;
}
https://blog.csdn.net/qq_33883389/article/details/81784409这是代码的原帖子
整个语言大部分都理解，但问题在标红字的地方，请问在语句while(p->rtag == Thread && p->rchild !=T)中为什么需要有p->rtag == Thread？
我认为如果这样写的话走到有右孩子的结点就走不下去了（即我觉得不是所有结点rtag都是thread，这样走走不全）
想了很久也没想出来，万分感谢 {:5_109:} {:5_109:} {:10_315:}
页:
[1]