#include "stdafx.h"
#include "stdlib.h"
#include "stdio.h"
typedef char DataType;
#define max 50
static a,b,c,d,e,f,g;
typedef struct DTnode
{
DataType data;
struct DTnode * lchild,* rchild;
}DTtree;
DTtree * Creat_DTtree()
{
int o=1;
DTtree *Q[max];
DataType ch;
int front,rear;
DTtree *s,*root;
root=NULL;
front=1;
rear=0;
printf("*****************请按照完全二叉树的编号顺序依次输入结点序列*********************");
printf("\t\t<；注：空结点用'@'表示，输入序列以'#'结束>\n");
ch=getchar();
while (ch!='#')
{
s=NULL;
if (ch!='#')
{
s=(DTtree*)malloc(sizeof(DTtree));                  /*建立二叉树的第一个根节点，根节点为输入的第一个ch的直，左右孩子为空*/
s->data=ch;
s->lchild=NULL;
s->rchild=NULL;
}
rear++;                                              /*队列第一个从数组下表为1的存储单元开始存储*/                           
if (o==1)                                            /*层次遍历的顺序即为存入二叉树的顺序*/
{printf ("\t\t层次遍历结果为：");}         
Q[rear]=s;                                            /*数组指针指向s的根节点*/
printf ("%c",Q[rear]->data);
if (rear==1)                                          /*确定返回值：root*/
root=s;
else
{
if(s&&Q[front])                                  /*满足指针s和当前的数组指针都不为空*/
{if(rear%2==0)                                    /*当为第偶数个结点时，将s给指针的左孩子，奇数为右孩子*/
Q[front]->lchild =s;
else
Q[front]->rchild =s;                         
if(rear%2==1)
front++;}                                  /*完成一个树的建立*/
}
ch=getchar();
o--;
if (ch!='#')
{printf("->");}
}
a=rear,b=rear,c=rear,d=rear,e=rear,f=rear,g=rear;
return root;
}
/*先序的非递归算法*/
void preorder_1(DTtree *t)         
{
DTtree *p,*s[max];
int top=0;
p=t;
int o=1;
do{
while (p!=NULL)
{
printf("%c",p->data);
if (e>1)
printf ("->");
if(p->rchild!=NULL)
s[top++]=p->rchild;
p=p->lchild;
e--;
}
if(top>=0)
p=s[--top];         
}while(top>=0);
}
/*先序的递归算法*/
void preorder(DTtree *t)
{
DTtree *p;
p=t;
if(t!=NULL)
{
printf("%c",p->data);
if(g>1)
{printf("->");g--;}
preorder(p->lchild);
preorder(p->rchild);
}
}
/*中序的非递归算法*/           
void midorder_1(DTtree*t)
{
DTtree *p,*s[max];
int top=0;
p=t;
do{
while (p!=NULL)
{
s[top++]=p;
p=p->lchild;
}
if(top>0){
p=s[--top];
printf ("%c",p->data);
安卓课程设计源代码
if(d>1)
{printf("->");d--;}
p=p->rchild;
}
else
break;
}while (top>=0);
}
/*中序的递归算法*/
void midorder(DTtree*t)
{
DTtree *p;
p=t;
if(t)
{
midorder(p->lch
ild);
printf("%c",p->data);
if(b>1)
{printf("->");b--;}
midorder(p->rchild);
}
}
/*后序非递归算法*/
void aftdorder_1(DTtree *t)
{
int top=0,flag=0;
int s2[max];
DTtree *p,*s[max];
p=t;
do{
while (p!=NULL)
{
s[top]=p;
s2[top++]=0;
p=p->lchild;
}int v=top;
if (top>0)
{
flag=s2[--top];
p=s[top];
if(flag==0)
{
s[top]=p;
s2[top++]=1;
p=p->rchild;
}
else
{
if (v>1)
{
printf ("%c->",p->data);
}
else
{ printf ("%c",p->data);}
v--;
p=NULL;
}
}
}while(top>0);
}
/*后序的递归算法*/
void aftdorder(DTtree*t)
{
if (t)
{
aftdorder(t->lchild);
aftdorder(t->rchild);
printf ("%c",t->data);
if(c>1){printf("->");
c--;}
}
}
void main(int argc, char* argv[])
{
DTtree*tree;
int m;
tree=Creat_DTtree();
printf ("\n\n");
do
{  printf ("\t请选择要遍历的方式1、先序  2、中序  3、后序  9、退出\n");
printf ("\t====================================================\n");
scanf ("%d",&m);
if(m==1)
{
printf("\n\t\t先序序列为(递归算法):");
preorder(tree);
printf("\n");
printf("\n\t\t先序序列为(非递归算法):");
preorder_1(tree);
printf("\n\n\n");
}
else if (m==2)
{
printf("\n\t\t中序序列为(递归算法):");
midorder(tree);
printf("\n");
printf("\n\t\t中序序列为(非递归算法):");
midorder_1(tree);
printf("\n\n");
}
else if (m==3)
{
printf("\n\t\t后序序列为(递归算法):");
aftdorder(tree);
printf("\n");
printf("\n\t\t后序序列为(非递归算法):");
aftdorder_1(tree);
printf("\n\n\n");
}
else printf ("\t\t您的输入有误，请重新输入！\n\n\n");
}while (m!=9);
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。