二叉树遍历课程设计

1、目录一选题背景 . . 1二问题描述 . . 1三概要设计 . . 23.1. 创建二叉树 . . 23.2. 二叉树的非递归前序遍历示意图 . 23.3. 二叉树的非递归中序遍历示意图 . 23.4. 二叉树的后序非递归遍历示意图 . 3四详细设计 . . 44.1 创建二叉树 . 44.2 二叉树的非递归前序遍历算法 . 44.3 二叉树的非递归中序遍历算法 . 54.4 二叉树的非递归后序遍历算法 . 5五测试数据与分析 . . 7六源代码 . . 7总结 . 11参考文献 : . . 121二叉树的链式存储结构是用指针建立二叉树中结点之间的关系。二叉链存储结构的每个结点包含三个域，分别

2、是数据域，左孩子指针域，右孩子指针域。因此每个结点为leftchilddatarightchild由二叉树的定义知可把其遍历设计成递归算法。共有前序遍历、中序遍历、后序遍历。 可先用这三种遍历输出二叉树的结点。然而所有递归算法都可以借助堆栈转换成为非递归算法。以前序遍历为例，它要求首 先要访问根节点，然后前序遍历左子树和前序遍历右子树。特点在于所有未被访问的节点 中，最后访问结点的左子树的根结点将最先被访问，这与堆栈的特点相吻合。因此可借助 堆栈实现二叉树的非递归遍历。将输出结果与递归结果比较来检验正确性。 。二.问题描述对任意给定的二叉树（顶点数自定）建立它的二叉链表存贮结构，并利用栈的五种

3、基 本运算（置空栈、进栈、出栈、取栈顶元素、判栈空）实现二叉树的先序、中序、后序三 种遍历，输出三种遍历的结果。画出搜索顺序示意图。2三.概要设计3.1.创建二叉树3.2.二叉树的非递归前序遍历示意图图3.2二叉树前序遍历示意图3.3.二叉树的非递归中序遍历示意图3图3.3二叉树中序遍历示意图34二叉树的后序非递归遍历示意图图3.4二叉树后序遍历示意图4四详细设计4.1创建二叉树(1)定义二叉树结点值的类型为字符型。#define m 50typedef struct Nodechar data;struct Node *Lchild;struct Node *Rchild;bitnode,*

4、bitree;typedef struct(2)结点个数不超过50个。(3)按先序次序输入，构造二叉链表表示的二叉树4.2二叉树的非递归前序遍历算法void preorder(bitree root)SeqStack S;bitree p;InitStack(&S);p=root;while(p!=NULL|!isempty(&S)while(p!=NULL)printf(%c,(p-data); push(&S,p);p=p-Lchild;if(!isempty(&S)pop(&S,&p);p=p-Rchild;a.访问结点的数据域。b.指针指

5、向p的左孩子结点。c.从栈中弹出栈顶元素。T,空格表示空树。5d.指针指向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;elsepop(&S,&p); printf(%c,(p-data); p=p-Rchild;a.指针指向p的左孩子结点b.从栈中弹出栈顶元素。c.访问结点的数据域。d.指针指向p的右孩子

6、结点。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;elseGetTop(&S, &p);if (p-Rchild=NULL | p-Rchild=q) printf(%c,(p-data);pop(&S, &p);q=p;p=NULL;6elsep=p-Rchild;root是要遍历树的

7、根指针，后序遍历要求在遍历完左右子树后，再访问根 需要判断根结点的左右子树是否均遍历过。也可采用标记法， 结点入栈时， 配一个标志tag一同入栈（1：遍历左子树前的现场保护，2：遍历右子树前的现场保护）。 首先将bt和tag（为1）入栈，遍历左子树； 返回后，修改栈顶tag为2，遍历右子树；最后访问根结点。7五.测试数据与分析Xebuer.exe六.源代码非递归算法实现：1.新建一个工程，再在工程中新建一个头文件，输入下列程序：#defi ne m 50typedef struct Nodechar data;struct Node *Lchild;struct Node *Rchild;bi

8、t no de,*bitree;typedef structbitree stackm; /*用来存放栈中元素的一维数组*/int top;SeqStack;void InitStack(SeqStack *s) /*初始化栈*/s-top=-1;int isempty(SeqStack *s)/*判断栈是否为空*/if(s-top=-1) return 1;BC. .DEG. .F.需更土 N 遍片输出请输心,4DCEEGF需学土立偏.厅输出请畅J ,:BEGDFn斋罢立诵厅输出请輸1 .DGEFDBft斋琴叱序遍厅諭出荫牧7.序呼列，空子树用，表示:中序遍历请输入2,中序遍历请输人氛中序遍

9、厉请输人裁中序遍万请输入氛后序遍历请输A3.A0：1后序遍历请输入3.结束输入0:2后序遍厉请输 2 盘束输入師后序遍历请输入札结東输入肌8elsereturn 0;int push(SeqStack *s,bitree x)/*进栈*/if(s-top=m-1) return(0);elses-top+; s-stacks-top=x; return(1);int pop(SeqStack *s,bitree *x)/*出栈*/if(s-top=-1)return(0);else*x=s-stacks-top; s-top-; return(1);int GetTop(SeqStack *s

10、,bitree *x)/*去栈顶元素*/if(s-top=-1)return 0;else*x=s-stacks-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,(p-data);9push(&S,p);p=p-Lchild;if(!isempty(&S)pop(&S,&p); p=p-Rchild;void i

11、norder(bitree root) /*中序遍历二叉树*/SeqStack S;bitree p;InitStack(&S);p=root;while(p!=NULL|!isempty(&S)if(p!=NULL)push(&S,p);p=p-Lchild;elsepop(&S,&p);printf(%c,(p-data); p=p-Rchild;void postorder(bitree root) /*后序遍历二叉树*/SeqStack S;bitree p,q;InitStack(&S);p=root;while (p!=NULL |

12、!isempty(&S)if (p!=NULL)push(&S, p);p=p-Lchild;elseGetTop(&S, &p);if (p-Rchild=NULL | p-Rchild=q) printf(%c,(p-data); pop(&S, &p); q=p; p=NULL;elsep=p-Rchild;2再在工程中新建一个C+源文件，将它另存为以.c为扩展名的文件，输入下列程序：#include stdio.h#include malloc.h10#include order.hbitree creatbitree()char ch;

13、bitree bt;ch=getchar();if(ch=.)bt=NULL;elsebt=(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,&a);switch(a)case(1): preorder(bt); break;case(2): inorder(bt); break; case(3): postorder(bt); break; case(0): break;printf(n);总结1.“ 数据结构 ” 是计算机类各专业的核心课程， 也是其他诸多类专业的重要选修课。 我通过学习这门课，可以为