#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编辑过]
----------------解决方案--------------------------------------------------------
好高深啊！！看都看不懂啊。真想帮你，就是心有余而力不足啊！
----------------解决方案--------------------------------------------------------
你想改成什麽样呢?
----------------解决方案--------------------------------------------------------
这是做什么的程序？
要理解别人的代码可不是一件容易的事！
----------------解决方案--------------------------------------------------------
应该是二叉树的建立，查找，遍历之类的程序吧，关键你是想改成什麽样呢？
----------------解决方案--------------------------------------------------------
我又改了一下
#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 *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'));
do
{
printf("\nenter the data to search:"); 查找值为X的结点
scanf("%d",&w);
t=locate(root,w);
if(t==0)
printf("x is not in the tree");flag=1;
if(t==1)
{
menu();
getchar();
ch=getchar();运行到这里就运行不下去了
pre=NULL;
inorderThreading(root);中序线索化
switch(ch)
{
case'1':flag=1;
p=infront(m);
result=p->data;
if(result==-2)
printf("The $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("The p$ is head");
else
printf("\nThe p$ is %d",result);
break;
case'0':flag=0;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!=NULL)
{
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)
{
inorderThreading(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 *p)
{
head=(struct node *)malloc(sizeof(struct node));
head->data=-2;
p->lchild=head;
p->ltag=1;
inThreading(p);
p->rchild=head;
p->rtag=1;
}
----------------解决方案--------------------------------------------------------
大概写了一个，基本功能跟楼主要求的差不多，大家看看行不行
#include <stdlib.h>
#include <stdio.h>
#define Null 0
struct tree
{
int data;
struct tree *left;
struct tree *right;
};
typedef struct tree tree_node;
typedef tree_node *btree;
btree insert_btree(btree root,int node)
{
btree new,parent,current;
new=(btree)malloc(sizeof(tree_node));
new->data=node;
new->left=Null;
new->right=Null;
if(root==Null)
{
return new;
}
else
{
current=root;
while(current!=Null)
{
parent=current;
if(new->data<current->data)
{
current=current->left;
}
else
{
current=current->right;
}
}
if(new->data<parent->data)
{
parent->left=new;
}
else
{
parent->right=new;
}
return root;
}
}
btree create_btree(int *nodlist,int len)
{
btree root=Null;
int i;
for(i=0;i<len;i++)
{
root=insert_btree(root,nodlist[i]);
}
return root;
}
void prorder(btree root)
{
if(root!=Null)
{
printf("%d\n",root->data);
prorder(root->left);
prorder(root->right);
}
}
void inorder(btree root)
{
if(root!=Null)
{
inorder(root->left);
printf("%d\n",root->data);
inorder(root->right);
}
}
void postorder(btree root)
{
if(root!=Null)
{
postorder(root->left);
postorder(root->right);
printf("%d\n",root->data);
}
}
btree search_btree(btree root,int findnode)
{
btree pointer;
pointer=root;
while(pointer!=Null&&pointer->data!=findnode)
{
if(findnode<pointer->data)
{
pointer=pointer->left;
}
else
{
pointer=pointer->right;
}
}
return pointer;
}
main()
{
int i,index,findnode,data;
int nodlist[16];
unsigned char ch;
btree root,pointer;
index=0;
printf("Please enter tree's node(-1 to end):\n");
scanf("%d",&data);
nodlist[index]=data;
while(data!=-1)
{
index=index+1;
printf("Please enter tree's node(-1 to end):\n");
scanf("%d",&data);
nodlist[index]=data;
}
printf("The linary tree has no any nodes!\n");
root=create_btree(nodlist,index);
do
{
printf("Creating binary tree is:\n");
printf("insert 1 to prcorder:\n");
printf("insert 2 to inorder:\n");
printf("insert 3 to postorder:\n");
scanf("%d",&ch);
switch(ch)
{
case'1':prorder(root);
break;
case'2':inorder(root);
break;
case'3':postorder(root);
break;
}
printf("Do you want to choise another located mathod again?(Y,y(Yes) or N,n(No))\n");
scanf("%d",&ch);
}while(ch==121||ch==89);
printf("enter the data to research:");
scanf("%d",&findnode);
pointer=search_btree(root,findnode);
if(pointer==Null)
{
printf("findnode is not in the tree!\n");
}
else
{
printf("%d\n",pointer->data);
}
getch();
}
----------------解决方案--------------------------------------------------------
楼主看看这个能用吗
----------------解决方案--------------------------------------------------------
迷糊
----------------解决方案--------------------------------------------------------
谢啦，不过我运行了，不成功哦
----------------解决方案--------------------------------------------------------