二叉树遍历课程设计

目录一选题背景1二问题描述1三概要设计23.1.创建二叉树23.2.二叉树的非递归前序遍历示意图23.3.二叉树的非递归中序遍历示意图23.4.二叉树的后序非递归遍历示意图3四详细设计44.1创建二叉树44.2二叉树的非递归前序遍历算法44.3二叉树的非递归中序遍历算法54.4二叉树的非递归后序遍历算法5五测试数据与分析7六源代码7总结11参考文献:12一选题背景二叉树的链式存储结构是用指针建立二叉树中结点之间的关系。二叉链存储结构的每个结点包含三个域，分别是数据域，左孩子指针域，右孩子指针域。因此每个结点为leftchild data rightchild 由二叉树的定义知可把其遍历设计成递归算法。共有前序遍历、中序遍历、后序遍历。可先用这三种遍历输出二叉树的结点。然而所有递归算法都可以借助堆栈转换成为非递归算法。以前序遍历为例，它要求首先要访问根节点，然后前序遍历左子树和前序遍历右子树。特点在于所有未被访问的节点中，最后访问结点的左子树的根结点将最先被访问，这与堆栈的特点相吻合。因此可借助堆栈实现二叉树的非递归遍历。将输出结果与递归结果比较来检验正确性。二问题描述对任意给定的二叉树（顶点数自定）建立它的二叉链表存贮结构，并利用栈的五种基本运算（置空栈、进栈、出栈、取栈顶元素、判栈空）实现二叉树的先序、中序、后序三种遍历，输出三种遍历的结果。画出搜索顺序示意图。三概要设计3.1.创建二叉树3.2.二叉树的非递归前序遍历示意图 图3.2二叉树前序遍历示意图3.3.二叉树的非递归中序遍历示意图 图3.3二叉树中序遍历示意图3.4.二叉树的后序非递归遍历示意图 图3.4二叉树后序遍历示意图四详细设计4.1创建二叉树(1)定义二叉树结点值的类型为字符型。#define m 50typedef struct Nodechar 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)while(p!=NULL)printf(%c,(p-data);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;elsepop(&S,&p);printf(%c,(p-data);p=p-Rchild;a.指针指向p的左孩子结点。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,(p-data); pop(&S, &p); q=p; p=NULL; else p=p-Rchild; root是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。也可采用标记法，结点入栈时，配一个标志tag一同入栈(1：遍历左子树前的现场保护，2：遍历右子树前的现场保护)。首先将bt和tag(为1)入栈，遍历左子树；返回后，修改栈顶tag为2，遍历右子树；最后访问根结点。五测试数据与分析六源代码非递归算法实现：1 新建一个工程，再在工程中新建一个头文件，输入下列程序：#define m 50typedef struct Nodechar data;struct Node *Lchild;struct Node *Rchild;bitnode,*bitree;typedef structbitree stackm; /*用来存放栈中元素的一维数组*/int top;SeqStack;void InitStack(SeqStack *s) /*初始化栈*/s-top=-1;int isempty(SeqStack *s)/*判断栈是否为空*/if(s-top=-1)return 1;elsereturn 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,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);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;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 | !isempty(&S) if (p!=NULL) push(&S, p); p=p-Lchild; else GetTop(&S, &p); if (p-Rchild=NULL | p-Rchild=q) printf(%c,(p-data); pop(&S, &p); q=p; p=NULL; else p=p-Rchild; 2 再在工程中新建一个C+源文件，将它另存为以.c为扩展名的文件，输入下列程序：#include stdio.h#include malloc.h#include order.hbitree creatbitree()char ch;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. “ 数据结构 ” 是计算机类各专业的核心课程，也是其他诸多类专业的重要选修课。我通过学习这门课，可以为理解、应用和开发程序提供技术和方