《数据结构课程设计之二叉树和树的遍历》由会员分享，可在线阅读，更多相关《数据结构课程设计之二叉树和树的遍历（45页珍藏版）》请在金锄头文库上搜索。
1、#大学数据结构课程设计报告题目： 二叉树和树的遍历 院（系）： 计算机工程学院 学生姓名: 班级： 学号: 起迄日期: 2011-6-21 至 2011-6-25指导教师: 20102011 年度 第 2 学期 一、需求分析 1.问题描述：进行二叉树和树的各种遍历，包括递归和非递归。2.基本功能二叉树前序递归遍历、二叉树中序递归遍历、二叉树后序递归遍历、二叉树前序非递归遍历、二叉树中序非递归遍历、二叉树后序非递归遍历、二叉树层次非递归遍历树先根递归遍历、树后根递归遍历、树先根非递归遍历、树后根非递归遍历、树层次非递归遍历，可循环执行直到按退出键。3.输入输出字符串形式二、 概要设计1.设计思路
2、：在递归遍历二叉树时，主要看遍历的根的先后，可根据遍历根，遍历左子树和遍历右子树的顺序不同来实现二叉树的先序，中序，后序递归遍历，二叉树的先序和中序非递归则用到了栈，一般都是先根进栈然后左孩子进栈，二叉树的后序遍历则用到了队列，并用tag 数组值 0、1 来标记二叉树结点的左右，树的先根非递归和后序非递归则参考了二叉树的先序和中序非递归遍历，也用到了栈，它的层次遍历则用到了队列。2.数据结构设计：/二叉树的结点结构typedef struct bitnodechar data;struct bitnode *lchild,*rchild;bitnode,* bitree;/二叉树的栈的结构ty
3、pedef structbitree *base;bitree *top;int stacksize;sqstack;为二叉树的先序和中序非递归提供栈，保存已经访问过的结点信息。/二叉树后序非递归的栈的结构typedef struct node1bitree data30; /默认 30 个元素 ，这里需要一个辅助堆栈！int top;stack;top 能够保存结点是左还是右孩子，该栈为后序遍历提供保存结点信息。/二叉树的队列结点结构typedef struct qnodebitree data;struct qnode *next;qnode,*queueptr;/二叉树的队列结构type
4、def structqueueptr front;queueptr rear;linkqueue;该队列能为二叉树层序遍历提供先进先出的数据访问条件/树的结点结构typedef struct csnodechar data;struct csnode *firstchild,*nextsibling;csnode,*cstree;/树的栈的结构typedef structcstree *base;cstree *top;int stacksize;sqstack1;为树的前根和后根非递归遍历提供保存已经访问过的数据信息/树的队列结点结构typedef struct qnode1cstree d
5、ata;struct qnode1 *next;qnode1,*queueptr1;/树的队列结构typedef structqueueptr1 front;queueptr1 rear;linkqueue1;为树的层次遍历提供条件3.软件结构设计：coutlchild)先序遍历右子树(T-rchild)return 1;return 0;return 1;二叉树的中序后序递归遍历和它类似。二叉树的前序非递归：int preordertraverse1(bitree T)bitree p;sqstack s;initstack(s); /初始化一个栈p=T;while(p 不空或栈不空 )wh
6、ile(p 不空 )visit(p); /访问 ppush(s,p); p=p-lchild;if(!stackempty(s) pop(s,p);p=p-rchild;return 0;3.主要函数的程序流程图，实现设计中主程序和其他子模块的算法，以流程图的形式表示。输入进行的操作 mm 不是 1 、 2 或 3 则提示出错重输m = = 1进入二叉树操作是m = = 2否m = = 3否进入树的操作是否输入 nn = = 1进行二 叉树 前序递归遍历是n = = 2否n = = 3否进行二 叉树 中序递归遍历是n = = 4否进行二 叉树 后序递归遍历是n = = 5否进行二 叉树 前序
7、非 递归遍历是进行二 叉树 中序 非 递归遍历n = = 6是否输入 hh = = 1进行 树 先根递归遍历是h = = 2否h = = 3否h = = 4否h = = 5否进行 树 后根递归遍历是进行 树 先根非递归遍历是进行 树 后根非递归遍历是进行 树 非递归遍历是h = = 6否是n = = 7否n = = 8否是退出程序否否进行二 叉树 后序 非 递归遍历是进行二 叉树 层序非 递归遍历是输出树的遍历结果输出二叉树树的遍历结果开始结束4. 画出函数之间的调用关系图。当选择进行何种遍历时，通过 switch 语句能直接调用该函数，函数之间调用关系很少。四、 调试分析 1.实际完成的情况
8、说明（完成的功能，支持的数据类型等）：能进行二叉树和树的各种遍历，包括递归和非递归，支持的数据类型是 char 型。 2.程序的性能分析，包括时空分析：采用栈和队列来处理遍历，当树的输入数据不多时，占用时间和空间不多。3.上机过程中出现的问题及其解决方案：上机中出现了一些问题，首先是栈的应用还不是很熟练，在指针操作上出了一些问题，还有在一些时候没有把栈更改的信息及时返回，导致遍历时出错，在二叉树的后序非递归遍历时，需要在进队列的同时，把二叉树结点是左还是右通过 tag 数组用 0、1 来标记。在树的先根和后根遍历时，参照了二叉树的先序和中序遍历，层次遍历时则运用队列，和二叉树的层次遍历差别在于
9、它有多个孩子结点，因此在遍历时要注意。4.程序中可以改进的地方说明：遍历的内容基本实现了多种多样，但还可以尝试运用队列来建树，程序运行的界面还有待改进，容错方面也有待改进。5.程序中可以扩充的功能及设计实现假想：森林的遍历可以添加，主要实现可以参考树的遍历。五、测试结果六、用户手册说明如何使用你编写的程序，详细列出每一步的操作步骤：首先选择进行的操作 1:进行二叉树的操作 2:进行树的操作 3:退出。如果输入的不是1、2、或，3 则提醒输入错误，要重新输入。选择 1，进行二叉树操作，先建立一棵二叉树，按先输入本结点然后输左孩子右孩子的顺序,代表空结点，并且输入该二叉树的数据类型要是 char
10、型，二叉树建好之后按回车即可选择进行遍历： 1:二叉树前序递归遍历 2:二叉树中序递归遍历 3:二叉树后序递归遍历 4:二叉树前序非递归遍历 5:二叉树中序非递归遍历 6:二叉树后序非递归遍历 7:二叉树层次非递归遍历 8:退出，如果输入的不是这 8 个数，程序会自动退出，退出遍历二叉树后，还可选择进行树的操作，先建立树，然后按回车后，可选择树的遍历方式：树先根递归遍历 2:树后根递归遍历 3:树先根非递归遍历 4:树后根非递归遍历 5:树层次非递归遍历 6:退出，如果输入的不是这六个数，程序也会自动退出，否则会按照选择进行遍历。七、体会与自我评价 通过这次数据结构课程设计，让我复习了很多 c
11、 语言的知识，也加深了对数据结构知识的理解，达到了融会贯通的作用，尽管程序并不是完全自己独创，但大部分都是自己独立完成的，有一部分是借鉴参考了一些老师以前给的算法并与同学讨论完成的，但是也同样起到了锻炼自己读写程序的能力，在这个实验中，主要用到了栈和队列的知识，在递归遍历中，要理解递归的先后顺序和遍历时的根与左右子树的遍历，在用栈时则要明确进出栈的顺序，即先进后出，而在用队列时则要注意它是先进先出的顺序，在做二叉树的后序非递归遍历时，它和二叉树的前序和中序非递归遍历有很大差别，因为它需要一个标记数组tag，树的前根和后根非递归遍历与二叉树的先序和中序遍历很类似，只需要，稍作修改就可以了，它的非
12、递归层次遍历则要用一个队列，在队列出一个结点的同时，把它的各个兄弟结点都入队列，这样当把队列出空时，就是层次遍历了，就可以满足层次遍历的要求，这个程序在界面上有些粗糙，还可以改进，还可以尝试在建树时用队列而不是递归的方法，在程序中出现过指针指的非法的情况，这是对细节的掌握不够，还有体会到了用引用来作为参数的好处，它可以把函数对参数做的改变保存下来，而不需要每次都返回值。借鉴参考的遍历算法都很巧妙，值得自己去慢慢体会，并争取内化成一种解题思想，虽然编写程序过程很枯燥，有时候出现错误不会应对的时候也很懊恼，但最终实现之后还是很有成就感的，以后要多做题，勤于思考，不懂多问。争取有更大的进步。源代码#
13、include#define NULL 0using namespace std;#define stack_init_size 100#define maxsize 100#define stackincrement 10char e;/二叉树的结点结构typedef struct bitnodechar data;struct bitnode *lchild,*rchild;bitnode,* bitree;/二叉树访问结点数据的函数int visit(bitree p) coutdata)ch;if(ch=)T=NULL;elseif(!(T=(bitnode *)malloc(size
14、of(bitnode)exit(0);T-data=ch;createbitree(T-lchild);createbitree(T-rchild);return 1;/二叉树先序递归遍历int preordertraverse(bitree T)if(T)if(visit(T)if(preordertraverse(T-lchild)if(preordertraverse(T-rchild)return 1;return 0;return 1;/二叉树中序递归遍历int inordertraverse(bitree T)if(T)if(inordertraverse(T-lchild)if(
15、visit(T)if(inordertraverse(T-rchild)return 1;return 0;return 1;/二叉树后序递归遍历int postordertraverse(bitree T)if(T)if(postordertraverse(T-lchild)if(postordertraverse(T-rchild)if(visit(T)return 1;return 0;return 1; /栈的结点结构typedef structbitree *base;bitree *top;int stacksize;sqstack;/初始化一个空栈int initstack(sqstack &S)S.base=(bitree *)malloc(stack_init_size*sizeof(bitree);if(!S.base)exit(0);S.top=S.base;S.stacksize=stack_init_size;return 1;int pop(sqstack &S, bitree& p)/这里用了引用if(S.top=S.base)return 0;p=*-S.top;return 1;/压栈函数int push(sqstack &S,bitree p)if(S.top-S.base=S
