建立二叉树,并实现先序遍历（ 用递归）
任务：要求能够输入树的各个结点，并能够输出先序遍历序列；
要求：分别建立二叉树存储结构的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数；
您可以把答案发送到我的邮箱里面把名字打上去``
我到时候再给你加分~
我的邮箱：xiexiufeng0414@yahoo.com.cn
用c语言编，其他不行啊，这是老师要求的。
回复
相关信息
关于vc++链表实现问题 我已经编了部分 就是弄不出来了..
1、 创建线性表类。线性表的存储结构使用链表。 2、 提供操作:自表首插入元素、删除指定元素、搜索表中是否有指定元素、输出链表。 3、 接收键盘录入的一系列整数（例10,25,8,33,60）作为节点的元素值，创建链表。输出链表内容。 4、 输入一个整数（例33），在链表中进行搜索，输出其在链表中的位置。如果不存在输出0。 5、 使用链表遍历器实现链表的反序输出。 6、 创建两...
我这里有,发给你吧!!
你看这2个哪个符合你的要求
我想了半天了,我不太会弄这个
#include <stdio.h> /*如发现bug请给我留言*/
#include <conio.h>
#include <stdlib.h>
#define LEN sizeof(struct node)
struct node
{
char data;
struct node *lchild,*rchild;
};
struct node *build()
{
struct node *stack[20]={NULL},*root,*temp,*p;
char c;
int i=-1;
c=getch();
if(c=='0')
return NULL;
root=p=(struct node *)malloc(LEN);
p->data=c;
c=getch();
while(1)
{
while(c!='0')
{
stack[++i]=p;
p=(struct node *)malloc(LEN);
p->data=c;
stack[i]->lchild=p;
c=getch();
}
p->lchild=NULL;
c=getch();
while(c=='0'&&i>=0)
{
p->rchild=NULL;
p=stack[i--];
c=getch();
}
if(c!='0')
{
temp=(struct node *)malloc(LEN);
p->rchild=temp;
temp->data=c;
p=temp;
c=getch();
}
else if(c=='0'&&i<0)
return root;
}
}
void output(struct node *head) /*中序输入出二叉树*/
{
struct node *stack[20],*p1=head;
int i=-1;
char c;
if(head==NULL)
return;
while(1)
{
while(p1->lchild!=NULL)
{
stack[++i]=p1;
p1=p1->lchild;
}
printf("%c",p1->data);
while(p1->rchild==NULL&&i>=0)
{
p1=stack[i--];
printf("%c",p1->data);
}
if(p1->rchild!=NULL)
{
p1=p1->rchild;
}
else if(p1->rchild==NULL&&i<0)
break;
}
}
int main(int argc, char *argv[])
{
struct node *head;
head=build();
output(head);
printf("\n");
return 0;
}
#include<stdio.h>
#include<stdlib.h>
#define D 2
#define R 10
#define N 11
typedef int KeyType;
typedef int DataType;
struct Node;
typedef struct Node radixNode;
struct Node
{
KeyType key[D];
/* DataType info; */
radixNode *next;
};
typedef radixNode * radixList;
typedef struct QueueNode
{
radixNode *f;
radixNode *e;
} Queue;
Queue queue[R];
void display(radixNode *plist)
{
int i;
radixNode *p;
p=plist->next;
while(p!=NULL)
{
printf("->");
for(i=0;i<D;i++)
printf("%1d",p->key[i]);
p=p->next;
}
printf("\n");
}
void radixSort(radixNode *plist,int d,int r)
{
int i,j,k;
radixNode *p,*head;
head=plist->next;
for(j=d-1;j>=0;j--)
{
p=head;
for(i=0;i<r;i++)
{
queue[i].f=NULL;
queue[i].e=NULL;
}
while(p!=NULL)
{
k=p->key[j];
if(queue[k].f==NULL)
queue[k].f=p;
else
(queue[k].e)->next=p;
queue[k].e=p;
p=p->next;
}
i=0;
while(queue[i].f==NULL)
i++;
p=queue[i].e; head=queue[i].f;
for(i++;i<r; i++)
if(queue[i].f!=NULL)
{
p->next=queue[i].f;
p=queue[i].e;
}
p->next=NULL;
printf("j=%d",j);
}
plist->next=head;
}
void main()
{
radixNode *p,*q,*head;
int a[]={30,12,20,17,40,60,34,42,29,35,47};
int i;
p=(radixNode *) malloc(sizeof(struct Node));
head=p;
p->next=NULL;
printf("test...\n");
for(i=0;i<11;i++)
{
q=(radixNode *) malloc(sizeof(struct Node));
q->key[0]=a[i]/10;
q->key[1]=a[i]%10;
q->next=NULL;
p->next=q;
p=p->next;
}
printf("before:\n");
display(head);
printf("\n");
radixSort(head,D,R);
printf("after:\n");
display(head);
}
递归非递归都在那里了,自己该一下
#include<stdio.h>
#include<stdlib.h>
#define ERROR 0
#define OK 1
#define OVERFLOW -2
#define S_INIT_SIZE 100 //存储空间初时分配量
#define SINCREMENT 10 //存储空间分配增量
typedef int Status;
typedef struct BTNode
{ //二叉树的二叉链表存储表示
char data;
struct BTNode *lchild,*rchild; //左右孩子指针
}BTNode,*BT;
typedef struct
{ BT *base;
BT *top; //栈顶指针
int stacksize; //当前已经分配的存储空间,以元素为单位
}SqS;
Status InitS(SqS &S)
{ //构造一个空栈
S.base=(BT *)malloc(S_INIT_SIZE*sizeof(BT));
if(!S.base) exit(OVERFLOW); //存储分配失败
S.top=S.base;
S.stacksize=S_INIT_SIZE;
return OK;
}//InitS
Status Gettop(SqS S, BT &e)
{ if(S.top==S.base) return ERROR;
e=*(S.top-1);
return OK;
}//Gettop
Status Push(SqS &S,BT e)
{ //插入元素为e的栈顶元素
if(S.top-S.base>=S.stacksize)
{ //栈满,追加存储空间'
S.base=(BT *)realloc(S.base,(S.stacksize+SINCREMENT)*sizeof(BT));
if(!S.base) exit(OVERFLOW); //存储分配失败
S.top=S.base+S.stacksize;
S.stacksize+=SINCREMENT;
}
*S.top++=e;
return OK;
}//Push
Status Pop(SqS &S,BT &e)
{ if(S.top==S.base) return ERROR;
e=*--S.top;
return OK;
}//Pop
Status SEmpty(SqS S)
{ if(S.top==S.base) return OK;
return ERROR;
}//SEmpty
Status CreatBT(BT &T)
{ //构造二叉链表表示的二叉树
char ch;
scanf("%c",&ch);
if(ch==' ') T=NULL;
else
{ if(!(T=(BTNode *)malloc(sizeof(BTNode)))) exit(OVERFLOW);
T->data=ch; //生成跟结点
CreatBT(T->lchild); //构造左子树
CreatBT(T->rchild); //构造右子树
}
return OK;
}//CreatBT
Status Output(char e)
{ printf("%c ",e);
return OK;
}
Status Inorder(BT T,Status(*Output)(char ch))
{ BT p; SqS S;
InitS(S); p=T;
while(p||!SEmpty(S))
{ if(p){Push(S,p); p=p->lchild;}//根指针进栈,遍历左子树
else
{ //根指针退栈,访问根结点,遍历右子树
Pop(S,p); if(!Output(p->data)) return ERROR;
p=p->rchild;
}// else
}//while
return OK;
}//Inorder
Status Traverse(BT T,Status(*Output)(char ch))
{
if(T)
{
if(Traverse(T->lchild,Output))
if(Output(T->data))
if(Traverse(T->rchild,Output)) return OK;
return ERROR;
}
else return OK;
}//Traverse
void main()
{ BT T;
printf("请出入:");
CreatBT(T);
printf("递归输出: ");
Traverse(T,Output);
printf("\n");
printf("非递归输出:");
Inorder(T,Output);
printf("\n");
}