Question

（高分回报）C语言 数据结构线索二叉树的遍历，为什么没办法打出结果来？在线等，急用

#include <stdio.h>
#include <stdlib.h>
#define OVERFLOW -2
#define OK 1
#define Link 0
#define Thread 1
typedef char TElemType;
typedef int Status;

//************************************
//enum(0, )Link,Thread;
// Link==0:指针，Thread==1:线索
typedef struct BiThrNode
{
TElemType data;
struct BiThrNode *lchild, *rchild; // 左右指针
bool LTag, RTag; // 左右标志
} BiThrNode, *BiThrTree;
BiThrTree pre;
//************************************
Status CreateBiThrTree(BiThrTree *T){
char ch;
ch=getchar();
if (ch=='#') (*T=NULL);
else{
(*T)=(BiThrTree)malloc(sizeof(BiThrNode));
(*T)->data=ch;
(*T)->LTag=(*T)->RTag=Link;
CreateBiThrTree(&(*T)->lchild);
CreateBiThrTree(&(*T)->rchild);
}
return OK;
}
//************************************
void InThreading(BiThrTree p){
if (p) {
InThreading(p->lchild); // 左子树线索化
if (!p->lchild){
p->LTag=Thread;
p->lchild=pre;} // 前驱线索
if (!pre->rchild) {
pre->RTag=Thread;pre->rchild=p;} // 后继线索
pre=p; // 保持pre指向p的前驱
InThreading(p->rchild); // 右子树线索化
}//if
} // InThreading
//************************************
Status InorderThreading(BiThrTree &Thrt, BiThrTree T)
{ if(!(Thrt =(BiThrTree)malloc(sizeof(BiThrNode))))
exit(OVERFLOW);
Thrt->LTag=Link; Thrt->RTag=Thread;
Thrt->rchild=Thrt;

if(!T) Thrt->lchild=Thrt;
else{
Thrt ->lchild=T;
pre=Thrt;
InThreading(T);
pre ->rchild=Thrt;
pre ->RTag=Thread;
Thrt->rchild=pre;
}
return OK;
}

//************************************
void InOrderTraverse(BiThrTree T)
{
BiThrTree p,m;
p = T->lchild; // p指向根结点
printf("%d",p->data);
while (p != T)
{ // 空树或遍历结束时，p= =T
while (p->LTag==Link) p = p->lchild ; // 第一个结点
printf("%c",p->data);
//m=p->
//printf("%c",m->data);

while (p->RTag==Thread && p->rchild!=T)
{//为右线索时找其右线索
p = p->rchild;
printf("%c",p->data); // 访问后继结点
}

p = p->rchild; // p进至其右子树根
printf("%c",p->data);
}
} // InOrder
//************************************
void main(){
BiThrTree T=NULL,Thrt=NULL;
printf("\nCreate a Thread Binary Tree\n");
CreateBiThrTree(&T);
InorderThreading(Thrt,T) ;
InOrderTraverse(T);
}
//************************************
这个函数问题主要是 在遍历中每当往最后一个右孩子的后继移动是就在后继的那个节点处发生溢出。 问题不难，试一试说不定 各位大神就能帮上忙。

Answer 1

在那个生成二叉树哪里写挂了，造成了超出预期的递归循环。。是因为你用的getchar()读取字符造成你输入的时候会把空格当作字符给读进去，所以当然你的程序会递归调用很多次。。。建议你将你的结构体中的data改为char*类型，输入改为读一个字符串，scanf("%s",ch);这样就不会将空格当作输入字符了，因为我们知道scanf是忽略空格的。。。这样改过之后是可以的。。。我在g++下测试了的。。lz试一下。。。

追问

朋友你好，这个问题我已经解决了。但是不是你所说的地方。展示的时候，先序输入一个二叉树，用“#”代表空，输出时全是字母没有#号了。上边的问题是根节点的左孩子可以输出但是根节点和右孩子无法输出。

追答

好吧。。。我以为你输入的时候把空格作为间隔符而造成多次递归了，我没跑你后面的程序，LZ下次可以把问题说清楚点哈。。。呵呵

追问

InOrderTraverse(T);其实把最后一句里的T改成Thrt就完美解决了。

Answer 2

好复杂