#include "stdio.h"
#include "conio.h"
#define NULL 0
struct node
{
int data;
int ltag;
int rtag;
struct node *lchild;
struct node *rchild;
struct node *parent;
}*root,*tree,*p,*pre,*head,*m;
main()
{
void search(struct node *root,struct node *tree);
void precorder(struct node *root);
void inorder(struct node *root);
void postorder(struct node *root);
void inorderThreading(struct node *head,struct node *t);
void inThreading(struct node *p);
void menu();
struct node *infront(struct node *p);
int locate(struct node *p,int x);
struct node *innext(struct node *p);
int a,w,t,flag,result;
char c,ch;
head=NULL;
do
{
root=(struct node *)malloc(sizeof(struct node));
printf("\n\nplease enter root's node(-1 to end)");
if(scanf("%d",&root->data)&&root->data==-1)
printf("\n\nThe linary tree has no any nodes");
else
{
root->parent=NULL;
root->lchild=NULL;
root->rchild=NULL;
printf("\n\nPlease enter tree's node(-1 to end)\n");
do
{
tree=(struct node *)malloc(sizeof(struct node));
scanf("%d",&tree->data);
if(tree->data!=-1)
{
tree->parent=NULL;
tree->lchild=NULL;
tree->rchild=NULL;
search(root,tree);
if(p->data<tree->data)
p->rchild=tree;
else if(p->data>tree->data)
p->lchild=tree;
else
free(tree);
tree->parent=p;
}
}while(tree->data!=-1);建立排序二叉树
do
{
printf("\n\nCreating binary tree is:\n");
printf("insert 1 to precorder:\n");
printf("insert 2 to inorder:\n");
printf("insert 3 to postorder:\n");
getchar();
ch=getchar();
switch(ch)
{
case'1':precorder(root); 前序输出
break;
case'2':inorder(root); 中序输出
break;
case'3':postorder(root); 后序输出
break;
}
printf("\n\nDo you want to choise another located mathod again?(Y,y(Yes) or N,n(No))");
}while((scanf("%c",&c)&&c=='Y')||(scanf("%c",&c)&&c=='y'));
}
printf("\n\nDo you want to create a new tree again? (Y,y(Yes) or N,n(No))");
}while((scanf("%c",&c)&&c=='Y')||(scanf("%c",&c)&&c=='y'));
inorderThreading(head,root);
do
{
printf("\nenter the data to search:"); 查找值为X的结点
scanf("%d",&w);
t=locate(root,w);
printf("%d",t);
if(t==0)
c='a';
else
c='b';
switch(c)
{
case'a': printf("\nx is not in the tree"); 这里运行不了，大家帮我看看 ^_^
flag=1;
break;
case'b':
{
menu();
getchar();
ch=getchar();
switch(ch)
{
case'1':flag=1;
p=infront(m);
result=p->data;
if(result==-2)
printf("\nThe $p is head"); 找前导
else
printf("\nThe $p is %d",result);
break;
case'2':flag=1;
p=innext(m);
result=p->data;
if(result==-2) 找后序
printf("\nThe $p is head");
else
printf("\nThe p$ is %d",result);
break;
case'0':flag=0;break;
default:flag=0;break;
}
}break;
}
}while(flag==1);
}
void search(struct node *root,struct node *tree)
{
if((root->data<tree->data)&&(root->rchild!=NULL))
search(root->rchild,tree);
else if((root->data>tree->data)&&(root->lchild!=NULL))
search(root->lchild,tree);
else
p=root;
}
void precorder(struct node *root)
{
if(root!=NULL)
{
printf("%d\t",root->data);
precorder(root->lchild);
precorder(root->rchild);
}
}
void inorder(struct node *root)
{
if(root!=NULL)
{
inorder(root->lchild);
printf("%d\t",root->data);
inorder(root->rchild);
}
}
void postorder(struct node *root)
{
if(root!=NULL)
{
postorder(root->lchild);
postorder(root->rchild);
printf("%d\t",root->data);
}
}
struct node *infront(struct node *p)
{
struct node *q;
q=p->lchild;
if(p->ltag==0)
while(q->rtag==0)
q=q->rchild;
return(q);
}
struct node *innext(struct node *p)
{
struct node *q;
q=p->rchild;
if(p->rtag==0)
while(q->ltag==0)
q=q->lchild;
return(q);
}
int locate(struct node *p,int x)
{
m=p;
while(m->data!=-2)
{
if(m->data==x)
return(1);
else if(m->data>x)
m=m->lchild;
else
m=m->rchild;
}
return(0);
}
void menu()
{
printf("\nEnter 1 to find $p");
printf("\nEnter 2 to find p$");
printf("\nEner 0 to exist");
}
void inThreading(struct node *p)
{
if(p!=NULL)
{
inThreading(p->lchild);
if(p->lchild!=NULL)
{
p->ltag=0;
}
else
{
p->ltag=1;
}
if(p->rchild!=NULL)
{
p->rtag=0;
}
else
{
p->rtag=1;
}
if(pre!=NULL)
{
if(pre->rtag==1)
pre->rchild=p;
if(p->ltag==1)
p->lchild=pre;
}
pre=p;
inThreading(p->rchild);
}
}
void inorderThreading(struct node *head,struct node *t)
{
head=(struct node*)malloc(sizeof(struct node));
head->ltag=0;
head->rtag=1;
head->rchild=head;
head->lchild=t;
head->data=-2;
pre=head;
inThreading(t);
pre->rchild=head;
pre->rtag=1;
head->rchild=pre;
}
[此贴子已经被作者于2005-12-15 0:00:28编辑过]
