建立二叉树,并实现先序遍历（用递归）

显示全部楼层 · 2006-12-21 08:38:33

你看这2个哪个符合你的要求我想了半天了,我不太会弄这个#include/*如发现bug请给我留言*/ #include#include#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->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'&&ilchild!=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 #include #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;ikey); 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;ikey[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.f==NULL) i++; p=queue.e; head=queue.f; for(i++;inext=queue.f; p=queue.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;ikey[0]=a/10; q->key[1]=a%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); }

千问 · 2006-12-21 08:38:33

递归非递归都在那里了,自己该一下#include#include#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;}//InitSStatus Gettop(SqS S, BT &e){if(S.top==S.base) return ERROR; e=*(S.top-1); return OK;}//GettopStatus 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;}//PushStatus Pop(SqS &S,BT &e){if(S.top==S.base) return ERROR; e=*--S.top; return OK;}//PopStatus SEmpty(SqS S){if(S.top==S.base) return OK; return ERROR;}//SEmptyStatus 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;}//CreatBTStatus 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;}//InorderStatus 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;}//Traversevoid main(){ BT T;
printf("请出入:"); CreatBT(T); printf("递归输出:");
Traverse(T,Output); printf("\n"); printf("非递归输出:"); Inorder(T,Output); printf("\n");}

千问 · 2006-12-21 08:38:33

我这里有,发给你吧!!

建立二叉树,并实现先序遍历（ 用递归）

建立二叉树,并实现先序遍历（用递归）