主题：怎样去建立中序线索？就是用中序遍历建立？
Jasperu
[专家分：80] 发布于 2010-05-05 10:45:00
#include "stdio.h"
#include "stdlib.h"
#define A sizeof(struct tree)
#define B 20
typedef struct tree
{
char data;
struct tree *lchild,*rchild;
}tr,*tre;
tr *creat()
{ tre t;
char c;
scanf("%c",&c);
if(c=='#')
t=NULL;
else
{ if((t=(tr * )malloc(A))==NULL)
{ printf(" fen peishi bai :");
getch();
exit(0);
}
else
{ t->data=c;
t->lchild=creat();
t->rchild=creat();
}
}
return t;
}
/* 这个是中序遍历了，*/
void ordsert2(tre t)
{ tre s[B],p;
int top=0;
p=t;
do
{ while(p!=NULL)
{ s[top++]=p;
p=p->lchild;
}
if(top>0)
{ p=s[--top];
printf("%2c",p->data);
p=p->rchild;
}
}while(top>0||p!=NULL);
}
现在我已经建立了一个二叉树，前序建立，然后我也写出了他的中序遍历的算法，但是，我不知道的就是，该怎样去建立这个二叉树的线索？难道是在修改？
这个是我摘抄的书上的：建立线索而产生的 算法
void inthreat(tre bt,tre *h)
{ if(bt!=NULL)
{ inthreat(bt->lchild,h);
if(bt->lchild==NULL)
{ bt->lchild=*h;
bt->ltag=1;
}
if((*h!=NULL)&&((*h)->rchild==NULL))
{ (*h)->rchild=bt;
(*h)->rtag=1;
*h=bt;
inthreat(bt->rchild,h);
}
}
/*访问穿线二叉树*/
treinsuc(tre p)
{ /* 在中序中寻找p的后继*/
tre s;
s=p->rchild;
if((p->rtag==)&&(s!=NULL))
while(s->ltag==0)
s=s->lchild;
return s;
}
/*对中序穿线二叉树，进行中序遍历*/
void innoder(htnode ht)
{
tre t;
t=ht;
while(t->lchild!=NULL)/*寻找第一个节点*/
t=t->lchild;
do
{ printf("%c",t->data);
t=insuc(t);/* 查找p的后继*/
}
while(t!=NULL);
}
但是， 我不明白的就是，这个线索导致是怎样建立的，？》是单独写一个程序，还是用中序的遍历的结果写出的？
回复列表 （共1个回复）
沙发
Jasperu [专家分：80] 发布于 2010-05-06 14:42:00
/* 建树*/
#include "stdio.h"
#include "malloc.h"
#include "stdlib.h"
#define A sizeof(struct tree)
#define B 20
typedef struct tree
{
char data;
struct tree *lchild,*rchild;
int ltag,rtag;
}tr,*tre;
tre pre;/*定义一个 全局变量然后起到之时的作用*/
tr *creat()
{ tre t;
char c;
scanf("%c",&c);
if(c=='#')
t=NULL;
else
{ if((t=(tr * )malloc(A))==NULL)
{ printf(" fen peishi bai :");
getch();
exit(0);
}
else
{ t->data=c;
t->rtag=NULL;/* 对指针进行初始化，防止出现错误*/
t->ltag=NULL;
t->lchild=creat();
t->rchild=creat();
}
}
return t;
}
/* 这个是在进行建立线索二叉树*/
void inter(tre t)
{
tre p;
p=t;
if(p)
{ inter(p->lchild);
if(!p->lchild)/*其实意思是在p->lchild==NULL,表示在其左子树为空时*/
{ p->ltag=1;/*标记左为1，表示不指向左子树，而时指向其前驱*/
p->lchild=pre;/* 标记pre为*/
}
if(!pre->rchild)/* 就是if(pre->rchild==NULL*/
{ pre->rtag=1;
pre->rchild=p;
}
pre=p;
inter(p->rchild);
}
}
/* 下面是中序线索化二叉树*/
tre noder(tre t)
{ tre p;/* p指向头节点*/
p=(tre )malloc(A);
p->lchild=t;/* t指向根节点*/
p->rchild=p;/* 跟指针的佑子树回指*/
pre=p;/* per指针指向头结点*/
inter(t);/* 开始进行线索化*/
pre->rtag=1;
pre->rchild=p;
p->rchild=pre;
return p; /* 返回头结点*/
}
/* 开始中序遍历二叉树*/
void inorder(tre t)/* t 表示头结点*/
{ tre p;
p=t->lchild; /* p指向根节点*/
while(p!=t)
{
while(p->rtag==0)
p=p->lchild;
printf("%c",p->data);
while(p->rtag==1&&p->rchild!=t)
{ p=p->rchild;
printf("%c",p->data);
}
p=p->rchild;
}
}
int main()
{
tre t,p;
t=creat();
p=noder(t);
inorder(p);
getch();
}
自己弄明白了，发个代码吧，给需要向我一样要帮助的人吧，
我来回复
您所在位置：