数据结构课设二叉树的遍历

1、 数据结构 课程设计说明书题目： 二叉树的遍历 学生姓名： 学 号： 院 （系）： 专 业： 指导教师： 年 月日目 录1 需求分析12 概要设计12.1 功能设计12.2 算法流程图23 详细设计23.1 创建二叉树23.2 二叉树的递归遍历算法33.3 二叉树的层次遍历算法33.4 二叉树的非递归遍历算法34 测试数据与分析35 算法分析96 总结9参 考 文 献10附录11数据结构课程设计1 需求分析数据结构是信息类专业最重要的专业基础课程，掌握好数据结构的知识将直接关系到后续专业课程的学习。数据结构研究四个方面的问题：（1）数据的逻辑结构，即数据之间的逻辑关系；（2）数据的物理结构，即

2、数据在计算机内的存储方式；（3）对数据的加工，即基于某种存储方式的操作算法；（4）算法的分析；即评价算法的优劣。 本实验是用链式存储结构来存储二叉树并进行一系列的算法，且结点内容的数据类型为字符型。 根据题目知，程序主要是根据给定二叉树的先序遍历结果，构造出二叉树并输出按中，后序遍历的结果，以及求二叉树的叶子个数等。其中二叉树的结点用字符表示。（1）创建二叉树：按先序次序输入，构造二叉链表表示的二叉树。（2）设计算法：先序遍历,中序遍历,后序遍历。（3）编写程序：设计main()函数调用以上步骤实现相关功能。 本程序用Microsoft Visual Studio 2008编写，可以实现各种二

3、叉树的遍历。包括先序遍历、中序遍历、后序遍历的递归算法，先序遍历、中序遍历、后序遍历的非递归算法以及能查找任一结点在某种遍历序列中的前驱和后继。2 概要设计2.1 功能设计（1）typedef struct BTNode定义二叉树定义一个用链式存储结构存储的二叉树，其中包括左孩子和右孩子以及数据元素的内容。和单链表类似，一个二叉链表由头指针唯一确定，若二叉树为空，则头指针指向空。并且结点内容的数据类型为字符型。（2）CreateBiTree(BiTree &T)构建二叉树此函数的功能是构建二叉树。从键盘上按先序次序输入字符构造二叉链表表示的二叉树T，其中用星号表示空树 。（3） NRPreOr

4、der(BiTree bt)先序遍历（非递归）此函数的功能是用非递归的方法实现二叉树的先序遍历算法。调用此函数可以获得二叉树的非递归的先序遍历的结果。（4）NRInOrder(BiTree bt)中序遍历（非递归）此函数的功能是用非递归的方法实现二叉树的中序遍历算法。调用此函数可以获得二叉树的非递归的中序遍历的结果。（5）NRPostOrder(BiTree bt)后序遍历（非递归）此函数的功能是用非递归的方法实现二叉树的后序遍历算法。调用此函数可以获得二叉树的非递归的后序遍历的结果。其中bt是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。可

5、采用标记法，结点入栈时，配一个标志tag一同入栈1：遍历左子树的现场保护，2：遍历右子树前的现场保护。首先将bt和tag(为1)入栈，遍历左子树；返回后，修改栈顶tag为2，遍历右子树；最后访问根结点。（6）PreOrderTraverse(BiTree T)先序遍历（递归）函数功能是用递归的方法对二叉树进行先序遍历，调用此函数可以获得二叉树的递归的先序遍历的结果。（7）InOrderTraverse(BiTree T)中序遍历（递归）函数功能是用递归的方法对二叉树进行中序遍历，调用此函数可以获得二叉树的递归的中序遍历的结果。（8）PostOrderTraverse(BiTree T)后序遍历

6、（递归）函数功能是用递归的方法对二叉树进行后序遍历，调用此函数可以获得二叉树的递归的后序遍历的结果。（9）main()主函数用while()与switch(select)语句对二叉树的操作的算法进行了设计。可以实现以上函数的功能，并能退出程序。2.2 算法流程图算法流程图如图1所示。图 2-1 算法流程图3 详细设计3.1 创建二叉树(1)定义二叉树结点值的类型为字符型。(2)结点个数不超过10个。(3)按先序次序输入，构造二叉链表表示的二叉树T，空格表示空树。3.2 二叉树的递归遍历算法DLR(1)访问根结点。(2)先序遍历根结点的左子数。(3)先序遍历根结点的右子数。LDR(1)先序遍历根

7、结点的左子数。(2)访问根结点。(3)先序遍历根结点的右子数。LRD(1)先序遍历根结点的左子数。(2)先序遍历根结点的右子数。(3)访问根结点。3.3 二叉树的层次遍历算法(1)访问该元素所指结点。(2)若该元素所指结点的左右孩子结点非空，则该元素所指结点的左孩子指针和右孩子指针顺序入队。3.4 二叉树的非递归遍历算法（1）非递归的先序遍历算法a.访问结点的数据域。b.指针指向p的左孩子结点。c.从栈中弹出栈顶元素。d.指针指向p的右孩子结点。（2）非递归的中序遍历算法a.指针指向p的左孩子结点。b.从栈中弹出栈顶元素。c.访问结点的数据域。d.指针指向p的右孩子结点。（3）非递归的后序遍历

8、算法bt是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。可采用标记法，结点入栈时，配一个标志tag一同入栈(1：遍历左子树前的现场保护。2：遍历右子树前的现场保护)。首先将bt和tag(为1)入栈，遍历左子树；返回后，修改栈顶tag为2，遍历右子树；最后访问根结点。4 测试数据与分析（1）运行程序，进入开始界面图4-1 开始运行（2）选择1，创建二叉树图4-2 创建二叉树(3)选择2，显示递归-中序遍历二叉树图4-3 递归-中序遍历二叉树（4）选择3，递归-前序遍历二叉树图4-4 递归-前序遍历二叉树（5）选择4，递归-后序遍历二叉树图4-5

9、 递归-后序遍历二叉树（6）选择5，非递归-后序遍历二叉树图4-6 非递归-后序遍历二叉树（7）选择6，层次遍历二叉树图4-7 层次遍历二叉树（8）选择7，计算二叉树的高度图4-8 二叉树的高度（9）选择8，计算二叉树的结点的个数图4-9 二叉树的结点的个数（10）选择9，计算二叉树的叶子结点个数图4-10 二叉树的叶子结点个数（11）选择10，交换二叉树的所有子树图4-11 交换二叉树的所有子树（12）选择0，则退出系统5算法分析 本程序按递归遍历所耗费的时间复杂度为O（n），其所耗费的空间复杂度也为O（n）。6 总结 这次课程设计，虽然看起来很简单，但是真的做起来的时候就发现了困难重重，让

10、我深刻的体会到了要用C语言做一个二叉树的遍历，里面需要的很多知识还是我们没有接触过的，所以我们需要不断的实践，不断的学习，不断的发现问题去思考问题。 通过此这次课程设计，我掌握了二叉树的存储实现，掌握了二叉树的遍历思想，掌握了二叉树的常见算法的程序实现。二叉树的高度（深度）为二叉树中结点层次的最大值，也可视为其左右字数高度的最大值加一。遍历二叉树的问题可以分解成两步，第一步是求出某种遍历次序下第一个被访问的结点，然后连续求出刚访问结点的后继结点，直至所有的结点均被访问。14参 考 文 献1张铭.数据结构与算法. 北京：高等教育出版社，20082 耿国华编.数据结构用C语言描述M.北京：高等教育

11、出版社，2011.63 谭浩强著.C+面向对象设计M.北京：清华大学出版社，2004.64 谭浩强著.C+程序设计M.北京：清华大学出版社，2004.6附录源程序代码#include #include #define MAXSIZE 100typedef char DataType;typedef struct BiTNode/* 二叉链表存储结构*/DataType data; struct BiTNode *lchild,*rchild;BiTree;typedef BiTree* ElemType ;/* 栈中数据元素类型，栈中保存结点指针*/typedef struct ElemTyp

12、e dataMAXSIZE; int top;SeqStack;/* 栈的类型定义，顺序栈*/typedef structElemType queueMAXSIZE;int front,rear;SP;SeqStack *initSeqStack() /* 初始化栈*/ SeqStack *s; /* 首先建立栈空间，然后初始化栈顶指针*/ s=(SeqStack*)malloc(sizeof(SeqStack); s-top=-1; return s;int push(SeqStack *s,ElemType x) if(s-top=MAXSIZE-1) /* 栈满不能入栈*/printf(

13、栈满); return 0; s-top+; s-datas-top=x; return 1;void pop(SeqStack *s) /* 出栈，假设栈不空*/ s-top-; int empty(SeqStack *s) if(s-top=-1) return 1; else return 0; ElemType top(SeqStack *s) /* 设栈不空*/return (s-datas-top); /* 递归算法创建二叉链表*/BiTree *createBiTree()DataType ch; BiTree *T; ch=getchar(); if(ch=0) return

14、NULL; else T=(BiTree *)malloc(sizeof(BiTree); T-data=ch; T-lchild=createBiTree(); T-rchild=createBiTree(); return T; /* 中序遍历二叉树的递归算法*/void InOrder(BiTree *T) if(T) InOrder(T-lchild); printf(%c,T-data); InOrder(T-rchild); /* 前序遍历二叉树的递归算法*/void PreOrder(BiTree *T)if(T)printf(%c,T-data); PreOrder(T-lch

15、ild); PreOrder(T-rchild); /* 后序遍历二叉树的递归算法*/void PostOrder (BiTree *T)if(T) PostOrder(T-lchild); PostOrder(T-rchild); printf(%c,T-data); /* 中序遍历二叉树的非递归算法*/void InOrderFei(BiTree *p)SeqStack *s; s=initSeqStack(); while(1) while(p) push(s,p); p=p-lchild;/* 先将结点指针压栈，待出栈时再访问*/ if(empty(s) break; p=top(s)

16、; pop(s); printf(%c,p-data); p=p-rchild; /* 按层次遍历*/void LevelOrder(BiTree *T) SP *p; p=(SP*)malloc(sizeof(SP); p-front=0; p-rear=0; if(T!=NULL) p-queuep-front=T; p-front=p-front+1; while(p-front!=p-rear) T=p-queuep-rear; p-rear=p-rear+1; printf(%c,T-data); if(T-lchild!=NULL) p-queuep-front=T-lchild;

17、/*左孩子进队列*/ p-front=p-front+1; if(T-rchild!=NULL) p-queuep-front=T-rchild;/*右孩子进队列*/ p-front=p-front+1; /* 求二叉树的高度*/int height(BiTree *T)int i,j; if(!T) return 0; i=height(T-lchild);/* 求左子树的高度*/ j=height(T-rchild);/* 求右子树的高度*/ return ij?i+1:j+1;/* 二叉树的高度为左右子树中较高的高度加*/* 求二叉树的所有结点个数*/int Nodes(BiTree *

18、T) int n1,n2; if(T=NULL) return 0; else if(T-lchild=NULL&T-rchild=NULL) return 1; else n1=Nodes(T-lchild); n2=Nodes(T-rchild); return n1+n2+1; /* 求二叉树的叶子结点个数*/int leafs(BiTree *T)int num1,num2; if(T=NULL) return 0; elseif(T-lchild=NULL&T-rchild=NULL) return 1; num1=leafs(T-lchild);/* 求左子树中叶子结点数*/ nu

19、m2=leafs(T-rchild);/* 求右子树中叶子结点数*/ return num1+num2; /* 交换二叉树的所有左右子树*/void exchange(BiTree *T) BiTree *temp=NULL; if(T-lchild=NULL&T-rchild=NULL) return; elsetemp=T-lchild; T-lchild=T-rchild; T-rchild=temp; if(T-lchild) exchange(T-lchild); if(T-rchild) exchange(T-rchild);/* 交换后二叉树的遍历*/void Display(B

20、iTree *T)printf(t交换后二叉树按中序遍历输出:);InOrder(T);printf(n); printf(t交换后二叉树按前序遍历输出:);PreOrder(T);printf(n); printf(t交换后二叉树按后序遍历输出:);PostOrder(T);printf(n);void menu() printf(n);printf(t*n); printf(tt1.递归-创建二叉链表n);printf(tt2.递归-中序遍历二叉树n);printf(tt3.递归-前序遍历二叉树n);printf(tt4.递归-后序遍历二叉树n);printf(tt5.非递归-中序遍历二叉树n);printf(tt6.层次-遍历二叉树n); printf(tt7.二叉树的高度n); printf(tt8.二叉树的结点个数n); printf(tt9.二叉树的叶子结点个数n);printf(tt10.交换二叉树的所有左右子树n);printf(tt0.退出系统n);printf(t*n);printf(nt请选择:); void main() BiTree *bt; bt=NULL;