二叉树遍历课程设计

《二叉树遍历课程设计》由会员分享，可在线阅读，更多相关《二叉树遍历课程设计（12页珍藏版）》请在装配图网上搜索。

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

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

3、。画出搜索顺序示意图。三概要设计31创建二叉树32二叉树的非递归前序遍历示意图图3.2二叉树前序遍历示意图33二叉树的非递归中序遍历示意图图3.3二叉树中序遍历示意图34二叉树的后序非递归遍历示意图图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、,空格表示空树。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(

5、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=roo

6、t;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;else p=p-Rchild;root是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。 需要判断根结点的左右子树是否均遍历过。也可采用标记法，结点入栈时，配一个标志tag 同入栈 (1：遍历左子树前的现场保护，2：遍历右子树前的现场保护)。首先将bt和tag(

7、为1)入栈，遍历左子树； 返回后，修改栈顶tag为2，遍历右子树；最后访问根结点。五测试数据与分析JLIIL 口六源代码非递归算法实现：1.新建一个工程，再在工程中新建一个头文件，输入下列程序:#define m 50typedef struet Nodechar data;struet Node *Lehild;struet Node *Rehild;bitnode ,*bitree;typedef struet 一bit ree st aekm; /*用来存放栈中元素的一维数组*/ int top;SeqStack;void Ini tSt aek(SeqS tack *s) /*初始化栈

8、*/ s_top=_1;int isemp ty(SeqS tack * s)/ *判断栈是否为空*/if(s-to p=-1) return 1;else return 0;int push(SeqS tack * s,b it ree x)/ *进栈*/if(s-top=m-1) return(0);else s-top+;s-stacks-top=x; return(1);int pop(SeqS tack * s,bi tree * x)/ *出栈*/if(s-top=-1) return(0);else *x=s-stacks-top;s-top-; return(1);int Ge

9、t Top(SeqS tack * s,bi tree * x)/ *去栈顶元素*/ if(s-top=-1) return 0;else *x=s-stacks-top;return 1;void preorder(bi tree 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;v

10、oid 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-data); p=p-Rchild;void postorder(bitree root) /*后序遍历二叉树*/ SeqStack S;bitree p,q;InitStack(&S);p=root;while (p!=NULL | !isempty(&S

11、)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;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=

12、NULL;elsebt=(bitree)malloc(sizeof(bitnode);bt-data=ch;bt-Lchild=creatbitree();bt-Rchild=creatbitree();return bt;void main()int a;bitree bt;prin tf(请输入二叉树的线序序列，空子树用表示:n);bt=creatbitree();while(a!=0)printf(需要先序遍历输出请输入1,中序遍历请输入2,后序遍历请输入3,结束输 入0:);scanf(%d,&a);switch(a)case(1): preorder(bt); break;case(

13、2): inorder(bt); break;case(3): postorder(bt); break;case(0): break;printf(n);1.“ 数据结构 ”是计算机类各专业的核心课程，也是其他诸多类专业的重要选修课。 我通过学习这门课，可以为理解、应用和开发程序提供技术和方法支持，为后续课程的学 习提供重要思想和方法基础。同时对于我的逻辑思维培养和程序设计思想体系的建立有着 重要的影响。2.在调试过程中，碰到诸多问题，比如定义表长过小，处理记录数量错误时程序的异常，记录冲突次数等等。处在不断调试，询问老师,和同学探讨之后，终于解决，运行成功。参考文献:【I】耿国华数据结构一一C语言描述高等教育出版社【2】严蔚敏数据结构一一C语言描述清华大学出版社