数据结构与算法课程设计二叉树仿真指针储存结构操作设计说明书

1、数学与计算机学院课程设计说明书课 程 名 称: 数据结构与算法课程设计 课 程 代 码: 题 目:二叉树的仿真指针储存结构操作年级/专业/班: 学 生 姓 名: 学 号: 开 始 时 间: 2011 年 12 月 08 日完 成 时 间: 2011 年 12 月 20 日课程设计成绩：学习态度及平时成绩（30）技术水平与实际能力（20）创新（5） 说明书（计算书、图纸、分析报告）撰写质量（45）总 分（100）指导教师签名： 年 月 日 二叉树的仿真指针存储结构操作目 录引 言- 1 -1 需求分析- 1 -1.1任务与分析- 1 -1.2测试数据- 2 -1.2.1二叉树1- 2 -1.2.

2、2二叉树2- 3 -1.2.3二叉树3- 3 -2 概要设计- 4 -2.1 adt描述- 4 -2.2 程序模块结构- 5 -2.3 各功能模块- 5 -3详细设计- 6 -3.1结构体定义- 6 -3.2 栈模板定义- 6 -3.3 类定义- 7 -3.4 初始化- 8 -3.5 创建二叉树操作- 9 -3.6 输出二叉树操作- 9 -3.7 先序遍历操作- 10 -3.8 中序遍历操作- 11 -3.9 后序遍历操作- 13 -3.10 撤销二叉树操作- 15 -3.11 查找操作- 15 -3.12 求各节点度操作- 16 -3.13 求二叉树深度操作- 16 -3.14 判断操作-

3、17 -3.15 菜单函数- 19 -4 调试分析- 21 -4.1问题分析- 21 -4.2时间复杂度分析- 21 -4.3经验和体会- 22 -5用户使用说明- 22 -6测试结果- 23 -6.1菜单函数- 23 -6.2创建二叉树函数- 23 -6.3输出二叉树函数- 24 -6.4先序遍历二叉树- 25 -6.5中序遍历二叉树- 26 -6.6后序遍历二叉树- 26 -6.7撤销二叉树函数- 27 -6.8查找函数- 27 -6.8.1基于二叉树1的查找成功- 27 -6.8.2基于二叉树1查找失败- 28 -6.9求各节点度函数- 28 -6.10求二叉树深度函数- 29 -6.1

4、1判断函数- 29 -结 论- 31 -致 谢- 32 -参考文献- 33 - 1 - 二叉树的仿真指针存储结构操作- 31 -摘 要随着计算机的应用以惊人的速度普及，计算机的应用早已不局限于科学计算，而更多的应用在现实生活中。数据的储存结构多种多样，其中树型结构是以分支关系定义的层次结构，是一种重要的非线性结构。树型结构在客观世界中广泛存在，例如在计算机文件管理和信息组织方面用树型结构来表示，又如人类的家庭族谱以及各种社会组织机构也都可以用树型结构来表示。而二叉树是一种有着重要用途的树型结构。研究二叉树的基本概念、储存结构以及相关运算，对研究一般树的储存和运算有着重要意义。本文研究二叉树的仿

5、真指针储存结构的实现以及一般操作。关键词：储存结构；二叉树；仿真指针储存；一般操作。引 言数据结构就是反映数据在内存中的存储方式以及对数据进行的一系列操作。数据结构可以和生活实际相联系，用于解决生活中实际问题。课程设计正是基于这个目的，通过课程设计，锻炼我们发现问题，解决问题的能力。该次课程设计任务是实现有向图的邻接矩阵存储方式及其相关操作，采用vs2010编程环境。1 需求分析1.1任务与分析dcgefba二叉树的仿真指针存储结构是用数组存储二叉树中的结点，数组中每个结点除数据元素域外，再增加仿真指针域用于仿真常规指针建立二叉树中结点之间的关系。如右图所示，二叉树按仿真指针存储为：数组下标d

6、atalchildrchild0a121b342c563d-1-14e-1-15f-1-16g-1-1编写程序实现二叉树仿真指针存储结构，并实现如下操作：1)输出该二叉树；2)写出三种遍历算法，输出遍历序列；3)二叉树的撤销操作4)查找数据元素操作5)求各结点度的操作6)求出该二叉树的深度7)判断该二叉树是否是完全二叉树？1.2测试数据1.2.1二叉树1数组下标datalchildrchild0a121b342c5-13d-1-14e-1-15f-1-11.2.2二叉树2数组下标datalchildrchild0a121b342c5-13d-1-14e6-15f-1-16g-1-11.2.3二

7、叉树3数组下标datalchildrchild0a-1-12 概要设计2.1 adt描述 adt binarytree数据对象：d=具有相同特性的数据元素的有限集合；数据关系：r=顺序储存基本操作：初始化一棵空树；建立一颗二叉树；输出一颗二叉树；二叉树的先序遍历；二叉树的中序遍历；二叉树的后序遍历；二叉树中数据元素的查找；求二叉树深度；求二叉树各结点度；判断二叉树是否是完全二叉树；销毁二叉树；等等；adt binarytree；2.2 程序模块结构2.3 各功能模块bitree(); /构造函数bitree() ; /析构函数void menu(); /菜单函数void creat(); /建

8、立二叉树void display(); /输出二叉树void preorder(); /先序遍历void inorder(); /中序遍历void postorder(); /后序遍历void destroy () /撤销二叉树void search(); /查找数据元素void predegree(); /求各结点度int predepth(nodetype bt); /求二叉树的深度void predepth_bt(); /调用predepth(nodetype bt)int max(int x,int y); /比较函数void isfull_bt(); /调用is_full(nodet

9、ype m)bool is_full(nodetype m); /7)判断二叉树是否是完全二叉树3详细设计3.1结构体定义struct nodetypeelemtype data; /存放结点值int lchild,rchild; /存放左、右孩子的数组元素的下标;3.2 栈模板定义#include stdafx.htemplate class sqstackprivate:type *stackspace;int maxsize;int top;public:sqstack(int m=30);int isempty() return top=-1; int isfull() return

10、top=maxsize-1; void push(type p);type pop();type gettop();template sqstack :sqstack(int m)top=-1; maxsize=m; stackspace =new typemaxsize;template void sqstack :push(type p)if(!isfull() top+; stackspacetop=p; template type sqstack :pop()type p;if(!isempty() p=stackspacetop; top-; return p;template ty

11、pe sqstack :gettop()if(!isempty() return stackspacetop;3.3 类定义class bitreeprivate:int length;nodetype *bt;public:bitree();bitree() ;void menu();void creat(); /建立二叉树void display(); /1)输出二叉树void preorder(); /2)先序遍历void inorder(); /2)中序遍历void postorder(); /2)后序遍历void destroy () /3)撤销二叉树void search(); /

12、4)查找数据元素void predegree(); /5)求各结点度int predepth(nodetype bt); /6)求二叉树的深度void predepth_bt();int max(int x,int y);void isfull_bt();bool is_full(nodetype m);/7)判断二叉树是否是完全二叉树;3.4 初始化bitree:bitree()bt=new nodetype maxsize; length=0;for(int i=0;ilength;i+) bti.data= ; bti.lchild=-1; bti.rchild=-1; 3.5 创建二叉

13、树操作void bitree:creat()int l;coutl; length=l;if(length!=0)cout按层序遍历输入二叉树数据（数据，左孩子下标，右孩子下标）：n;for(int i=0;ibti.data; cinbti.lchild; cinbti.rchild;3.6 输出二叉树操作void bitree:display() /1)输出二叉树if(length=0)cout二叉树为空！n;elsecout按层序遍历输出二叉树数据：n;cout数组下标 数据(data) 左孩子(lchild) 右孩子(rchild)n;for(int i=0;ilength;i+) c

14、outisetw(8)bti.datasetw(8)bti.lchildsetw(8)bti.rchildendl; 3.7 先序遍历操作void bitree:preorder() /2)先序遍历输出if(length=0)cout二叉树为空！n;elsecout按先序遍历输出二叉树数据：n;cout数组下标 数据(data) 左孩子(lchild) 右孩子(rchild)n;nodetype m; m=bt0;int i=0,bool=1;sqstack s;sqstack t;while(bool)while(i!=-1)coutisetw(8)bti.datasetw(8)bti.lc

15、hildsetw(8)bti.rchildendl;s.push(m); t.push(i);i=bti.lchild;if(i=-1) break;else m=bti;if(s.isempty() & t.isempty() bool=0;elsei=t.pop() ; m=s.pop();while(m.rchild=-1 & !s.isempty() & !t.isempty() i=t.pop() ; m=s.pop(); i=bti.rchild;if(i=-1) ;else m=bti;3.8 中序遍历操作void bitree:inorder() /2)中序遍历输出if(len

16、gth=0)cout二叉树为空！n;elsecout按中序遍历输出二叉树数据：n;cout数组下标 数据(data) 左孩子(lchild) 右孩子(rchild)n;nodetype m; m=bt0;int i=0,bool=1;sqstack s;sqstack t;while(bool)while(i!=-1)s.push(m); t.push(i);i=bti.lchild;if(i=-1) break;else m=bti; if(s.isempty() & t.isempty() bool=0;elsei=t.pop() ; m=s.pop();while(m.rchild=-1

17、 & !s.isempty() & !t.isempty()coutisetw(8)bti.datasetw(8)bti.lchildsetw(8)bti.rchildendl;i=t.pop() ; m=s.pop();coutisetw(8)bti.datasetw(8)bti.lchildsetw(8)bti.rchildendl;i=bti.rchild;if(i=-1) ;else m=bti;3.9 后序遍历操作void bitree:postorder() /2)后序遍历输出if(length=0)cout二叉树为空！n;elsecout按后序遍历输出二叉树数据：n;cout数组

18、下标 数据(data) 左孩子(lchild) 右孩子(rchild)n;nodetype m; m=bt0;int i=0,bool=1,printedmaxsize;for(int j=0;jmaxsize;j+) printedj=0;sqstack s;sqstack t,j;while(bool)while(i!=-1)s.push(m); t.push(i); j.push(1);i=bti.lchild;if(i=-1) break;else m=bti; if(s.isempty() & t.isempty() bool=0;elseif(j.gettop()=1)j.pop(

19、); j.push(2); i=t.gettop(); m=s.gettop();i=bti.rchild; if(i=-1) ;else m=bti;elsei=t.pop() ; m=s.pop(); j.pop();coutisetw(8)bti.datasetw(8)bti.lchildsetw(8)bti.rchildendl;printedi=1;i=bti.rchild;if(i=-1) ;elseif(printedi=1) i=-1;else m=bti;3.10 撤销二叉树操作void destroy () /3)撤销二叉树 length=0; delete bt; cou

20、t撤销二叉树成功！n; 3.11 查找操作void bitree:search() /4)查找数据元素if(length=0)cout二叉树为空！n;elseelemtype elem; int i;coutelem;for(i=0;imaxsize;i+)if(elem=bti.data) cout查找的结点如下：n;cout数组下标：i 结点值：bti.data;cout 左孩子下标：bti.lchild 右孩子下标：bti.rchild=maxsize) cout查找的结点不存在！n; 3.12 求各节点度操作void bitree:predegree() /5)求各结点度if(leng

21、th=0)cout二叉树为空！n;elseint dg;for(int i=0;ilength;i+)dg=0;if(bti.lchild!=-1) dg+;if(bti.rchild!=-1) dg+;cout数组下标：i 结点值：bti.data 结点度：dgendl;3.13 求二叉树深度操作void bitree:predepth_bt()if(length=0)cout二叉树为空,树的深度为！n;elsenodetype bt=bt0;cout树的深度为：predepth(bt)=y?x:y);3.14 判断操作void bitree:isfull_bt() /7)判断二叉树是否是完

22、全二叉树if(length=0)cout二叉树为空！n;elsenodetype bt=bt0;if(is_full(bt) /调用is_fullbt(bt)函数判断是否是完全二叉树，是则返回真，否则返回假cout该二叉树是完全二叉树！n;elsecout该二叉树不是完全二叉树！n;bool bitree:is_full(nodetype bt)int num1=1,num2=2,j=0;if(bt.lchild=-1 & bt.rchild=-1) /判断二叉树是否只有根节点，若只有根节点，则是完全二叉树，返回真。return true;elsefor(int i=1;i=length |

23、num2-12(predepth(bt)-1)-1，=(2predepth(bt)-1,若不是，返回假return false;elsewhile(2*j=length-1) /2*j=length-1时，节点j有下标为*j+1的左孩子，否则没有。若有左孩子但下标不为*j+1，则返回假if(btj.lchild!=-1 & btj.lchild!=2*j+1)return false;else j+;j=0;while(2*j+1=length-1) /2*j=length-1时，节点j有且只有下标为*j+1+1的右孩子，否则没有。若有右孩子但下标不为*j+1，则返回假if(btj.rchil

24、d!=-1 & btj.rchild!=2*j+1+1)return false;else j+;return true;3.15 菜单函数void bitree:menu()int choice;cout*二叉树的仿真指针存储结构操作*n;cout* 1.建立二叉树 *n;cout* 2.输出二叉树 *n;cout* 3.先序遍历二叉树 *n;cout* 4.中序遍历二叉树 *n;cout* 5.后序遍历二叉树 *n;cout* 6.撤销二叉树 *n;cout* 7.查找数据元素 *n;cout* 8.求各结点度 *n;cout* 9.求二叉树的深度 *n;cout* 10.判断二叉树是否是

25、完全二叉树 *n;cout* 0.退出 *n;cout*谢谢使用！*n;coutchoice;switch(choice)case 1: creat(); menu(); coutendl; break; case 2: display(); coutendl; menu(); break; case 3: preorder(); coutendl; menu(); break; case 4: inorder(); coutendl; menu(); break; case 5: postorder(); coutendl; menu(); break; case 6: destroy();

26、 coutendl; menu(); break; case 7: search(); coutendl; menu(); break; case 8: predegree(); coutendl; menu(); break; case 9: predepth_bt(); coutendl; menu(); break; case 10: isfull_bt(); coutendl; menu(); break; case 0: cout退出程序！n; coutendl; break;default: cout输入选择错误！n; coutendl; menu(); 4 调试分析4.1问题分析

27、该次试验中，认识到了二叉树的仿真指针存储结构，用数组存储二叉树中的结点，数组中每个结点除数据元素域外，再增加仿真指针域用于仿真常规指针建立二叉树中结点之间的关系，以及通过仿真指针储存对二叉树的一些基本操作，结合二叉树的链表储存及仿真指针储存，加深了对二叉树的理解。在后序遍历二叉树和判断二叉树是否是完全二叉树时，通过网上查阅资料及书籍的帮助下成功完成算法。4.2时间复杂度分析void creat()：假设二叉树的结点个数为n，即表长length=n，对每个节点都要输入一次。所以时间复杂度t(n)=o(n)。void display()：假设二叉树的结点个数为n，即表长length=n，对每个节点

28、都要输入一次。所以时间复杂度t(n)=o(n)。void preorder()：假设二叉树的结点个数为n，即表长length=n，对每个节点都要进行一次出栈和进栈，即入栈和出栈各执行n次，对结点访问n次记作o(n)；伴随遍历每个结点都要涉及两次入栈和两次出栈操作，也记作o(n)。所以时间复杂度t(n)=o(n)。void inorder()：假设二叉树的结点个数为n，即表长length=n，对每个节点都要进行一次出栈和进栈，即入栈和出栈各执行n次，对结点访问n次，记作o(n)；伴随遍历每个结点都要涉及两次入栈和两次出栈操作，也记作o(n)。所以时间复杂度t(n)=o(n)。void posto

29、rder()：假设二叉树的结点个数为n，即表长length=n，对每个节点都要进行一次出栈和进栈，即入栈和出栈各执行n次，对结点访问n次，记作o(n)；伴随遍历每个结点都要涉及三次入栈和三次次出栈操作，也记作o(n)。所以时间复杂度t(n)=o(n)。void search()：假设二叉树的结点个数为n，即表长length=n，需查找的结点下标为i，则需对你i个结点进行比较。所以时间复杂度t(n)=o(n)。void predegree():假设二叉树的结点个数为n，即表长length=n，对每个节点都要进行一次统计结点度。所以时间复杂度t(n)=o(n)。int predepth(nodet

30、ype bt)：假设二叉树的结点个数为n，即表长length=n，对每个节点都要遍历一次。所以时间复杂度t(n)=o(n)。bool is_full(nodetype m)：假设二叉树的结点个数为n，即表长length=n，对每个节点都要遍历一次。所以时间复杂度t(n)=o(n)。4.3经验和体会此次课程设计中，体会到了到编写程序时，必须要理清思路，认识到完成算法需要创建什么，需要什么循环语句，该在什么情况是退出循环，并且不能只想不动，有新的想法时需要动手实现并通过测试判断算法是否真确实现。5用户使用说明用户需安装microsoft visual studio 2008，microsoft visual studio 2010编程软件，并按照提示输入。6测试结果6.1菜单函数图6-1 菜单函数图6.2创建二叉树函数图6-2.1 创建二叉树1图图6-2.1 创建二叉树2图图6-2.