|
|
#2
hzh5122010-05-06 15:04
有4个错误,有两个非常低级的错误。非常不应该发生!
1. if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)))); exit(0); 2. while(p->RTag==Thread&&p->lchild!=T)//访问后继结点 抄书都抄错了,太不应该了! 3. 线索初始化。T->LTag=Link; T->RTag=Link; 4. 指针错误。你要注意,书上的是引用,而你用C,所以要使用二级指针。 下面是已改错的源码: 程序代码:#include <stdio.h>//测试值:abc@@de@g@@f@@@ #include <stdlib.h> #define Link 0 #define Thread 1 typedef char TElemType; typedef struct BiThrNode { TElemType data; struct BiThrNode *lchild,*rchild; int LTag,RTag; }BiThrNode,*BiThrTree; //////// BiThrTree pre;//全局变量 //////// BiThrTree CreatBiThrTree();//先序创建二叉树 void InThreading(BiThrTree p);//中序遍历二叉树 void InOrderThreading(BiThrTree *Thrt,BiThrTree T);//中序线索化二叉树 void Visit(char c); void InorderTraverse_Thr(BiThrTree T);//中序遍历二叉树 void main() { BiThrTree t; BiThrTree thrtnode=NULL; printf("请按先序遍历序列输入二叉树中各个结点的值(字符),若为空树时输入空格键:\n"); printf("<说明:例如参考数据为:abc@@de@g@@f@@@,则用空格键表示@,输完后再输入一个回车键.>\n"); t=CreatBiThrTree(); printf("中序线索化二叉树:\n"); InOrderThreading(&thrtnode,t); printf("线索化工作已经完成!\n"); printf("中序遍历线索二叉树:\n"); InorderTraverse_Thr(thrtnode); } BiThrTree CreatBiThrTree()//先序创建二叉树 { TElemType ch; BiThrTree T; scanf("%c",&ch); if(ch==' ') T=NULL; else { T=(BiThrTree)malloc(sizeof(BiThrNode)); if(!T) exit(0); T->data=ch; T->LTag=Link; T->RTag=Link; T->lchild=CreatBiThrTree(); T->rchild=CreatBiThrTree(); } return T; } 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);//右子树线索化 } } void InOrderThreading(BiThrTree *Thrt,BiThrTree T)//中序线索化二叉树 { if(!((*Thrt)=(BiThrTree)malloc(sizeof(BiThrNode)))) exit(0); (*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; } } void Visit(char c) { printf(" %c ",c); } void InorderTraverse_Thr(BiThrTree T)//中序遍历二叉树 { BiThrTree p; p=T->lchild; while(p!=T)//空树或遍历结束时,p=T { while(p->LTag==Link) p=p->lchild; Visit(p->data);//访问左子树为空的结点 while(p->RTag==Thread&&p->rchild!=T)//访问后继结点 { p=p->rchild; Visit(p->data); } p=p->rchild; } } |
#include <stdio.h>//测试值:abc@@de@g@@f@@@
#include <stdlib.h>
#define Link 0
#define Thread 1
typedef char TElemType;
typedef struct BiThrNode
{
TElemType data;
struct BiThrNode *lchild,*rchild;
int LTag,RTag;
}BiThrNode,*BiThrTree;
////////
BiThrTree pre;//全局变量
////////
BiThrTree CreatBiThrTree()//先序创建二叉树
{
TElemType ch;
BiThrTree T;
scanf("%c",&ch);
if(ch==' ')
T=NULL;
else
{
T=(BiThrTree)malloc(sizeof(BiThrNode));
if(!T)
exit(0);
T->data=ch;
T->lchild=CreatBiThrTree();
T->rchild=CreatBiThrTree();
}
return T;
}
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);//右子树线索化
}
}
void InOrderThreading(BiThrTree Thrt,BiThrTree T)//中序线索化二叉树
{
if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode))));
exit(0);
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;
}
}
void Visit(char c)
{
printf("%c",c);
}
void InorderTraverse_Thr(BiThrTree T)//中序遍历二叉树
{
BiThrTree p;
p=T->lchild;
while(p!=T)//空树或遍历结束时,p=T
{
while(p->LTag==Link)
p=p->lchild;
Visit(p->data);//访问左子树为空的结点
while(p->RTag==Thread&&p->lchild!=T)//访问后继结点
{
p=p->rchild;
Visit(p->data);
}
p=p->rchild;
}
}
void main()
{
BiThrTree t;
BiThrNode thrtnode;
printf("请按先序遍历序列输入二叉树中各个结点的值(字符),若为空树时输入空格键:\n");
printf("<说明:例如参考数据为:abc@@de@g@@f@@@,则用空格键表示@,输完后再输入一个回车键.>\n");
t=CreatBiThrTree();
printf("中序线索化二叉树:\n");
InOrderThreading(&thrtnode,t);
printf("线索化工作已经完成!\n");
printf("中序遍历线索二叉树:\n");
InorderTraverse_Thr(&thrtnode);
}
程序代码: