一．选题背景 ..................................................... 1 二．问题描述 ..................................................... 1 三．概要设计 ..................................................... 2 3.1.创建二叉树 ................................................ 2 3.2.二叉树的非递归前序遍历示意图 .............................. 2 3.3.二叉树的非递归中序遍历示意图 .............................. 2 3.4.二叉树的后序非递归遍历示意图 .............................. 3 四．详细设计 ..................................................... 3 4.1创建二叉树 ................................................ 3 4.2二叉树的非递归前序遍历算法 ................................ 3 4.3二叉树的非递归中序遍历算法 ................................ 4 4.4二叉树的非递归后序遍历算法 ................................ 5 五．测试数据与分析 ............................................... 6 六．源代码 ....................................................... 6 总结............................................................ 10 参考文献: ....................................................... 11
cheng
一．选题背景
二叉树的链式存储结构是用指针建立二叉树中结点之间的关系。二叉链存储结构的每个结点包含三个域，分别是数据域，左孩子指针域，右孩子指针域。因此每个结点为
leftchild data rightchild
由二叉树的定义知可把其遍历设计成递归算法。共有前序遍历、中序遍历、后序遍历。 可先用这三种遍历输出二叉树的结点。
然而所有递归算法都可以借助堆栈转换成为非递归算法。以前序遍历为例，它要求首先要访问根节点，然后前序遍历左子树和前序遍历右子树。特点在于所有未被访问的节点中，最后访问结点的左子树的根结点将最先被访问，这与堆栈的特点相吻合。因此可借助堆栈实现二叉树的非递归遍历。将输出结果与递归结果比较来检验正确性。。
二．问题描述
对任意给定的二叉树（顶点数自定）建立它的二叉链表存贮结构，并利用栈的五种基本运算（置空栈、进栈、出栈、取栈顶元素、判栈空）实现二叉树的先序、中序、后序三种遍历，输出三种遍历的结果。画出搜索顺序示意图。
cheng
cheng
三．概要设计
3.1.创建二叉树
3.2.二叉树的非递归前序遍历示意图
图3.2二叉树前序遍历示意图
3.3.二叉树的非递归中序遍历示意图
图3.3二叉树中序遍历示意图
cheng
cheng
3.4.二叉树的后序非递归遍历示意图
图3.4二叉树后序遍历示意图
四．详细设计
4.1创建二叉树
(1)定义二叉树结点值的类型为字符型。 #define m 50
typedef struct Node {
char data;
struct Node *Lchild; struct Node *Rchild; }bitnode,*bitree; typedef struct
(2)结点个数不超过50个。
(3)按先序次序输入，构造二叉链表表示的二叉树T，空格表示空树。 4.2二叉树的非递归前序遍历算法
void preorder(bitree root) {
SeqStack S;bitree p; InitStack(&S); p=root;
while(p!=NULL||!isempty(&S))
cheng
cheng
}
{ }
while(p!=NULL) {
printf(\"%c\ push(&S,p);
p=p->Lchild; }
if(!isempty(&S)) {
pop(&S,&p); p=p->Rchild; }
a.访问结点的数据域。
b.指针指向p的左孩子结点。 c.从栈中弹出栈顶元素。 d.指针指向p的右孩子结点。
4.3二叉树的非递归中序遍历算法
void inorder(bitree root) {
SeqStack S;bitree p; InitStack(&S); p=root;
while(p!=NULL||!isempty(&S)) {
if(p!=NULL) {
push(&S,p); p=p->Lchild; } else {
pop(&S,&p);
printf(\"%c\ p=p->Rchild; } } }
a.指针指向p的左孩子结点。
cheng
cheng
b.从栈中弹出栈顶元素。 c.访问结点的数据域。 d.指针指向p的右孩子结点。 4.4二叉树的非递归后序遍历算法
void postorder(bitree root) {
SeqStack S;bitree p,q; InitStack(&S); p=root;
while (p!=NULL || !isempty(&S)) {
if (p!=NULL) {
push(&S, p); p=p->Lchild; } else {
GetTop(&S, &p);
if (p->Rchild==NULL || p->Rchild==q) {
printf(\"%c\ pop(&S, &p); q=p; p=NULL; } else {
p=p->Rchild; } } } }
root是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。 需要判断根结点的左右子树是否均遍历过。
也可采用标记法，结点入栈时，配一个标志tag一同入栈
(1：遍历左子树前的现场保护，2：遍历右子树前的现场保护)。 首先将bt和tag(为1)入栈，遍历左子树；
返回后，修改栈顶tag为2，遍历右子树；最后访问根结点。
cheng
cheng
五．测试数据与分析
六．源代码
非递归算法实现：
1．新建一个工程，再在工程中新建一个头文件，输入下列程序： #define m 50
typedef struct Node {
char data;
struct Node *Lchild; struct Node *Rchild; }bitnode,*bitree; typedef struct {
bitree stack[m]; /*用来存放栈中元素的一维数组*/ int top; }SeqStack;
void InitStack(SeqStack *s) /*初始化栈*/ {
s->top=-1; }
int isempty(SeqStack *s)/*判断栈是否为空*/ {
if(s->top==-1) return 1;
cheng
cheng
else
return 0; }
int push(SeqStack *s,bitree x)/*进栈*/ {
if(s->top==m-1) return(0); else {
s->top++;
s->stack[s->top]=x; return(1); } }
int pop(SeqStack *s,bitree *x)/*出栈*/ {
if(s->top==-1) return(0); else {
*x=s->stack[s->top]; s->top--; return(1); } }
int GetTop(SeqStack *s,bitree *x)/*去栈顶元素*/ {
if(s->top==-1) return 0; else {
*x=s->stack[s->top]; return 1; } }
void preorder(bitree root)/*先序遍历二叉树*/ {
SeqStack S;bitree p; InitStack(&S); p=root;
while(p!=NULL||!isempty(&S)) {
while(p!=NULL) {
printf(\"%c\
cheng
cheng
push(&S,p);
p=p->Lchild; }
if(!isempty(&S)) {
pop(&S,&p); p=p->Rchild; } } }
void inorder(bitree root) /*中序遍历二叉树*/ {
SeqStack S;bitree p; InitStack(&S); p=root;
while(p!=NULL||!isempty(&S)) {
if(p!=NULL) {
push(&S,p); p=p->Lchild; } else {
pop(&S,&p);
printf(\"%c\ p=p->Rchild; } } }
void postorder(bitree root) /*后序遍历二叉树*/ {
SeqStack S;bitree p,q; InitStack(&S); p=root;
while (p!=NULL || !isempty(&S)) {
if (p!=NULL) {
push(&S, p); p=p->Lchild; } else {
GetTop(&S, &p);
cheng
cheng
if (p->Rchild==NULL || p->Rchild==q) {
printf(\"%c\ pop(&S, &p); q=p; p=NULL; } else {
p=p->Rchild; } } } }
2．再在工程中新建一个C++源文件，将它另存为以.c为扩展名的文件，输入下列程序： #include \"stdio.h\" #include \"malloc.h\" #include \"order.h\" bitree creatbitree() {
char ch;bitree bt; ch=getchar(); if(ch=='.') bt=NULL; else {
bt=(bitree)malloc(sizeof(bitnode)); bt->data=ch;
bt->Lchild=creatbitree(); bt->Rchild=creatbitree(); }
return bt; }
void main() {
int a; bitree bt;
printf(\"请输入二叉树的线序序列，空子树用'.'表示:\\n\"); bt=creatbitree(); while(a!=0)
{printf(\"需要先序遍历输出请输入1，中序遍历请输入2，后序遍历请输入3,结束输入0:\");
scanf(\"%d\ switch(a) {
case(1): preorder(bt); break;
cheng
cheng
case(2): inorder(bt); break; case(3): postorder(bt); break; case(0): break; }
printf(\"\\n\"); } }
总结
1. “ 数据结构 ” 是计算机类各专业的核心课程，也是其他诸多类专业的重要选修课。我通过学习这门课，可以为理解、应用和开发程序提供技术和方法支持，为后续课程的学习提供重要思想和方法基础。同时对于我的逻辑思维培养和程序设计思想体系的建立有着重要的影响。
2.在调试过程中，碰到诸多问题，比如定义表长过小，处理记录数量错误时程序的异常，记录冲突次数等等。处在不断调试，询问老师,和同学探讨之后，终于解决，运行成功。
cheng
cheng
参考文献:
【1】 耿国华 数据结构——C语言描述 高等教育出版社 【2】 严蔚敏 数据结构——C语言描述 清华大学出版社
cheng
因篇幅问题不能全部显示，请点此查看更多更全内容