二叉树的各种遍历算法的实现
学生姓名：严智行  指导老师：肖增良
摘  要：本课程设计主要解决树的前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现。在课程设计中，系统开发平台为Windows 2000，程序设计设计语言采用Visual C++，用除递归算法前序，后续，中序遍历树外还通过非递归的算法遍历树。程序通过调试运行，初步实现了设计目标，并且经过适当完善后，将可以应用在商业中解决实际问题。
关键词  程序设计；C++；树的遍历；非递归遍历
1 引  言
本课程设计主要解决树的前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现。
1.1实验的目的 
通过对题目的分析编程，了解二叉树，知晓二叉树的各种遍历算法思想，树的遍历分为前序、
中序和后序，可以用递归算法实现树的三种遍历。除了递归外还可以构造栈，利用出栈和入栈来实现树的前序遍历、中序遍历和后序遍历。
1.2实验内容
  1) 构造一棵树并输入数据； 
  2) 实现二叉树的各种遍历；
  3) 随时显示操作的结果。
1.3实验要求
1） 编写创建二叉树的函数，函数名命名为creat( )。
2） 编写递归实现二叉树的先序、中序和后序遍历算法。函数名分别为：preorder、inorder、postorder。
3） 编写主函数测试以上二叉树的创建和遍历函数。
1.4 编程环境
    软件方面：测试系统在Windows 7 下的Microsoft Visual C++6.0环境中编写并测试。
    编程语言：c语言
    编程人员：1人完成。
1.5实验的意义 
  1)提高对数据逻辑结构的特点以及存储表示方式的认识，培养在具体应用中选择合适的数据结构和存储结构的能力。 
  2)熟悉软件开发的基本过程，初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等阶段基本任务和技能方法。 
  3)培养自己的算法设计和算法分析能力，提高综合运用所学的理论知识和方法独立分析和解决问题的能力。 
  4)综合运用二叉树的各种遍历算法，理论结合实际，将其运用到文章编辑这一实验中。使这些知识得到进一步巩固、加深和拓展。
2 数据结构设计
2.1模块说明
1）建树模块
    二叉树的建立函数，其原理是对于一般的二叉树，添加虚结点 ’二叉树的遍历及应用实验报告# ’使其成为完全二叉树，然后按顺序横向输入结点信息，以‘！’为结束标志，设置指针类型的数组来记录地址，使front指向队列里最前面的结点，rear指向输入的结点，其中front初始为0，rear初始为-1，增加counter计数，若输入的结点不是虚结点，则建立一个新结点，若是第一个，则令其为根结点，不断循环，直至遇到 ’! ’ 符号。
2）先序遍历算法模块
void preorder(TNODE *bt)
{
    if(bt!=NULL)
    {
        printf("%c  ",bt->data);
        preorder(bt->lchild);
        preorder(bt->rchild);
    }
}
3）中序遍历算法
void inorder(TNODE *bt)
{
    if(bt!=NULL)
    {
        inorder(bt->lchild);
        printf("%c    ",bt->data);
        inorder(bt->rchild);
    }
}
4）后序遍历算法
void postorder(TNODE *bt)
{
    if(bt!=NULL)
    {
        postorder(bt->lchild);
        postorder(bt->rchild);
        printf("%c    ",bt->data);
    }
}
2.2实验流程图
2.3页面设计
1）
******************************************************************
**    建立二叉树，请输入结点：（以# 表示虚节点，以!表示结束）  **
******************************************************************
2)
************************************************************
**  1递归先序遍历 2递归中序遍历 3递归后序遍历 0退出************************************************************
3详细设计
3.1设计的相关知识
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。
数据类型是一个值的集合和定义在这个值集上的一组操作的总称。数据类型可分为两类：原子类型、结构类型。一方面，在程序设计语言中，每一个数据都属于某种数据类型。类型明显或隐含地规定了数据的取值范围、存储方式以及允许进行的运算。可以认为，数据类型是在程序设计中已经实现了的数据结构。另一方面，在程序设计过程中，当需要引入某种新的数据结构时，总是借助编程语言所提供的数据类型来描述数据的存储结构。
此次课程设计是关于二叉树的各种遍历算法，首先建立一个树，然后有程序来分别输出先序遍历，中序遍历和后序遍历。
3.2实验流程图
4测试
4.1实验验证结果
  1） 可执行性：程序在刚写好的时候，里面未免会有一系列的错误，包括逻辑错误、语句错误及粗心引起的标点的错误等。在测试中，通过多次的测试来出其中的错误所在，并修改。 
2） 可用性：本次设计的主要目标是实现二叉树的前序遍历、中序遍历和后序遍历。在本块中，要通过运行程序进行一遍一遍的循环，判断，删除，通过调试、修改达到最后的目标。 
4.2实验测试截图
1)界面测试
图4.2-1界面测试截图
2）实验操作测试
图4.2-2测试操作截图a
图4.2-2测试操作截图b
5设计总结
  通过这次的课程设计，我认识到：仅仅掌握课本上的知识是不够的，在实际操作时，常常遇到一些问题，自己看不懂，更无法解决。不过，经过自己不断的思考，尝试着去更改代码中出现的问题。虽然开始很困难，但在老师和同学的帮助下，我逐渐的熟悉了许多操作，为后继工作的顺利进行做了准备。 个人的力量是薄弱的，我学会了咨询别人，不再胆怯，不再保守。在过程中和同学相互讨论，询问老师，不断进步。 
也许，我们可以说，编一个程仅仅是开始，调试和运行相比之下更难。实践中收获的远比想象的多。在这个编程中，如果你在设计时存在逻辑错误，虽然源代码没错，不过在运 行时就有问题，在调试中前后函数的功能要对应，要不然就不能正确运行，还有一些基本的符合不符合规范，注意英文字母的书写。 
  看到自己完成了所要求的任务，有一种无法用言语来形容的欣慰之感，这也是无法从学习书本知识中得到的。 
    课程设计的结束并不代表着学习的结束。这次的设计，把我带入到了一个全新的不曾接触过的领域，让我在以往只是注重操作的基础上，更多的思考到了，这是如何实现的，运用我所学到的知识是不是可以同样做出这样的网站，实现不一样的操作，达到同样的效果？我似乎有所领悟了，学习的本质不是让你牢牢的掌握一个知识，而是让你掌握一种方法，一种思想。
参考文献 
[1] 严蔚敏，吴伟民．数据结构（C语言版）．北京：清华大学出版社，2002
[2] 许卓．数据结构与算法．北京：高等教育出版社，2004
[3] 金远平．数据结构(C语言版）． 北京：清华大学出版社，2005
[4] 陈倩诒 邓红卫．数据结构（C语言版） 武汉：华中科技大学出版社，2013
附页：实验代码
#include <stdio.h>
#include <malloc.h>
struct tnode//结点结构体//
{
    char data;
    struct tnode *lchild,*rchild;
};
typedef struct tnode TNODE;
TNODE *creat(void)
{
    TNODE *root,*p;
    TNODE *queue[50];
    int front=0,rear=-1,counter=0;//初始队列中需要的变量front、rear和计数器counter//
    char ch;
    printf("**************************************************************************\n");
    printf("**      建立二叉树，请输入结点：（以# 表示虚节点，以!表示结束）    **\n");
    printf("**************************************************************************\n");
    ch=getchar();
    while(ch!='!')
    {
            if(ch!='#')
              {
                p=(TNODE *)malloc(sizeof(TNODE));
                  p->data=ch;
                  p->lchild=NULL;
                  p->rchild=NULL;
                rear++;
                queue[rear]=p;//把非#的元素入队//
                if(rear==0)//如果是第一个元素，则作为根节点//
                {
                    root=p;
                    counter++;
                }
                else
                {
                    if(counter%2==1)//奇数时与其双亲的左子树连接//
                    {
                        queue[front]->lchild=p;
                   
                    }
                    if(counter%2==0)//偶数时与其双亲的左子树连接//
                    {
                        queue[front]->rchild=p;
                        front++;
                       
                    }
                        counter++;
                }               
            }

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。