|
|
#2
xichong2010-06-29 21:25
楼主主要问题是不知道怎样使用指针和一些小问题,我给你改了前序递归遍历以前的部分,后面的你自己照着改。。。
程序代码:#include<stdio.h> #include<stdlib.h> #include<string.h> #include<malloc.h> #include<math.h> //#define NULL 0==================重复了,NULL的值在系统中本来就是0 #define MAXsize 100 typedef struct Xnode { char data; struct Xnode *lchild,*rchild; }BTNode,*BTree;//===============================BTree,指向结点的指针!!!!!!!! typedef struct stack { BTree data[MAXsize]; int tag[MAXsize]; int top; }seqstack; void push(seqstack* s,BTree bt) //进栈 { s->data[++s->top]=bt; } BTree pop(seqstack* s) //出栈 { if(s->top!=-1) { s->top--; return(s->data[s->top+1]); } } BTree CreateBTree() { BTree bt; char ch; if((ch=getchar())==' ')//======================空字符是' ',不是'' bt=NULL; else { bt=(BTree)malloc(sizeof(BTNode));//========================= bt->data =ch; bt->lchild=CreateBTree(); bt->rchild=CreateBTree(); } return bt; } void Preorder(BTree bt)//======================= { if(bt!=NULL) { printf("%c",bt->data); Preorder(bt->lchild); Preorder(bt->rchild); } } /*void Preorder1(BTree *bt) { BTree *St[MAXsize],*p; int top=1; if(bt!=NULL) { top++; St[top]=bt; while(top>-1) { p=St[top]; top--; printf("%c",p->data ); if(p->rchild !=NULL) { top++; St[top]=p->data ; } if(p->lchild !=NULL) { top++; St[top]=p->data ; } } } } void inorder(BTree *bt) { if(bt!=NULL) { inorder(bt->lchild ); printf("%c",bt->data ); inorder(bt->rchild ); } } void inorder1(BTree bt) { BTree St[MAXsize],p; int top=1; if(bt!=NULL) { top++; St[top]=bt; while(top>-1) { if(p->rchild !=NULL) { top++; St[top]=p->data ; } p=St[top]; top--; printf("%c",p->data ); if(p->lchild !=NULL) { top++; St[top]=p->data ; } } } } void postorder(BTree *bt) { if(bt!=NULL) { postorder(bt->lchild ); postorder(bt->rchild ); printf("%c",bt->data ); } } void postorder1(BTree bt) { BTree St[MAXsize]; BTree p; p=bt; int flag,top=-1; do { while(bt) { top++; St[top]=bt; bt=bt->lchild ; } p=NULL; flag=1; while(top!=-1&&flag) { bt=St[top]; if(bt->rchild ==p) { printf("%c",bt->data ); top--; p=bt; } else { bt=bt->rchild ; flag=0; } } }while(top!=-1); } void translevel(BTree *bt) { struct node { BTree *vec[MAXsize]; int f,r; }Qu; Qu.f=0; Qu.r=0; if(bt!=NULL) printf("%c",bt->data ); Qu.vec[Qu.r]=bt; Qu.r=Qu.r=1; while(Qu.f<Qu.r) { bt=Qu.vec[Qu.f]; Qu.f=Qu.f=1; if(bt->lchild!=NULL) { printf("%c",bt->lchild->data); Qu.vec[Qu.r]=bt->lchild; Qu.r=Qu.r+1; } if(bt->rchild!=NULL) { printf("%c",bt->rchild->data); Qu.vec[Qu.r]=bt->rchild; Qu.r=Qu.r+1; } } printf("\n"); }*/ void main() { BTree bt; printf("请输入一棵二叉树:\n"); bt=CreateBTree(); printf("递归的先序遍历为:"); Preorder(bt); printf("\n"); /* printf("非递归的先序遍历为:"); Preorder1(bt); printf("\n"); printf("递归的中序遍历为:"); inorder(bt); printf("\n"); printf("非递归的中序遍历为:"); inorder1(bt); printf("\n"); printf("递归的后续遍历为:"); postorder(bt); printf("\n"); printf("递归的后续遍历为:"); postorder1(bt); printf("\n"); printf("层次序的非递归遍历为:"); translevel(bt); printf("\n");*/ } 画了======================的地方都是我改过的! |
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<malloc.h>
#include<math.h>
#define NULL 0
#define MAXsize 100
typedef struct Xnode
{
char data;
struct Xnode *lchild,*rchild;
}BTree;
typedef struct stack
{
BTree data[MAXsize];
int tag[MAXsize];
int top;
}seqstack;
void push(seqstack* s,BTree bt) //进栈
{
s->data[++s->top]=bt;
}
BTree pop(seqstack* s) //出栈
{
if(s->top!=-1)
{
s->top--;
return(s->data[s->top+1]);
}
}
BTree CreateBTree()
{
BTree bt;
char ch;
if((ch=getchar())=='')
bt=NULL;
else
{
bt=(BTree*)malloc(sizeof(BTree));
bt->data =ch;
bt->lchild=CreateBTree();
bt->rchild=CreateBTree();
}
return bt;
}
void Preorder(BTree *bt)
{
if(bt!=NULL)
{
printf("%c",bt->data);
Preorder(bt->lchild);
Preorder(bt->rchild);
}
}
void Preorder1(BTree *bt)
{
BTree *St[MAXsize],*p;
int top=1;
if(bt!=NULL)
{
top++;
St[top]=bt;
while(top>-1)
{
p=St[top];
top--;
printf("%c",p->data );
if(p->rchild !=NULL)
{
top++;
St[top]=p->data ;
}
if(p->lchild !=NULL)
{
top++;
St[top]=p->data ;
}
}
}
}
void inorder(BTree *bt)
{
if(bt!=NULL)
{
inorder(bt->lchild );
printf("%c",bt->data );
inorder(bt->rchild );
}
}
void inorder1(BTree bt)
{
BTree St[MAXsize],p;
int top=1;
if(bt!=NULL)
{
top++;
St[top]=bt;
while(top>-1)
{
if(p->rchild !=NULL)
{
top++;
St[top]=p->data ;
}
p=St[top];
top--;
printf("%c",p->data );
if(p->lchild !=NULL)
{
top++;
St[top]=p->data ;
}
}
}
}
void postorder(BTree *bt)
{
if(bt!=NULL)
{
postorder(bt->lchild );
postorder(bt->rchild );
printf("%c",bt->data );
}
}
void postorder1(BTree bt)
{
BTree St[MAXsize];
BTree p;
p=bt;
int flag,top=-1;
do
{
while(bt)
{
top++;
St[top]=bt;
bt=bt->lchild ;
}
p=NULL;
flag=1;
while(top!=-1&&flag)
{
bt=St[top];
if(bt->rchild ==p)
{
printf("%c",bt->data );
top--;
p=bt;
}
else
{
bt=bt->rchild ;
flag=0;
}
}
}while(top!=-1);
}
void translevel(BTree *bt)
{
struct node
{
BTree *vec[MAXsize];
int f,r;
}Qu;
Qu.f=0;
Qu.r=0;
if(bt!=NULL)
printf("%c",bt->data );
Qu.vec[Qu.r]=bt;
Qu.r=Qu.r=1;
while(Qu.f<Qu.r)
{
bt=Qu.vec[Qu.f];
Qu.f=Qu.f=1;
if(bt->lchild!=NULL)
{
printf("%c",bt->lchild->data);
Qu.vec[Qu.r]=bt->lchild;
Qu.r=Qu.r+1;
}
if(bt->rchild!=NULL)
{
printf("%c",bt->rchild->data);
Qu.vec[Qu.r]=bt->rchild;
Qu.r=Qu.r+1;
}
}
printf("\n");
}
void main()
{ BTree bt;
printf("请输入一棵二叉树:\n");
bt=CreateBTree();
printf("递归的先序遍历为:");
Preorder(bt);
printf("\n");
printf("非递归的先序遍历为:");
Preorder1(bt);
printf("\n");
printf("递归的中序遍历为:");
inorder(bt);
printf("\n");
printf("非递归的中序遍历为:");
inorder1(bt);
printf("\n");
printf("递归的后续遍历为:");
postorder(bt);
printf("\n");
printf("递归的后续遍历为:");
postorder1(bt);
printf("\n");
printf("层次序的非递归遍历为:");
translevel(bt);
printf("\n");
}
程序代码: