回复 9楼 九转星河
#include<stdio.h>#include<stdlib.h>
#include<string.h>
#define MAXSIZE 1024
#define MAXNODE 1024
typedef struct QueueNode
{
char s[MAXSIZE]; /*队列存放数据*/
int front; /*队列头指针*/
int rear; /*队列尾指针*/
}QueueNode,*Queue;
typedef struct BiTNode
{
char data;
struct BiTNode *lchild,*rchild; /*左右孩子指针*/
}BiTNode,*BiTree;
Queue Init_Queue(); /*队列初始化*/
void In_Queue(Queue q,BiTree bt); /*入队*/
void OutQueue(Queue q,BiTree* x); /*出队并取其数据*/
void Destroy_Queue(Queue* q); /*销毁队列*/
int Empty_Queue(Queue q); /*判断队列是否为空*/
int Full_Queue(Queue q); /*判断队列是否为满*/
int Initiate (BiTree bt); /*初始化二叉树*/
void PreOrder(BiTree bt); /*前序遍历*/
void InOrder(BiTree bt); /*中序遍历*/
void PostOrder(BiTree bt); /*后序遍历*/
void LevelOrder(BiTree bt); /*层次遍历*/
void NRPreOrder(BiTree bt); /*非递归前序遍历*/
void NRInOrder(BiTree bt); /*非递归中序遍历*/
void Destroy (BiTree* bt); /*销毁二叉树*/
void Visite(char c)
{
printf("%c",c);
}
int main() /*主函数*/
{
BiTree bt;
printf("请输入数据\n");
Initiate(bt);
printf("\n前序遍历结果：\n");
PreOrder(bt);
printf("\n前序非递归遍历结果：\n");
NRPreOrder(bt);
printf("\n中序遍历结果：\n");
InOrder(bt);
printf("\n中序非递归遍历结果：\n");
NRInOrder(bt);
printf("\n后序遍历结果：\n");
PostOrder(bt);
}
Queue Init_Queue()
{
Queue p=(Queue)malloc(sizeof (QueueNode));
if (p==NULL)
{
puts("申请空间失败!");
return NULL;
}
memset(p->s,0,sizeof(p->s));
p->front=p->rear=0;
return p;
}
void In_Queue(Queue q,BiTree bt) /*入队*/
{
if (Full_Queue(q))
return ;
++q->rear;
q->rear%=MAXSIZE;
bt->data=q->s[q->rear];
}
void OutQueue(Queue q,BiTree* bt) /*出队*/
{
if (Empty_Queue(q))
return ;
++q->front;
q->front%=MAXSIZE;
(*bt)->data=q->s[q->front];
}
int Empty_Queue(Queue q) /*判断队列是否为空*/
{
return q->front==q->rear;
}
void Destroy_Queue(Queue* q) /*销毁队列*/
{
if (*q)
free(*q);
*q=NULL;
}
int Full_Queue(Queue q)
{
return q->front==q->rear+1; /*判断是否队满*/
}
int index=0;
char node[10];
int Initiate (BiTree bt) /*初始化建立二叉树*bt的头结点*/
{ char ch;
ch = node[index++];
scanf("%d",&bt);
if('#' == ch)
{
bt = NULL;
}
else{
if((bt=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)
return 0;
bt->lchild=NULL;
bt->rchild=NULL;
return 1;
}
}
void PreOrder(BiTree bt) /*先序遍历二叉树bt*/
{
if (bt==NULL)
return; /*递归调用的结束条件*/
Visite(bt->data); /*访问结点的数据域*/
PreOrder(bt->lchild); /*先序递归遍历bt的左子树*/
PreOrder(bt->rchild); /*先序递归遍历bt的右子树*/
}
void InOrder(BiTree bt) /*中序遍历二叉树bt*/
{
if (bt==NULL) /*递归调用的结束条件*/
return;
PreOrder(bt->lchild); /*先序递归遍历bt的左子树*/
Visite(bt->data); /*访问结点的数据域*/
PreOrder(bt->rchild); /*先序递归遍历bt的右子树*/
}
void PostOrder(BiTree bt) /*后序遍历二叉树bt*/
{
if (bt==NULL) /*递归调用的结束条件*/
return;
PostOrder(bt->lchild); /*后序递归遍历bt的左子树*/
PostOrder(bt->rchild); /*后序递归遍历bt的右子树*/
Visite(bt->data); /*访问结点的数据域*/
}
void LevelOrder(BiTree bt) /*层次遍历二叉树bt*/
{
Queue q=Init_Queue(); /*队列初始化*/
BiTree x=0; /*队列暂存数据*/
if (bt==NULL)
return;
In_Queue(q,bt); /*入队*/
while(!Empty_Queue(q)) /*如果队列不为空*/
{
OutQueue(q,&x); /*取出队列数据*/
Visite(x->data); /*访问队首结点的数据域*/
if (x->lchild!=NULL) /*将队首结点的左孩子结点入队列*/
In_Queue(q, x->lchild);
if (x->rchild!=NULL) /*将队首结点的右孩子结点入队列*/
In_Queue(q, x->rchild);
}
Destroy_Queue(&q);
}
void NRPreOrder(BiTree bt) /*非递归先序遍历二叉树*/
{
BiTree stack[MAXSIZE]={0};
BiTree p=NULL;
int top=0;
if(bt==NULL)
return;
p=bt;
while(!(p=NULL&&top==0))
{
while(p!=NULL)
{
/*访问结点的数据域*/
if(top<MAXNODE-1) /*将当前指针p压栈*/
{
stack[top]=p;
top++;
}
else
{
printf("栈溢出");
return;
}
p=p->lchild; /*指针指向p的左孩子*/
}
if(top<=0)
return; /*栈空时结束*/
else
{
top--;
Visite(p->data);
p=stack[top]; /*从栈中弹出栈顶元素*/
p=p->rchild; /*指针指向p的右孩子结点*/
}
}
}
void NRInOrder(BiTree bt) /*非递归中序遍历二叉树*/
{
BiTree stack[MAXSIZE]={0};
BiTree p=NULL;
int top=0;
if(bt==NULL)
return;
p=bt;
while(!(p=NULL&&top==0))
{
while(p!=NULL)
{
/*访问结点的数据域*/
if(top<MAXNODE-1) /*将当前指针p压栈*/
{
stack[top]=p;
top++;
}
else
{
printf("栈溢出");
return;
}
p=p->lchild; /*指针指向p的左孩子*/
}
if(top<=0)
return; /*栈空时结束*/
else
{
top--;
p=stack[top]; /*从栈中弹出栈顶元素*/
Visite(p->data);
p=p->rchild; /*指针指向p的右孩子结点*/
}
}
}
void Destroy (BiTree *bt)
{
if(*bt)
{
Destroy(&(*bt)->lchild);
Destroy(&(*bt)->rchild);
free(*bt);
}
*bt=NULL;
}
这回显示没错误但是不能运行
程序代码：
~~
)非递归中序遍历和非递归后序遍历类似这种写法~修改一下就行了~~~