数据结构课程设计之二叉树和树的遍历.doc

《数据结构课程设计之二叉树和树的遍历.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、##大学数据结构课程设计报告题目：二叉树和树的遍历院（系）：计算机工程学院学生姓名:班级：学号:起迄日期:2011-6-21至2011-6-25指导教师:2010—2011年度第2学期一、需求分析1.问题描述：进行二叉树和树的各种遍历，包括递归和非递归。2.基本功能二叉树前序递归遍历、二叉树中序递归遍历、二叉树后序递归遍历、二叉树前序非递归遍历、二叉树中序非递归遍历、二叉树后序非递归遍历、二叉树层次非递归遍历树先根递归遍历、树后根递归遍历、树先根非递归遍历、树后根非递归遍历、树层次非递归遍历，可循环执行直到按退出键。3.输

2、入输出字符串形式二、概要设计1.设计思路：在递归遍历二叉树时，主要看遍历的根的先后，可根据遍历根，遍历左子树和遍历右子树的顺序不同来实现二叉树的先序，中序，后序递归遍历，二叉树的先序和中序非递归则用到了栈，一般都是先根进栈然后左孩子进栈，二叉树的后序遍历则用到了队列，并用tag数组值0、1来标记二叉树结点的左右，树的先根非递归和后序非递归则参考了二叉树的先序和中序非递归遍历，也用到了栈，它的层次遍历则用到了队列。2.数据结构设计：//二叉树的结点结构typedefstructbitnode{chardata;structb

3、itnode*lchild,*rchild;}bitnode,*bitree;//二叉树的栈的结构typedefstruct{bitree*base;bitree*top;intstacksize;}sqstack;为二叉树的先序和中序非递归提供栈，保存已经访问过的结点信息。//二叉树后序非递归的栈的结构typedefstructnode1{bitreedata[30];//默认30个元素，这里需要一个辅助堆栈！！！inttop;}stack;top能够保存结点是左还是右孩子，该栈为后序遍历提供保存结点信息。//二叉树的队

4、列结点结构typedefstructqnode{bitreedata;structqnode*next;}qnode,*queueptr;//二叉树的队列结构typedefstruct{queueptrfront;queueptrrear;}linkqueue;该队列能为二叉树层序遍历提供先进先出的数据访问条件//树的结点结构typedefstructcsnode{chardata;structcsnode*firstchild,*nextsibling;}csnode,*cstree;//树的栈的结构typedefstr

5、uct{cstree*base;cstree*top;intstacksize;}sqstack1;为树的前根和后根非递归遍历提供保存已经访问过的数据信息//树的队列结点结构typedefstructqnode1{cstreedata;structqnode1*next;}qnode1,*queueptr1;//树的队列结构typedefstruct{queueptr1front;queueptr1rear;}linkqueue1;为树的层次遍历提供条件3.软件结构设计：cout<<"1:进行二叉树的操作2:进行树的操作3

6、:退出"<

7、历是：";gradatraverse(T);cout<<"先根递归遍历是：";preordertraverse2(T1);cout<<"后根递归遍历是：";postordertraverse2(T1);cout<<"树前根非递归遍历是：";preordertraverse3(T1);cout<<"树后根非递归遍历是：";postordertraverse3(T1);cout<<"层次非递归遍历是：";gradatraverse1(T1);函数的返回值都是int型的，当函数执行成功，会返回1。三、详细设计1.定义程序中所有用

8、到的数据及其数据结构，及其基本操作的实现；//二叉树的结点结构typedefstructbitnode{chardata;structbitnode*lchild,*rchild;}bitnode,*bitree;//二叉树的栈的结构typedefstruct{bitree*base;bitree*to