1、实验目的
通过本实验掌握二叉的建立和递归遍历、非递归遍历算法，了解二叉树在实际中的应用并熟练运用二叉树解决实际问题。
2、实验内容
根据前序遍历的顺序建立一棵二叉树，并根据遍历规则遍历二叉树。
打印输出。
3、实验要求
(非递归)
#include<stdio.h>
#include<stdlib.h>
typedef char datatype;
typedef struct node{ /*二叉树结构定义*/
datatype data;
struct node *lchild,*rchild;
}bintnode;
typedef bintnode *bintree;
typedef struct stack{ /*栈结构定义*/
bintree data[100];
int tag[100]; /*为栈中每个元素设置的标记，用于后序遍历*/
int top; /*栈顶指针*/
}seqstack;
void push(seqstack *s,bintree t) /*进栈*/
{
s->data[s->top]=t;
s->top++;
}
bintree pop(seqstack *s) /*出栈*/
{
if(s->top!=0)
{
s->top--;
return (s->data[s->top]);
}
else
return NULL;
}
bintree createbintree() /*根据前序遍历结果创建一棵给定的二叉树*/
{
char ch;
bintree t;
scanf("%c",&ch);
if(ch=='#')
t=NULL;
else
{
t=(bintnode *)malloc(sizeof(bintnode));
t->data=ch;
t->lchild=createbintree();
t->rchild=createbintree();
}
return t;
}
void preorder1(bintree t) /*二叉树前序遍历非递归算法的实现*/
{
seqstack s;
s.top=0;
while( (t) || (s.top!=0)) /*当前处理的子树不为空或栈不为空则循环*/
{
if(t)
{
printf("%c",t->data);
push(&s,t);
t=t->lchild;
}
else
{
t=pop(&s);
t=t->rchild;
}
}
}
void inorder1(bintree t) /*二叉树中序遍历非递归算法的实现*/
{
seqstack s;
s.top=0;
while(t!=NULL || (s.top!=0))
{
if(t)
{
push(&s,t);
t=t->lchild;
}
else
{
t=pop(&s);
printf("%c",t->data);
t=t->rchild;
}
}
}
void postorder1(bintree t) /*二叉树后序遍历非递归算法的实现*/
{
seqstack s;
s.top=0;
while((t) || (s.top!=0))
{
if(t)
{
s.data[s.top]=t;
s.tag[s.top]=0;
s.top++;
t=t->lchild;
}
else
{
if(s.tag[s.top-1]==1)
{
s.top--;
t=s.data[s.top];
printf("%c",t->data);
t=NULL;
}
else
{
t=s.data[s.top-1];
s.tag[s.top-1]=1;
t=t->rchild;
}
}
}
}
int main()
{
bintree t;
printf("请输入一组字符，以‘#’作为结束:（如ABC##DE#G##F###(先序建立)）\n");
t=createbintree();
printf("前序遍历二叉树：\n");
preorder1(t);
printf("\n");
printf("中序遍历二叉树：\n");
inorder1(t);
printf("\n");
printf("后序遍历二叉树：\n");
postorder1(t);
return 0;
}
(递归)
#include<stdio.h>
#include<stdlib.h>
typedef char datatype;
typedef struct node{
datatype data;
struct node *lchild,*rchild;
}bintnode;
typedef bintnode *bintree;
bintree createbintree()
{
char ch;
bintree t;
scanf("%c",&ch);
if(ch=='#')
t=NULL;
else
{
t=(bintnode *)malloc(sizeof(bintnode));
t->data=ch;
t->lchild=createbintree();
t->rchild=createbintree();
}
return t;
}
void preorder(bintree t)
{
if(t)
{
printf("%c",t->data);
preorder(t->lchild);
preorder(t->rchild);
}
}
void inorder(bintree t)
{
if(t)
{
inorder(t->lchild);
printf("%c",t->data);
inorder(t->rchild);
}
}
void postorder(bintree t)
{
if(t)
{
postorder(t->lchild);
postorder(t->rchild);
printf("%c",t->data);
}
}
int main()
{
bintree t;
printf("请输入一组字符，以‘#’作为结束:（如ABC##DE#G##F###(先序建立)）\n");
t=createbintree();
printf("前序遍历二叉树：\n");
preorder(t);
printf("\n");
printf("中序遍历二叉树：\n");
inorder(t);
printf("\n");
printf("后序遍历二叉树：\n");
postorder(t);
return 0;
}
