编程题-二叉树的遍历要求:二叉树
#include
#include
typedef struct Binnode{//二叉树结点结构体
char data;
struct Binnode *lchild;
struct Binnode *rchild;
};
typedef Binnode *Bintree ;
typedef struct stack{ //二叉树结点栈
Bintree data[100];
int flag[100];
int top;
};
typedef struct queue{ //二叉树结点队列
Bintree data[30];
int front;
int rear;
};
/*****...全部
#include
#include
typedef struct Binnode{//二叉树结点结构体
char data;
struct Binnode *lchild;
struct Binnode *rchild;
};
typedef Binnode *Bintree ;
typedef struct stack{ //二叉树结点栈
Bintree data[100];
int flag[100];
int top;
};
typedef struct queue{ //二叉树结点队列
Bintree data[30];
int front;
int rear;
};
/*******************************************/
/* 按照前序遍历建立二叉树 */
/*******************************************/
void Creat_Bintree(Bintree *root)
{
char ch;
if((ch=getchar())==' ')
{
*root=NULL;
}
else
{
*root=(Binnode*)malloc(sizeof(Binnode));
(*root)->data=ch;
Creat_Bintree(&(*root)->lchild);
Creat_Bintree(&(*root)->rchild);
}
}
/*******************************************/
/* 按照前序递归遍历二叉树 */
/*******************************************/
void Preorder1(Bintree t)
{
if(t!=NULL)
{
printf("%c",t->data);
Preorder1(t->lchild);
Preorder1(t->rchild);
}
}
/*******************************************/
/* 按照中序递归遍历二叉树 */
/*******************************************/
void Inorder1(Bintree t)
{
if(t!=NULL)
{
Inorder1(t->lchild);
printf("%c",t->data);
Inorder1(t->rchild);
}
}
/*******************************************/
/* 按照后序递归遍历二叉树 */
/*******************************************/
void Posorder1(Bintree t)
{
if(t!=NULL)
{
Posorder1(t->lchild);
Posorder1(t->rchild);
printf("%c",t->data);
}
}
/*******************************************/
/* 按照前序非递归遍历二叉树 */
/*******************************************/
void Preorder2(Bintree t)
{
Bintree pre=t;
stack s;
p=0;
printf("输出前序遍历序列:");
while(pre|| p>0)
{
if(pre)
{
printf("%c",pre->data);
s。
data[ p++]=pre;
pre=pre->lchild;
}
else
{
pre=s。
data[-- p]->rchild;
}
}
printf("\n\n");
}
/*******************************************/
/* 按照中序非递归遍历二叉树 */
/*******************************************/
void Inorder2(Bintree t)
{
Bintree pre=t;
stack s;
p=0;
printf("输出中序遍历序列:");
while(pre|| p>0)
{
if(pre)
{
s。
data[ p++]=pre;
pre=pre->lchild;
}
else
{
pre=s。
data[-- p];
printf("%c",pre->data);
pre=pre->rchild;
}
}
printf("\n\n");
}
/*******************************************/
/* 按照后序非递归遍历二叉树 */
/*******************************************/
void Posorder2(Bintree t)
{
stack s;
p=-1;
printf("输出后序遍历序列:");
while(t!=NULL|| p!=-1)
{
while(t)
{
p++;
s。
flag[ p]=0;
s。data[ p]=t;
t=t->lchild;
}
while( p>=0&&s。
flag[ p]==1)
{
t=s。data[ p];
printf("%c",t->data);
p--;
}
if( p>=0)
{
t=s。
data[ p];
s。flag[ p]=1;
t=t->rchild;
}
else
{
t=NULL;
}
}
printf("\n\n");
}
/*******************************************/
/* 按照层次遍历二叉树 */
/*******************************************/
void Levelorder(Bintree t)
{
queue q;
q。
data[0]=t;
ont=0; ar=1;
printf("层次遍历二叉树结果:");
while( ontdata);
q。data[ ar++]=q。
data[ ont]->lchild;
q。data[ ar++]=q。
data[ ont]->rchild;
ont++;
}
else
{
ont++;
}
}
printf("\n\n");
}
。收起