先序线索二叉树和中序线索二叉树有什么区别 最好图解
先序是先根节点在左结点再右结点,中序是先左,再根节点,再右结点
先序线索二叉树和中序线索二叉树有什么区别
先序是先根节点在左结点再右结点，中序是先左，再根节点，再右结点
线索二叉树
//二叉树的二叉线索存储表示
#
#
enum e;//Link==0,指针,Thread==1,线索
char ;
struct
data;
struct _lchild,_rchild; //左右孩子指针
LTag,RTag; //左右标志
},*;
pre; //前驱指针
void ( *T)//建树
char ch;
scanf("%c",&ch);
fflush(stdin);
if(ch==' ')
else
{
if(!(*T=()malloc(sizeof()))) exit();
(*T)->data = ch;
(_T)->lchild = (_T)->rchild = NULL;
(_T)->LTag = (_T)->RTag = Link;
(&(*T)->lchild);
(&(*T)->rchild);
}
void ( T) //建立线索
if(T)
{
(T->lchild); //左子树线索化
if(!T->lchild)//前驱线索
{
T->LTag = Thread; T->lchild = pre;
}
if(!pre->rchild)//后继线索
{
pre->RTag = Thread; pre->rchild = T;
}
pre = T;
(T->rchild);
}
void ( *Thrt, T)//建立线索头结点
//中序遍历二叉树T，并将其中序线索化，Thrt指向头结点。
if(!(*Thrt=()malloc(sizeof()))) exit(1);
(*Thrt)->LTag = Link; //建立头结点
(*Thrt)->RTag = Thread;
(Thrt)->rchild = Thrt; //右指针回指
if(!T) (Thrt)->lchild = Thrt; //若二叉树空,左指针也回指
else
{
(Thrt)->lchild = T; pre = Thrt;
(T); //进行中序线索化
pre->rchild = *Thrt; pre->RTag = Thread; //最后一个结点线索化
(*Thrt)->rchild = pre;
}
void ( T)//线索化中序遍历
//T指向头结点，头结点左链lchild指向根结点。
p;
p = T->lchild;//p指向根结点
while(p!=T)//空树或遍历结束时，p==t
{
while(p->LTag==Link) p = p->lchild;
//左子树为空时访问
printf(https://xuan.ddwoo.top%c/);
while(p->RTag==Thread && p->rchild!=T)
{
p = p->rchild;
printf("%c ",p->data); //访问后继结点
}
p = p->rchild;
}
int main(void)
tree,;
(&tree);
(&,tree);
printf(":n");
();
return 0;
this is blank
this is blank
this is blank
this is blank
< ----这代表打空格
this is blank
this is blank
this is blank
this is blank
this is blank
this is blank
this is blank
this is blank
a b * c - d - e / f
线索二叉树的遍历比较麻烦，没有把他都搞出来。上面是参考老严的代码。根结点也需要处理，根结点的前驱为空，后继为队里中的下一个元素。#"stdio.h"
#"stdlib.h"
#"string.h"
struct {
int ltag,rtag;
char date20;
struct lchild, rchild;
} , *;
pre=null;
void visite(char * ch)
printf("n输出节点信息:");
printf("%s",ch);
//初始化二叉树
(char ch[])
t;
char ch120,ch220;
t=( )malloc(sizeof());
strcpy(t->date,ch);
printf("n请输入左子树的数值，结束输入0:n");
scanf("%s",ch1);
if(strcmp(ch1,"0")==0)
t->ltag=1;
t->lchild=null;
else
{ t->ltag=0;
t->lchild=(ch1);
printf("n请输入右子树的数值，结束输入0:n");
scanf("%s",ch2);
if(strcmp(ch2,"0")==0)
t->rtag=1;
t->rchild=null;
else
{t->rtag=0;
t->rchild=(ch2);
return t;
//建立中序线索二叉树算法实现
void ( t)
{ if (t)
{ (t->lchild);
if (t->lchild==null)
{ t->ltag=1; t->lchild=pre; }
if (t->rchild==null)
t->rtag=1;
if ((pre)&&(pre->rtag==1))
pre->rchild=t;
pre=t;
(t->rchild); }
//在中序线索二叉树上寻找结点p的中序后继结点的算法:
( p)
{ post;
post=p->rchild;
if (p->rtag==0)
while (post->ltag==0) post=post->lchild;
return (post);
// 在中序线索二叉树上查找值为x的结点
search ( t,char x[] )
{ p;
p=t;
if (p)
{ while (p->ltag==0) p=p->lchild;
while (p&&strcmp(p->date,x)!=0)
p= (p);
return p;
//在中序线索二叉树上寻找结点p的中序前驱结点的算法：
( p)
{ prel;
prel=p->lchild;
if (p->ltag==0)
while (prel->rtag==0) prel= prel->rchild;
printf("n结点p的中序前驱结点信息！n");
visite(prel->date);
return(prel);
// 中序线索二叉树的遍历算法
void ( t)
{ p;
if (t)
{ p=t;
while (p->ltag==0) p=p->lchild;
while (p)
{ visite(p->date);
p= (p);
void main()
t,p;
char ch20,x20;
int flag=1;
while(flag){
printf("n请选择需要进行的操作:n");
printf("n1：创建二叉树n");
printf("n2：线索二叉树n");
printf("n3：中序线索二叉树n");
printf("n4：寻找结点p的中序前驱结点n");
printf("n5：寻找结点p的中序后继结点n");
printf("n6：查找值为x的结点n");
printf("n0：退出！nn");
scanf("%d",&flag);
switch(flag){
case 1 :
printf("n开始创建二叉树n");
printf("n请输入一个数值:");
scanf("%s",ch);
t=(ch);
printf("nnnnn");break;
case 2:
printf("n开始线索二叉树！n");
(t) ;break;
case 3:
printf("n中序线索二叉树！n");
( t) ;break;
case 4://在中序线索二叉树上寻找结点p的中序前驱结点的算法：
printf("n输入p节点信息，以方便查找n");
scanf("%s",x);
printf("n寻找结点p的中序前驱结点!n");
p=search (t,x) ;
( p);
break;
case 5://在中序线索二叉树上寻找结点p的中序后继结点的算法:
printf("n输入p节点信息，以方便查找!n");
scanf("%s",x);
printf("n结点p的中序后继结点信息！n");
printf("n寻找结点p的中序后继结点!n");
p=search (t,x) ;
p=( p);
visite(p->date);
break;
case 6:// 在中序线索二叉树上查找值为x的结点
printf("n请输入查找的数值！n");
scanf("%s",x);
p=search(t,x);
if(p) printf("n查找成功！nn"); else printf("n查找失败！nn");
break;
:break;
if(flag!=0)
printf("n请选择操作*n");
}二叉树的二叉线索存储表示
#.h
中序线索化二叉树程序
#
char ;
enum{ Link , Thread } ;
struct node{
data;
,;
struct node , ;
},*;
//先序创建线索二叉树
void reate( &T)
char ch;
cin>>ch;
if(ch!='*')
T=new ;
T->data=ch;
T->=T->=Link;
T->=NULL;
T->=NULL;
reate(T->);
reate(T->);
else T=NULL;
//中序线索化二叉树
void ( p, &pre)
if(p)
(p->,pre);
if(p->==NULL)
p->=pre;
p->=Thread;
if(pre->==NULL)
pre->=p;
pre->=Thread;
pre=p;
(p->,pre);
void ( &T, &head)
head=new ;
head->=Link;
head->=Thread;
head->=head;
if(T==NULL)head->=head;
else
head->=T;
pre;
pre=head;
(T,pre);
pre->=head;
pre->=Thread;
head->=pre;
}(curr->left(),pre); //这句 ，结点往左走，pre还不变吗？还能这样写吗？
这个是递归调用本函数，如果不为空，有节点，就顺左子树的线路往下找线索二叉树怎么画，pre指向该节点本身的前驱节点(也就是左孩子)
if(pre==null) curr->lth()=1; //置线索 是curr->left()为空才置1吧？跟pre==null有什么关系？
这个pre==null是看该节点是不是叶子节点，要是按你说的curr->left()为空才置1，那curr->right呢？不就错了
我也是刚学的数据结构，不过我看的书的线索二叉树是 如果该节点没有左孩子，则空出来的指针域指向其前驱(都是中序遍历)线索二叉树怎么画，没有又孩子，则指向其后继，你这个看起来有点怪， 我也正在学，说的也不一定对
本文共 940 个字数,平均阅读时长 ≈ 3分钟
