第1页 / 共6页
第2页 / 共6页
第3页 / 共6页
第4页 / 共6页
第5页 / 共6页
第6页 / 共6页
数据结构综合课设二叉树的建立与遍历.docx
二叉树的建立与遍历
1. 问题描述：
建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结
果。
2. 基本要求：
从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序
来建立），并采用递归算法对其进行遍历（先序、中序、后序），将遍历结果打印
输出。
3.测试要求：
ABCффDEфGффFффф（其中ф表示空格字符）
则输出结果为：
先序：ABCDEGF
中序：CBEGDFA
后序：CGEFDBA
[选作内容]
采用非递归算法实现二叉树遍历。
4.算法思想：
以广义表格式输入一个二叉树，将其接收至一维数组中，利用栈结构建立二叉链
表树；通过先、中、后访问根结点递归算法遍历二叉树；利用栈结构依次将结点
入栈、出栈实现二叉树的非递归遍历算法；利用队列的入队、出队操作实现二叉
树的层次遍历。
5.数据结构：
typedef struct node
二叉树结点定义
typedef struct stack
栈结构定义
bintree creatbytree()
按照前序遍历的顺序建立一棵给定的二叉树
void inorder(bintree t)
递归实现二叉树中序遍历
void postorder(bintree t)
递归实现二叉树后序遍历
void push(seqstack *s,bintree t)
进栈
bintree pop(seqstack *s)
出栈
void preorder1(bintree t)
非递归实现二叉树前序遍历
void inorder1(bintree t)
非递归实现二叉树中序遍历
void postorder1(bintree t)
非递归实现二叉树后序遍历
6.源程序：
#include
#include
typedef char datatype;
typedef struct node
{
/*二叉树结点定义*/
datatype data;
struct node *lchild,*rchild;
}binnode;
typedef binnode *bintree;
typedef struct stack
{
bintree data[100];
int tag[100];
int top;
/*栈结构定义*/
/*为栈中每个元素设置的标记，用于后序遍历*/
/*栈顶指针*/
}seqstack;
/****************************************/
bintree creatbytree()
{
/*按照前序遍历的顺序建立一棵给定的二叉树*/
datatype ch;
bintree t;
if((ch=getchar())=='#')
return NULL;
else
{
t=(bintree)malloc(sizeof(binnode));
t->data=ch;
t->lchild=creatbytree();
t->rchild=creatbytree();
}
return t;
}
/****************************************/
void preorder(bintree t)
{
/*递归实现二叉树前序遍历*/
if(t!=NULL)
{
printf("%c\t",t->data);
preorder(t->lchild);
preorder(t->rchild);
}
}
/****************************************/
void inorder(bintree t)
{
/*递归实现二叉树中序遍历*/
if(t!=NULL)
{
inorder(t->lchild);
printf("%c\t",t->data);
inorder(t->rchild);
}
}
/****************************************/
void postorder(bintree t)
{
/*递归实现二叉树后序遍历*/
if(t!=NULL)
{
postorder(t->lchild);
postorder(t->rchild);
printf("%c\t",t->data);
}
}
/****************************************/
void push(seqstack *s,bintree t)
/*进栈*/
{
s->data[s->top++]=t;
}
/****************************************/
bintree pop(seqstack *s)
/*出栈*/
{
if(s->top==0)
return NULL;
/*栈空返回 NULL*/
else
{
}
s->top--;
return s->data[s->top];
/*返回栈顶的数据*/
}
/****************************************/
/*非递归实现二叉树前序遍历*/
/*输出第一个数据*/
/*二叉树右子树进栈*/
void preorder1(bintree t)
{
seqstack s;
s.top=0;
while(t!=NULL || s.top!=0)
{
if(t)
{
printf("%c\t",t->data);
if(t->rchild!=NULL)
push(&s,t->rchild);
t=t->lchild;
}
else
{
t=pop(&s);
/*左子树遍历完毕出栈继续遍历*/
}
}
}
/****************************************/
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",t->data);
t=t->rchild;
/*出栈*/
/*输出栈顶数据*/
}
}
}
/****************************************/
void postorder1(bintree t)
{
/*非递归实现二叉树后序遍历*/
seqstack s;
s.top=0;
while(t!=NULL || s.top!=0)
{
if(t)
{
s.data[s.top++]=t;
s.tag[s.top-1]=0;
t=t->lchild;
}
else
/*t 进栈保存*/
/*标志还未进入该结点的右子树*/
/*指向下一个左子树*/
if(s.tag[s.top-1]==1)
/*判断栈顶结点右子树是否进入过*/
{
}
else
{
}
}
t=pop(&s);
printf("%c\t",t->data);
t=NULL;
/*输出元素*/
/*置空后进入循环*/
t=s.data[s.top-1];
s.tag[s.top-1]=1;
t=t->rchild;
/*出栈但是不改栈顶指针*/
/*标志已经进入过该结点的右子树*/
/*进入该节点的右子树*/
}
/****************************************/
int main()
{
/*主程序*/
bintree head;
printf("请按前序遍历输入创建一棵二叉树：\n");
head=creatbytree();
printf("二叉树递归前序遍历结果：\n");
preorder(head);
printf("\n");
printf("二叉树递归中序遍历结果：\n");
inorder(head);
printf("\n");
printf("二叉树递归后序遍历结果：\n");
postorder(head);
printf("\n");
printf("二叉树非递归前序遍历结果：\n");
preorder1(head);
printf("\n");
printf("二叉树非递归中序遍历结果：\n");
inorder1(head);
printf("\n");
printf("二叉树非递归后序遍历结果：\n");
postorder1(head);
return 0;
}
7.实验结果：
8.测试情况：
测试全部通过，递归遍历和非递归遍历均已经实现，代码如上。
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
