您所在位置：主题：线索二叉树的父子节点查找失败
Jasperu
[专家分：80] 发布于 2010-05-08 14:03:00
/* Note:Your choice is C IDE */
#include "stdio.h"
#include "string.h"
#include "conio.h"
#include "stdlib.h"
#define A sizeof(struct tre)
typedef char in;
typedef enum{ab,bc} pag;/*ab表示0,bc表示1*/
typedef struct tre
{ in data;
struct tre *lchild,*rchild;
pag ltag,rtag;
}*tree;
tree pre;/*建立一个全局变量*/
tree creat()/*建立二叉树,用前序建立*/
{ tree t;
in c;
scanf("%c",&c);
if(c=='#')
t=NULL;
else
{if((t=(tree)malloc(A))==NULL)
{ printf("分配失败:");
getch();
exit(0);
}
else
{ t->data=c;
t->rtag=ab;
t->ltag=ab;
t->lchild=creat();
t->rchild=creat();
}
}
return t;
}
/* 先进行3中遍历把,用递归实现*/
void inter2(tree t)
{ if(t)
{ printf("%c",t->data);
inter2(t->lchild);
inter2(t->rchild);
}
}
/* 进行中序便利*/
void order(tree t)
{ if(t)
{ order(t->lchild);
printf("%c",t->data);
order(t->rchild);
}
}
void ender(tree t)
{ if(t)
{ printf("%c",t->data);
ender(t->lchild);
ender(t->rchild);
}
}
/*开始进行线索化的建立,是引用了头指针的概念*/
void inter (tree t)
{ tree p;
p=t;
if(p)
{ inter(t->lchild);/*我开始落下了这个,错误*/
if(p->lchild==NULL)/*在此时,这个pre指向这个头结点,在下面一个函数中说明*/
{ p->ltag=bc;
p->lchild=pre;
}/* 建立了这个前序*/
if(pre->rchild==NULL)
{ pre->rtag=bc;
pre->rchild=p;
}/* 因为这个前驱和后记是相互出现的,所以,用成对来进行*/
pre=p;/* 使pre始终指向这个p*/
inter(t->rchild);
}
}
/* 下面是建立一个头节点,形成链表结构*/
tree oper(tree p)/* 这里,定义p为根节点*/
{ tree s;/*另外定义s为头指针,要为s分配空间*/
if((s=(tree)malloc(A))==NULL)
{printf("分配失败:");
getch();
exit(0);
}
s->lchild=p;/* p 作为这个头指针的左子树*/
s->rchild=s;/*头结点的佑子树回指*/
pre=s;/*per指向这个头戒掉*/
inter(p);/*调用线索函数建立线索*/
/*下面是处理这个用头结点建立的尾指针*/
pre->rtag=bc;/* 先处理pre*/
pre->rchild=s;
/*s->rtag=1;
这个一步素要不？*/
s->rchild=pre;
return s;
}
/*下面的是开始进行中序的遍历以及输出,其实这个时候了,这个用线索很容易就可以了实现了*/
void pre2(tree t)/* t 此时为这个头结点*/
{ tree p;
p=t->lchild;/*说明这个p为根节点*/
while( p!=t)
{ while(p->ltag==ab)/* 寻找这个首节点*/
p=p->lchild;
printf("%c",p->data);
while(p->rtag==bc&&p->rchild!=t)
{ p=p->rchild;/*寻找右子书的左边,其实就是在寻找这个的后继*/
printf("%c",p->data);
}
p=p->rchild;/* 沿着这个p的佑子树不断寻找*/
}
}
/* 这个是查找孩子的节点*/
tree found(tree t)
{
in c;
tree p, p2;
printf("\n 请输入要查找的子节点值:\n");
c=getchar();
getchar();
if(t!=NULL)
{ if(t->data==c)
return t;
}
else
{
if(t->ltag!=1)
{p=found(t->lchild);
if(p!=NULL)
return p;
}
if(t->rtag!=1)
{ p2=found(t->rchild);
if(p2!=NULL)
return p2;
}
else
return NULL ;
}
}
/* 这个是查找父节点的函数*/
tree found2(tree t,tree s)
{
tree p,p2;
if(t!=NULL)
{
if((t->ltag!=1&&t->lchild==s)||(t->rtag!=1&&t->rchild==s))
return t;
}
else
{
if(t->ltag!=1)
{p=found2(t->lchild,s);
if(p!=NULL)
return p;
}
if(t->rtag!=1)
{ p2=found2(t->rchild,s);
if(p2!=NULL)
return p2;
}
}
}
/*现在已经建立了这个二叉线索树*/
main()
{ tree t,p,s;
int i;
t=creat();
/*现在开始进行中序建立*/
s=found(t);
t=found2(t,found(t));
while(1)
{
printf(" --------请输入命令:---------\n****1先序输出\n****2中序输出\n****3 后续输出\n****4 线索中序输出\n****5进行孩子节点的查找\n****6进行父亲节点的查找\n**** 7退出系统\n");
E :printf("\n inter:\n");
scanf("%d",&i);
if(i<=0||i>7)
{printf("对不起你输入错了,请重新输入:\n");
goto E;
}
else
{
switch(i)
{ case 1 : inter2(t);break;
case 2 : order(t);break;
case 3 : ender(t);break;
case 4 : printf("你的结果是:\n");p=oper(t); pre2(p);;break;
case 5: printf("开始进行孩子节点的查找:\n");printf("%c",s->data);break;
case 6: printf("开始进行父亲节点的查找:\n");printf("%c",t->data);break;
case 7 : printf("结束了:\n");exit(0);break;
}
}
}
}
就是在输入的时候了，在查找父子节点的程序是老是失败而且还有警告为/* Note:Your choice is C IDE */
#include "stdio.h"
#include "string.h"
#include "conio.h"
#include "stdlib.h"
#define A sizeof(struct tre)
typedef char in;
typedef enum{ab,bc} pag;/*ab表示0,bc表示1*/
typedef struct tre
{ in data;
struct tre *lchild,*rchild;
pag ltag,rtag;
}*tree;
tree pre;/*建立一个全局变量*/
tree creat()/*建立二叉树,用前序建立*/
{ tree t;
in c;
scanf("%c",&c);
if(c=='#')
t=NULL;
else
{if((t=(tree)malloc(A))==NULL)
{ printf("分配失败:");
getch();
exit(0);
}
else
{ t->data=c;
t->rtag=ab;
t->ltag=ab;
t->lchild=creat();
t->rchild=creat();
}
}
return t;
}
/* 先进行3中遍历把,用递归实现*/
void inter2(tree t)
{ if(t)
{ printf("%c",t->data);
inter2(t->lchild);
inter2(t->rchild);
}
}
/* 进行中序便利*/
void order(tree t)
{ if(t)
{ order(t->lchild);
printf("%c",t->data);
order(t->rchild);
}
}
void ender(tree t)
{ if(t)
{ printf("%c",t->data);
ender(t->lchild);
ender(t->rchild);
}
}
/*开始进行线索化的建立,是引用了头指针的概念*/
void inter (tree t)
{ tree p;
p=t;
if(p)
{ inter(t->lchild);/*我开始落下了这个,错误*/
if(p->lchild==NULL)/*在此时,这个pre指向这个头结点,在下面一个函数中说明*/
{ p->ltag=bc;
p->lchild=pre;
}/* 建立了这个前序*/
if(pre->rchild==NULL)
{ pre->rtag=bc;
pre->rchild=p;
}/* 因为这个前驱和后记是相互出现的,所以,用成对来进行*/
pre=p;/* 使pre始终指向这个p*/
inter(t->rchild);
}
}
/* 下面是建立一个头节点,形成链表结构*/
tree oper(tree p)/* 这里,定义p为根节点*/
{ tree s;/*另外定义s为头指针,要为s分配空间*/
if((s=(tree)malloc(A))==NULL)
{printf("分配失败:");
getch();
exit(0);
}
s->lchild=p;/* p 作为这个头指针的左子树*/
s->rchild=s;/*头结点的佑子树回指*/
pre=s;/*per指向这个头戒掉*/
inter(p);/*调用线索函数建立线索*/
/*下面是处理这个用头结点建立的尾指针*/
pre->rtag=bc;/* 先处理pre*/
pre->rchild=s;
/*s->rtag=1;
这个一步素要不？*/
s->rchild=pre;
return s;
}
/*下面的是开始进行中序的遍历以及输出,其实这个时候了,这个用线索很容易就可以了实现了*/
void pre2(tree t)/* t 此时为这个头结点*/
{ tree p;
p=t->lchild;/*说明这个p为根节点*/
while( p!=t)
{ while(p->ltag==ab)/* 寻找这个首节点*/
p=p->lchild;
printf("%c",p->data);
while(p->rtag==bc&&p->rchild!=t)
{ p=p->rchild;/*寻找右子书的左边,其实就是在寻找这个的后继*/
printf("%c",p->data);
}
p=p->rchild;/* 沿着这个p的佑子树不断寻找*/
}
}
/* 这个是查找孩子的节点*/
tree found(tree t)
{
in c;
tree p, p2;
printf("\n 请输入要查找的子节点值:\n");
c=getchar();
getchar();
if(t!=NULL)
{ if(t->data==c)
return t;
}
else
{
if(t->ltag!=1)
{p=found(t->lchild);
if(p!=NULL)
return p;
}
if(t->rtag!=1)
{ p2=found(t->rchild);
if(p2!=NULL)
return p2;
}
else
return NULL ;
}
}
/* 这个是查找父节点的函数*/
tree found2(tree t,tree s)
{
tree p,p2;
if(t!=NULL)
{
if((t->ltag!=1&&t->lchild==s)||(t->rtag!=1&&t->rchild==s))
return t;
}
else
{
if(t->ltag!=1)
{p=found2(t->lchild,s);
if(p!=NULL)
return p;
}
if(t->rtag!=1)
{ p2=found2(t->rchild,s);
if(p2!=NULL)
return p2;
}
}
}
/*现在已经建立了这个二叉线索树*/
main()
{ tree t,p,s;
int i;
t=creat();
/*现在开始进行中序建立*/
s=found(t);
t=found2(t,found(t));
while(1)
{
printf(" --------请输入命令:---------\n****1先序输出\n****2中序输出\n****3 后续输出\n****4 线索中序输出\n****5进行孩子节点的查找\n****6进行父亲节点的查找\n**** 7退出系统\n");
E :printf("\n inter:\n");
scanf("%d",&i);
if(i<=0||i>7)
{printf("对不起你输入错了,请重新输入:\n");
goto E;
}
else
{
switch(i)
{ case 1 : inter2(t);break;
case 2 : order(t);break;
case 3 : ender(t);break;
case 4 : printf("你的结果是:\n");p=oper(t); pre2(p);;break;
case 5: printf("开始进行孩子节点的查找:\n");printf("%c",s->data);break;
case 6: printf("开始进行父亲节点的查找:\n");printf("%c",t->data);break;
case 7 : printf("结束了:\n");exit(0);break;
}
}
}
}
就是在执行第5 6 部是失败，老是返回1，我的这里两部是在查找
父 子节点 ，但是，老是失败，而且有警告为found not all control paths return a vaule
请各位帮忙一下，看看到底是那里错了我
#include "stdio.h"
#include "string.h"
#include "conio.h"
#include "stdlib.h"
#define A sizeof(struct tre)
typedef char in;
typedef enum{ab,bc} pag;/*ab表示0,bc表示1*/
typedef struct tre
{ in data;
struct tre *lchild,*rchild;
pag ltag,rtag;
}*tree;
tree pre;/*建立一个全局变量*/
tree creat()/*建立二叉树,用前序建立*/
{ tree t;
in c;
scanf("%c",&c);
if(c=='#')
t=NULL;
else
{if((t=(tree)malloc(A))==NULL)
{ printf("分配失败:");
getch();
exit(0);
}
else
{ t->data=c;
t->rtag=ab;
t->ltag=ab;
t->lchild=creat();
t->rchild=creat();
}
}
return t;
}
/* 先进行3中遍历把,用递归实现*/
void inter2(tree t)
{ if(t)
{ printf("%c",t->data);
inter2(t->lchild);
inter2(t->rchild);
}
}
/* 进行中序便利*/
void order(tree t)
{ if(t)
{ order(t->lchild);
printf("%c",t->data);
order(t->rchild);
}
}
void ender(tree t)
{ if(t)
{ printf("%c",t->data);
ender(t->lchild);
ender(t->rchild);
}
}
/*开始进行线索化的建立,是引用了头指针的概念*/
void inter (tree t)
{ tree p;
p=t;
if(p)
{ inter(t->lchild);/*我开始落下了这个,错误*/
if(p->lchild==NULL)/*在此时,这个pre指向这个头结点,在下面一个函数中说明*/
{ p->ltag=bc;
p->lchild=pre;
}/* 建立了这个前序*/
if(pre->rchild==NULL)
{ pre->rtag=bc;
pre->rchild=p;
}/* 因为这个前驱和后记是相互出现的,所以,用成对来进行*/
pre=p;/* 使pre始终指向这个p*/
inter(t->rchild);
}
}
/* 下面是建立一个头节点,形成链表结构*/
tree oper(tree p)/* 这里,定义p为根节点*/
{ tree s;/*另外定义s为头指针,要为s分配空间*/
if((s=(tree)malloc(A))==NULL)
{printf("分配失败:");
getch();
exit(0);
}
s->lchild=p;/* p 作为这个头指针的左子树*/
s->rchild=s;/*头结点的佑子树回指*/
pre=s;/*per指向这个头戒掉*/
inter(p);/*调用线索函数建立线索*/
/*下面是处理这个用头结点建立的尾指针*/
pre->rtag=bc;/* 先处理pre*/
pre->rchild=s;
/*s->rtag=1;
这个一步素要不？*/
s->rchild=pre;
return s;
}
/*下面的是开始进行中序的遍历以及输出,其实这个时候了,这个用线索很容易就可以了实现了*/
void pre2(tree t)/* t 此时为这个头结点*/
{ tree p;
p=t->lchild;/*说明这个p为根节点*/
while( p!=t)
{ while(p->ltag==ab)/* 寻找这个首节点*/
p=p->lchild;
printf("%c",p->data);
while(p->rtag==bc&&p->rchild!=t)
{ p=p->rchild;/*寻找右子书的左边,其实就是在寻找这个的后继*/
printf("%c",p->data);
}
p=p->rchild;/* 沿着这个p的佑子树不断寻找*/
}
}
/* 这个是查找孩子的节点*/
tree found(tree t)
{
in c;
tree p, p2;
printf("\n 请输入要查找的子节点值:\n");
c=getchar();
getchar();
if(t!=NULL)
{ if(t->data==c)
return t;
}
else
{
if(t->ltag!=1)
{p=found(t->lchild);
if(p!=NULL)
return p;
}
if(t->rtag!=1)
{ p2=found(t->rchild);
if(p2!=NULL)
return p2;
}
else
return NULL ;
}
}
/* 这个是查找父节点的函数*/
tree found2(tree t,tree s)
{
tree p,p2;
if(t!=NULL)
{
if((t->ltag!=1&&t->lchild==s)||(t->rtag!=1&&t->rchild==s))
return t;
}
else
{
if(t->ltag!=1)
{p=found2(t->lchild,s);
if(p!=NULL)
return p;
}
if(t->rtag!=1)
{ p2=found2(t->rchild,s);
if(p2!=NULL)
return p2;
}
}
}
/*现在已经建立了这个二叉线索树*/
main()
{ tree t,p,s;
int i;
t=creat();
/*现在开始进行中序建立*/
s=found(t);
t=found2(t,found(t));
while(1)
{
printf(" --------请输入命令:---------\n****1先序输出\n****2中序输出\n****3 后续输出\n****4 线索中序输出\n****5进行孩子节点的查找\n****6进行父亲节点的查找\n**** 7退出系统\n");
E :printf("\n inter:\n");
scanf("%d",&i);
if(i<=0||i>7)
{printf("对不起你输入错了,请重新输入:\n");
goto E;
}
else
{
switch(i)
{ case 1 : inter2(t);break;
case 2 : order(t);break;
case 3 : ender(t);break;
case 4 : printf("你的结果是:\n");p=oper(t); pre2(p);;break;
case 5: printf("开始进行孩子节点的查找:\n");printf("%c",s->data);break;
case 6: printf("开始进行父亲节点的查找:\n");printf("%c",t->data);break;
case 7 : printf("结束了:\n");exit(0);break;
}
}
}
}
就是在输入的时候了，在查找父子节点的程序是老是失败而且还有警告为/* Note:Your choice is C IDE */
#include "stdio.h"
#include "string.h"
#include "conio.h"
#include "stdlib.h"
#define A sizeof(struct tre)
typedef char in;
typedef enum{ab,bc} pag;/*ab表示0,bc表示1*/
typedef struct tre
{ in data;
struct tre *lchild,*rchild;
pag ltag,rtag;
}*tree;
tree pre;/*建立一个全局变量*/
tree creat()/*建立二叉树,用前序建立*/
{ tree t;
in c;
scanf("%c",&c);
if(c=='#')
t=NULL;
else
{if((t=(tree)malloc(A))==NULL)
{ printf("分配失败:");
getch();
exit(0);
}
else
{ t->data=c;
t->rtag=ab;
t->ltag=ab;
t->lchild=creat();
t->rchild=creat();
}
}
return t;
}
/* 先进行3中遍历把,用递归实现*/
void inter2(tree t)
{ if(t)
{ printf("%c",t->data);
inter2(t->lchild);
inter2(t->rchild);
}
}
/* 进行中序便利*/
void order(tree t)
{ if(t)
{ order(t->lchild);
printf("%c",t->data);
order(t->rchild);
}
}
void ender(tree t)
{ if(t)
{ printf("%c",t->data);
ender(t->lchild);
ender(t->rchild);
}
}
/*开始进行线索化的建立,是引用了头指针的概念*/
void inter (tree t)
{ tree p;
p=t;
if(p)
{ inter(t->lchild);/*我开始落下了这个,错误*/
if(p->lchild==NULL)/*在此时,这个pre指向这个头结点,在下面一个函数中说明*/
{ p->ltag=bc;
p->lchild=pre;
}/* 建立了这个前序*/
if(pre->rchild==NULL)
{ pre->rtag=bc;
pre->rchild=p;
}/* 因为这个前驱和后记是相互出现的,所以,用成对来进行*/
pre=p;/* 使pre始终指向这个p*/
inter(t->rchild);
}
}
/* 下面是建立一个头节点,形成链表结构*/
tree oper(tree p)/* 这里,定义p为根节点*/
{ tree s;/*另外定义s为头指针,要为s分配空间*/
if((s=(tree)malloc(A))==NULL)
{printf("分配失败:");
getch();
exit(0);
}
s->lchild=p;/* p 作为这个头指针的左子树*/
s->rchild=s;/*头结点的佑子树回指*/
pre=s;/*per指向这个头戒掉*/
inter(p);/*调用线索函数建立线索*/
/*下面是处理这个用头结点建立的尾指针*/
pre->rtag=bc;/* 先处理pre*/
pre->rchild=s;
/*s->rtag=1;
这个一步素要不？*/
s->rchild=pre;
return s;
}
/*下面的是开始进行中序的遍历以及输出,其实这个时候了,这个用线索很容易就可以了实现了*/
void pre2(tree t)/* t 此时为这个头结点*/
{ tree p;
p=t->lchild;/*说明这个p为根节点*/
while( p!=t)
{ while(p->ltag==ab)/* 寻找这个首节点*/
p=p->lchild;
printf("%c",p->data);
while(p->rtag==bc&&p->rchild!=t)
{ p=p->rchild;/*寻找右子书的左边,其实就是在寻找这个的后继*/
printf("%c",p->data);
}
p=p->rchild;/* 沿着这个p的佑子树不断寻找*/
}
}
/* 这个是查找孩子的节点*/
tree found(tree t)
{
in c;
tree p, p2;
printf("\n 请输入要查找的子节点值:\n");
c=getchar();
getchar();
if(t!=NULL)
{ if(t->data==c)
return t;
}
else
{
if(t->ltag!=1)
{p=found(t->lchild);
if(p!=NULL)
return p;
}
if(t->rtag!=1)
{ p2=found(t->rchild);
if(p2!=NULL)
return p2;
}
else
return NULL ;
}
}
/* 这个是查找父节点的函数*/
tree found2(tree t,tree s)
{
tree p,p2;
if(t!=NULL)
{
if((t->ltag!=1&&t->lchild==s)||(t->rtag!=1&&t->rchild==s))
return t;
}
else
{
if(t->ltag!=1)
{p=found2(t->lchild,s);
if(p!=NULL)
return p;
}
if(t->rtag!=1)
{ p2=found2(t->rchild,s);
if(p2!=NULL)
return p2;
}
}
}
/*现在已经建立了这个二叉线索树*/
main()
{ tree t,p,s;
int i;
t=creat();
/*现在开始进行中序建立*/
s=found(t);
t=found2(t,found(t));
while(1)
{
printf(" --------请输入命令:---------\n****1先序输出\n****2中序输出\n****3 后续输出\n****4 线索中序输出\n****5进行孩子节点的查找\n****6进行父亲节点的查找\n**** 7退出系统\n");
E :printf("\n inter:\n");
scanf("%d",&i);
if(i<=0||i>7)
{printf("对不起你输入错了,请重新输入:\n");
goto E;
}
else
{
switch(i)
{ case 1 : inter2(t);break;
case 2 : order(t);break;
case 3 : ender(t);break;
case 4 : printf("你的结果是:\n");p=oper(t); pre2(p);;break;
case 5: printf("开始进行孩子节点的查找:\n");printf("%c",s->data);break;
case 6: printf("开始进行父亲节点的查找:\n");printf("%c",t->data);break;
case 7 : printf("结束了:\n");exit(0);break;
}
}
}
}
就是在执行第5 6 部是失败，老是返回1，我的这里两部是在查找
父 子节点 ，但是，老是失败，而且有警告为found not all control paths return a vaule
请各位帮忙一下，看看到底是那里错了我