基于二叉树遍历系统设计与实现课程设计论文(编辑修改稿)

基于二叉树遍历系统设计与实现课程设计论文(编辑修改稿)内容摘要：

性数据结构，其中一树和二叉树最重要。 树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构够可以用树来形象表示。 树在计算机领域中也得到了广泛应用，如在编译程序中，可以用树来表示源程序的语法结构。 二叉树是一种非线性数据结构，对它进行操作时总需要对每个数据逐一进行操作，这样就存在一个操作顺序问题，由此提出了二叉树的遍历操作问题，所谓遍历二叉树就是按某种顺序访问二叉树中某个结点一次且仅一次的过程，这里的访问可以是输出 .比较 .更新 .查看 元素内容等各种操作。 设计目的 二叉树结点结构 的建立。 、中序和后序遍历的基本操作。 设计内容 利用 二叉树特点和功能实现先序、中序和后序遍历 系统 的实现 ，具体功能：输入、输出 遍历结果 、 先序遍历、中序遍历和后序遍历 ，并能在屏幕上输出操作前后的结果。 设计要求 ,并建模。 ,界面友好。 长春建筑学院《数据结构》课程设计 （论文） 2 设计思想。 采用递归函数和非递归函数分别实现多种遍历的方式。 另外还有层次遍历，来充分实现本书对树的遍历。 ，采用边查找边删除的方式。 如果没有查找到，则不对树做任何的修改；如果查找到结点则删除。 系统模块划分。 ，逐个加入，逐个建立。 ，对数进行插入删除。 ，包括将所有方法归并在一起，还要建立查看界面一边有系统的视觉效果。 主要功能模块设计 程序 主要设计了几个功能：首先是创建二叉排序树，完成后出现任务菜单，菜单中设计了八个模块：树状输出二叉树，前序遍历二叉树，中序遍历二叉树，后序遍历二叉树，输出叶子结点，输出叶子结点个数，输出二叉树的深度，退出。 长春建筑学院《数据结构》课程设计 （论文） 3 第 2 章 系统总体设计 基本理论 （ 1）建立二叉树的操作就是用递归算法以先序遍历的次序从根结点开始建立一棵二叉树。 （ 2） 利用栈的非递归算法对二叉树进行遍历，从二叉树的根结点开始，自顶向下，同层自左往右访问树中的每个结点，此时，保存结点的顺序和访问的顺序刚好一致。 （ 3） 用递归算法求出左右子树的深度。 需求分析 ： （ 1）输入二叉树的特殊先序序列，建立二叉树。 （ 2）实现二叉树的层次遍历和中序遍历。 （ 3）求二叉树的深度。 （ 4）将二叉树中所有结点的左右子树相互交换。 （ 5）求二叉树中叶子结点的数目。 概要设计 CreatBinTree(amp。 T):建立一棵二叉树， Value(T,e)：查找值为 e的二叉树结点，并返回该结点的地址。 BinTreeDepth(T)：返回二叉树的深度， Parent(T,e)：查找二叉树 T 中的值为 e 的结点的双亲，若没有根结点，则操作失败。 PreOrderTraverse(T)：先序遍历二叉树，并输出结点序列。 InorderTraverse(T)：中序遍历二叉树，并输出结点序列。 PostOrderTraverse(T)：后序遍历二叉树，并输出结点序列。 LevelOrderTraverse(T)：层次遍历二叉树，并输出结点序列。 说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次 (调用 )关系。 长春建筑学院《数据结构》课程设计 （论文） 4 第 3 章 详细设计 Void CreateBinTree(BinTreeamp。 T) {//按先序次序输入二叉树中结点的值 //构造二叉链表表示的二叉树 T TelemType ch； Scanf(“ %c” ,amp。 ch)。 If(i==’’ ) T=Null。 Else { T=(BinTree)malloc(sizeof(BinTNode))。 //生成根结点 Id(!=T) Exit(0)。 Tdata=ch。 CreateBinTree(Tlchild)。 //构造左子树 CreateBinTree(Trchild)。 //构造右子树 } Return。 } 二叉树的 层次遍历和中序遍历 中序遍历模块（以中序为例来说明） 遍历（ Traversal）是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。 访问结点所做的操作依赖于具体的应用问题。 二叉树共有三个部分组成，即根结点，根结点的左子树，根结点的右子树。 限定以从左至右方式共有三种遍历方式，即前序遍历，中序遍历，后序遍历。 中序遍历的原则：若被遍历的二叉树为非空，则依次执行如下操作： 长春建筑学院《数据结构》课程设计 （论文） 5 include // malloc()等 include // 标准输入输出头文件，包 括 EOF(=^Z 或 F6)， NULL 等 include // atoi()， exit() include // 数学函数头文件，包括 floor()， ceil()， abs()等 define ClearBiTree DestroyBiTree // 清空二叉树和销毁二叉树的操作一样 typedef struct BiTNode { int data。 // 结点的值 BiTNode *lchild,*rchild。 // 左右孩子指针 }BiTNode,*BiTree。 int Nil=0。 // 设整型以 0为空 void visit(int e) { printf(%d ,e)。 // 以整型格式输出 } void InitBiTree(BiTree amp。 T) { // 操作结果：构造空二叉树 T T=NULL。 } void CreateBiTree(BiTree amp。 T) { // 算法 ：按先序次序输入二叉树中结点的值 (可为字符型或整型，在主程中定义 )， // 构造二叉链表表示的二叉树 T。 变量 Nil 表示空 (子 )树。 修改 int number。 scanf(%d,amp。 number)。 // 输入结点的值 if(number==Nil) // 结点的值为空 T=NULL。 else // 结点的值不为空 { T=(BiTree)malloc(sizeof(BiTNode))。 // 生成根结点 if(!T) exit(OVERFLOW)。 Tdata=number。 // 将值赋给 T所指结点 CreateBiTree(Tlchild)。 // 递归构造 左子树 长春建筑学院《数据结构》课程设计 （论文） 6 CreateBiTree(Trchild)。 // 递归构造右子树 } } void DestroyBiTree(BiTree amp。 T) { // 初始条件：二叉树 T 存在。 操作结果：销毁二叉树 T if(T) // 非空树 { DestroyBiTree(Tlchild)。 // 递归销毁左子树，如无左子树，则不执行 任何操作 DestroyBiTree(Trchild)。 // 递归销毁右子树，如无右子树，则不执 行任何操作 free(T)。 // 释放根结点 T=NULL。 // 空指针赋 0 } } void。