数据结构课程设计二叉树遍历C语言

1、淮阴工学院实践报告数据结构课程设计设计题目：二叉树遍历系 别： 计算机工程学院 专 业： 软件工程 班 级： 软件1111 学生姓名: 周淼 学 号: 1111315217 起止日期: 2012年12月24日2012年12月30日指导教师： 寇海洲 摘要：现代社会生活中，计算机扮演着重要角色，而随着计算机运行速度的不断加快，对数据的处理能力也日益增强，因此，程序所涉及的数据成爆发式增长。随之而来的问题就是如何科学有效的对数据进行操作，使得计算机的时间和空间利用率最高。针对这样的问题，我选择了二叉树对数据的各种操作作为我的课程设计主题，希望通过课程设计来提高对数据的处理能力，促进对数据结构课程的

2、理解，在日后面向对象的程序设计中科学的规划数据结构。在本次课程设计中，二叉树的建立使用了递归算法，遍历则同时使用了递归与非递归的算法，同时，在遍历算法的实现中使用了栈结构与队列结构，这大大方便了二叉树的遍历。在前序、中序、后续遍历算法中，分别实现了递归与非递归算法，从实际应用中体验了递归这一算法的优越性。关键词：二叉树建立，递归与非递归，遍历，栈，队列编号： 47 淮阴工学院 软件工程 专业数据结构课程设计答辩记录课题名称： 二叉树的算法 班 级 软件1111 学 号 1111315217 姓 名 周淼 答 辩 记 录问题1：课题中涉及到哪些数据结构和算法？答： 1）数组，二叉树，栈，队列，线

3、性表2）二叉树的中序、前序、后序的递归、非递归遍历算法，层次序遍历非递归算法，栈、队列的实现算法问题2：课题研究和设计中的关键技术是什么？答：关键技术是二叉树的建立，以及栈结构、队列的算法实现问题3：课题的主要功能和模块有哪些？答：1）主要功能：根据数据建立二叉树，实现二叉树的中序、前序、后序遍历2）模块：栈的应用，队列结构的应用，二叉树的操作问题4：课题在实现过程中遇到的主要难点有哪些？答：遍历二叉树过程中栈结构以及队列的使用问题5：课题中未能实现的功能有哪些？答：以树形结构输出完全二叉树 记录人：寇海洲 2012 年 12 月 28日目录1需求分析51.1二叉树与树结构51.2面向对象的程

4、序设计51.3二叉树遍历的应用51.4软件运行环境：visual c+ 6.0版本52概要设计62.1 总体功能结构62.2数据结构部分设计62.2.1结点结构62.2.2 二叉树结构73详细设计123.1建立二叉树123.1.1功能描述123.1.2算法原理123.1.3 具体程序123.2 前序遍历133.2.1 功能原理133.2.2 算法原理133.2.3 具体程序133.3 中序遍历143.3.1 功能原理143.3.2 算法原理143.3.3 具体程序143.4 后序遍历153.4.1功能原理153.4.2 算法原理153.4.3 具体程序163.5层次序非递归遍历173.5.1

5、功能原理173.5.2 算法原理173.5.3 具体程序173.6 栈结构183.6.1 功能原理183.6.2算法原理183.6.3 具体程序183.7 队列结构193.7.1 功能原理193.7.2 算法原理193.7.3 具体程序194调试与操作说明20致 谢23参考文献24附录：251需求分析1.1二叉树与树结构树结构的是建立在数据逻辑结构基础上的数据结构类型，二叉树则是树结构中最常见和使用最多的类型。通过对二叉树的操作，可以实现多种数据操作，如排序、查找等。一个好的二叉树遍历算法应包含以下功能：1）以递归和非递归方法建立二叉树或完全二叉树；2）实现二叉树的前序遍历、中序遍历、后序遍历

6、；3）每种遍历算法皆以递归和非递归方法实现；4）在具体实现时应用其他数据结构类型对数据进行操作，如：栈，队列，数组。1.2面向对象的程序设计在面向对象的程序设计中，模板的使用很普遍，因此，如何在程序设计中使用模板使得方法的实现与定义分开，程序模块化，既方便了程序设计者，又为程序的后期维护带来便利。1.3二叉树遍历的应用当数据以数组或文档形式存储在内存时，其数据之间虽有逻辑联系，却过于分散，因此，建立二叉树以存储数据并且遍历该二叉树，可以从逻辑上理顺数据之间的关系，使得原本分数的数据排列的有序且可靠。一个好的二叉树应用算法其空间复杂度与时间复杂度必然最低，这样给程序带来时间和空间上的极大优化。1

7、.4软件运行环境：visual c+ 6.0版本2概要设计2.1 总体功能结构二叉树的遍历，主要包含以下功能：1）建立二叉树：递归方法、非递归方法2）中序遍历：递归方法、非递归方法3）前序遍历：递归方法、非递归方法4）后序遍历：递归方法、非递归方法5）栈结构使用：遍历时输入临时变量以保存6）队列结构使用：完全二叉树遍历时用以存储数据2.2数据结构部分设计2.2.1结点结构 二叉树结点结构中包数据域（data），指针域（*leftchild，*rightchild）。结点结构的代码如下：struct bintreenode/树结点t data;bintreenode<t> *left

8、child;bintreenode<t> *rightchild;bintreenode():leftchild(null), rightchild(null)bintreenode(t x, bintreenode<t> *l = null, bintreenode<t> *r = null):leftchild(l), rightchild(r)data = x; 栈结构结点包含数据域（data），指针域（*link），实现代码如下：struct stacknode/栈结点t data;stacknode<t> *link;stacknode

9、(t d = 0, stacknode<t> *next = null):link(next),data(d);队列结构结点包含数据域（data），指针域（*link），实现代码如下：struct linknodet data;linknode<t> *link;linknode(linknode<t> *ptr=null)link = ptr;linknode(const t &item, linknode<t> *ptr = null)data = item;link = ptr;2.2.2 二叉树结构 二叉树包含了递归、非递归建树过

10、程，递归、非递归的前序遍历、中序遍历、后续遍历过程。二叉树的类定义包含各种操作，实现代码如下：template <typename t>class binarytree/二叉树类定义public:binarytree():root(null)binarytree(t value):root(null)refvalue = value;binarytree(binarytree<t> &s)if (this != &s)root=copy(s.root);binarytree()destroy(root);bintreenode<t> *par

11、ent(bintreenode <t> *t)return (root = null | root = t)?null:parent(root, t);bintreenode<t> *leftchild(bintreenode<t> *t)return (t != null)?t->leftchild:null;bintreenode<t> *rightchild(bintreenode<t> *t)return (t != null)?t->rightchild:null;void preorder(void (*vis

12、it)(bintreenode<t> *t)preorder(root, visit);void inorder(void (*visit)(bintreenode<t> *t)inorder (root, visit);void postorder(void (*visit)(bintreenode<t> *t)postorder(root, visit);void createcompbintree(t *cbt, int num)/建立完全二叉树createcompbintree(cbt, num, 0, root);void levelorder(v

13、oid (*visit)(bintreenode<t> *t);/层次序遍历void preorder1(void (*visit) (bintreenode<t> *t);/非递归前序遍历void inorder1(void (*visit) (bintreenode<t> *t);/非递归中序遍历void postorder1(void (*visit) (bintreenode<t> *t);/非递归后序遍历friend istream& operator >> (istream &in, binarytree&

14、lt;t> &tree)/输入二叉树tree.createbintree(in, tree.root);return in;栈结构的定义中，包含了对数据的入栈、出栈、清空等基本操作，实现代码如下template <typename t>class linkedstackprivate:stacknode<t> *top;public:linkedstack():top(null)/无头结点linkedstack()makeempty();void push(const t &x);bool pop(t &x);bool isempty()c

15、onstreturn top=null;bool isfull()constreturn false;void makeempty();friend ostream& operator << (ostream &os, linkedstack<t> &s)os<<"stack size: "<<s.getsize()<<endl;stacknode<t> *p=s.top;int i=0;while (p)os<<+i<<": "<

16、;<p->data<<endl;p=p->link;return os;template <typename t>void linkedstack<t>:makeempty()stacknode<t> *p;while (top)p=top;top=top->link;delete p;队列的类定义，实现了对数据的入队、出队操作，实现代码如下：template <typename t>class linkedqueue/无头结点public:linkedqueue()rear = null;front = nu

17、ll;linkedqueue()makeempty();bool enqueue(const t &x);bool dequeue(t &x);void makeempty();bool isempty()constreturn front = null;friend ostream& operator << (ostream &os, linkedqueue<t> &q)linknode<t> *p = q.front;int i = 0;while (p)os << "#" <

18、< +i << ": " << p->data << endl;p = p->link;os << "queue size: " << q.getsize() << endl;return os;void output();protected:linknode<t> *front, *rear;3详细设计3.1建立二叉树 3.1.1功能描述 二叉树是程序的核心，如何合理的建立至关重要。本实例中使用递归和非递归方法分别建立二叉树，二叉树的数据来源于程序开始

19、时建立的数组。建立后的二叉树保存，并且留作之后的遍历使用。3.1.2算法原理 本实例使用的是完全二叉树，首先建立头结点，并且保存数据，然后根据递归方法，分别建立其左右孩子结点，且左右孩子结点的指针域指向空。3.1.3 具体程序以递归方式建立二叉树，每次建立一个结点后，将其左右孩子指针域置空，成为叶子结点。具体实现代码如下：template <typename t>void binarytree<t>:createbintree(istream &in, bintreenode<t> *& subtree)t item;if (in >&

20、gt; item)if (item != refvalue)subtree = new bintreenode<t>(item);/create rootassert(subtree);createbintree(in, subtree->leftchild);/ create left child treecreatebintree(in, subtree->rightchild);/ create reght child treeelsesubtree = null;/建立完全二叉树template<typename t>void binarytree&

21、lt;t>:createcompbintree(t *cbt, int num, int rt, bintreenode<t> *& subtree)if (rt >= num)subtree = null;elsesubtree = new bintreenode<t>(cbtrt);createcompbintree(cbt, num, 2*rt+1, subtree->leftchild);createcompbintree(cbt, num, 2*rt+2, subtree->rightchild);3.2 前序遍历3.2.1 功

22、能原理 通过前序遍历，将二叉树中的数据按照前序遍历的结果输出，达到前序便利的目的，方便数据的使用。3.2.2 算法原理前序遍历使用了递归与非递归两种方法，在程序头文件中定义了两个函数分别实现其功能。递归时，输出第一个结点数据时，找到数据，然后找到其后面的数据，然后依次递归输出。非递归时，使用栈和队列结构，将部分数据保存在栈或队列中，等待将数据放到合适位置。3.2.3 具体程序1）递归算法实现：template <typename t>void binarytree<t>:preorder(bintreenode<t>* subtree, void (*vis

23、it)(bintreenode<t> *t)if (subtree != null)visit(subtree);preorder(subtree->leftchild, visit);preorder(subtree->rightchild, visit);2）非递归算法实现：template <typename t>void binarytree<t>:preorder1(void (*visit) (bintreenode<t> *t) ) linkedstack<bintreenode<t>*> s;b

24、intreenode<t> *p = root; s.push (null);while (p!=null) visit(p); /访问结点if (p->rightchild != null)s.push (p->rightchild); /预留右指针在栈中if (p->leftchild != null) p=p->leftchild;/进左子树else s.pop(p);/左子树为空，由堆栈弹出3.3 中序遍历3.3.1 功能原理 通过中序遍历，将二叉树中的数据按照中序序遍历的结果输出，达到中序遍历的目的，实现数据的最优，方便数据的使用。3.3.2 算法

25、原理中序遍历使用了递归与非递归两种方法，在程序头文件中定义了两个函数分别实现其功能。递归时，输出第一个结点数据时，找到数据，然后依次找到其后面的数据，然后依次递归输出。非递归时，使用栈和队列结构，将部分数据保存在栈与队列中，等待将数据放到合适位置。3.3.3 具体程序1）递归算法实现：template <typename t>void binarytree<t>:inorder(bintreenode<t> *subtree, void (*visit)(bintreenode<t> *t)if (subtree != null)inorder(

26、subtree->leftchild, visit); visit(subtree);inorder(subtree->rightchild, visit);2）非递归算法实现：template <typename t> void binarytree<t>:inorder1(void (*visit) (bintreenode<t> *t) /非递归中序遍历 linkedstack<bintreenode<t>*> s; bintreenode<t> *p = root; while(p!=null | !s

27、.isempty ()while (p!= null) /遍历指针向左下移动s.push (p); /该子树沿途结点进栈p=p->leftchild;if (!s.isempty() /栈不空时退栈s.pop(p);visit (p);/退栈, 访问p=p->rightchild;/遍历指针进到右子女3.4 后序遍历3.4.1功能原理 通过后序遍历，将二叉树中的数据按照后序遍历的结果输出，达到后序遍历的目的，实现数据的最优，方便数据的使用。3.4.2 算法原理后序遍历使用了递归与非递归两种方法，在程序头文件中定义了两个函数分别实现其功能。递归时，输出第一个结点数据时，找到数据，然后

28、依次找到其后面的数据，然后依次递归输出。非递归时，使用栈和队列结构，将部分数据保存在栈与队列中，等待将数据放到合适位置。3.4.3 具体程序1）递归算法实现：template <typename t>void binarytree<t>:postorder(bintreenode<t> *subtree, void (*visit)(bintreenode<t> *t)if (subtree != null )postorder(subtree->leftchild, visit);postorder(subtree->rightch

29、ild, visit);visit (subtree);2）非递归算法实现：template <typename t>void binarytree<t>:postorder1(void (*visit) (bintreenode<t> *t)/非递归后序遍历linkedstack<stknode<t> > s;stknode<t> w; bintreenode<t> *p=root; /p是遍历指针do while (p != null) w.ptr = p;w.tag = stknode<t>:

30、l;/枚举类型定义在struct stknode中，如定义为全局性就简单了s.push (w); p = p->leftchild; int continue1 = 1; while (continue1 && !s.isempty () s.pop (w); p = w.ptr; switch (w.tag) /判断栈顶的tag标记 case stknode<t>:l: w.tag = stknode<t>:r; s.push (w); continue1 = 0; p = p->rightchild; break; case stknod

31、e<t>:r: visit (p); break; while (!s.isempty();/继续遍历其他结点 cout << endl;3.5层次序非递归遍历3.5.1 功能原理 层次序非递归遍历，依据的是递归原理，每次遍历一个结点后，同时让其左右孩子入队，以便达到层次序的目的。3.5.2 算法原理每次遍历完一个结点后，检查该结点是否为叶子结点，如果是叶子结点则继续下一结点的遍历，否则其左右孩子入队，继续遍历。3.5.3 具体程序template <typename t>void binarytree<t>:levelorder (void (

32、*visit) (bintreenode<t> *t) /层次序遍历 if (root = null) return; linkedqueue<bintreenode<t> *> q; bintreenode<t> *p=root; visit(p); q.enqueue(p); while (!q.isempty () q.dequeue (p); if (p->leftchild != null) visit (p->leftchild); q.enqueue (p->leftchild); if (p->rightc

33、hild != null) visit (p->rightchild); q.enqueue(p->rightchild); 3.6 栈结构3.6.1 功能原理 运用栈结构，在非递归算法中，未输出的数据暂时存入栈中，依据先进后出原则，方便了二叉树的遍历。3.6.2算法原理二叉树的结点信息，保存在栈中。第一个入栈的数据元素保存在栈底，后进栈的在上方，现出栈。3.6.3 具体程序template <typename t>void linkedstack<t>:push(const t &x)top = new stacknode<t>(x,

34、top);template <typename t>bool linkedstack<t>:pop(t &x)if (isempty()return false;stacknode<t> *p = top;top=top->link;x=p->data;delete p;return true;3.7 队列结构3.7.1 功能原理 运用队列结构，在层次序遍历算法中，未输出的数据暂时存入队列中，依据先进先出原则，方便了二叉树的遍历。3.7.2 算法原理层次序遍历二叉树信息时，二叉树的结点信息保存在队列中。第一个入队的数据元素保存队首，后入队

35、的元素依次连接上，先入队的先出队。3.7.3 具体程序template <typename t>void linkedqueue<t>:makeempty()linknode<t> *p;while (front)p = front;front = front->link;delete p;template <typename t>bool linkedqueue<t>:enqueue(const t &x)if (!front)front = rear = new linknode<t>(x);if (!f

36、ront)return false;elserear->link = new linknode<t>(x);if (!(rear->link)return false;rear = rear->link;return true;template <typename t>bool linkedqueue<t>:dequeue(t &x)if (isempty()return false;linknode<t> *p = front;x = front->data;front = front->link;dele

37、te p;return true;template <typename t>void linkedqueue<t>:output()linknode<t> *p = front; int i = 1;while (i <= getsize()cout << p->data << " "<<endl;p = p->link; i+;4调试与操作说明操作说明：当程序运行后，会在控制台提示一下文字：“从数组数据建立完全二叉树:”，“ 输入二叉树的元素总个数:”，然后从键盘输入二叉树元素个数，

38、紧接着系统会自动运行，得到各种遍历结果。运行截图：完全二叉树32个元素时的运行截图总结这次的课程设计我选择了二叉树的遍历，因为树结构是数据结构课程的典型内容，而且综合使用了多种逻辑结构，具有代表性，可以锻炼个人编程能力。在刚开始选题后，我感觉无从下手，一是因为没有实践经验，二是因为对数据结构课程的内容没有把握到位，然后在参考一些专业书籍并且学习了之前其他人的课程设计，才逐渐可以上手去自己做。在做了一小段后我发现如果不使用数组来建立二叉树是很麻烦的一件事，每个结点的信息都靠键盘输入是不合理的，于是运用了数组这一数据类型。在之后的递归算法中，我遇到的最大困难是如何实现递归，为此我参考了一本专业书籍

39、，学会了如何正确使用递归方法，这也让我感觉到学习与应用是不可分开的。对于非递归算法，我使用了栈结构和队列结构，分别用于前序遍历、中序、后序遍历、非递归层次序遍历方法中。使用栈和队列的过程中，我在实践中又学习了栈和队列的一些知识，提高了各种逻辑结构之间的综合运用能力。在后期测试阶段，我参考了许多课程设计案例，他们都运用了switch（）语句，这样虽然看着有条理，却不适合用在二叉树的遍历上，因为遍历结果显而易见并不十分复杂，没有必要使程序复杂化，因此我采用的是程序运行输出模式。总体来说，在本次课程设计中，我深刻体会了再面向对象程序设计中数据结构的实现方法，既学到了专业知识，也体会到“温故知新”的乐

40、趣，因此如果还有课程设计我还会积极参加，在实践中锻炼自己的能力水平。致谢对我来说这次课程设计的机会来之不易，首先我的父母辛苦工作，用他们赚到的血汗钱供我读书，让我有机会接受高等教育。其次，我的课程设计指导老师寇老师，冒着严寒每天早早地到机房为我指导、调试程序，从没有一句怨言。再者，我的数据结构授课教师周教授，从一开始接触这门课就不辞辛劳的给我传授知识，教我学的立足社会的资本。对你们，我想发自内心的说一句：谢谢你们，辛苦了！参考文献（1）数据结构（用面向对象方法与c+语言描述）殷人昆 清华大学出版社（2）深入体验c+项目开发 管西京 清华大学出版社（3）c+程序员教程(美)deitel.p.j.

41、,(美)deitel,h.m.著北京电子工业出版社附录：程序源代码：/mian（）主函数中：#include "binarytree.h"#include <iostream>#include <fstream>#include <iomanip>using namespace std;void visit(bintreenode<int> *t)cout<<t->data<<" "void main()binarytree<int> bintree(0);cout

42、 << "从数组数据建立完全二叉树:n"cout << "输入二叉树的元素总个数: "long num;cin >> num;int *cbt = new intnum;cout << "n数组中数据为:n"for (int i = 0; i < num; i+)cbti = i+1;cout << setw(4) << i+1;cout << endl;binarytree<int> bintree1;bintree1.create

43、compbintree(cbt, num);cout << "n完全二叉树前序遍历结果:n"bintree1.preorder(visit);cout << "nn完全二叉树中序遍历结果:n"bintree1.inorder(visit);cout << "nn完全二叉树后序遍历结果:n"bintree1.postorder(visit);cout << "n完全二叉树非递归前序遍历结果:n"bintree1.preorder1(visit);cout <<

44、; "nn完全二叉树非递归中序遍历结果:n"bintree1.inorder1(visit);cout << "nn完全二叉树非递归后序遍历结果:n"bintree1.postorder1(visit);cout << "n完全二叉树层次序遍历结果:n"bintree1.levelorder(visit);cout<<endl;delete cbt;/包含在头文件binarytree.h中#include <string>#include <cassert>#include

45、<iostream>using namespace std;#include"linkedstack.h"#include"linkedqueue.h"template <typename t>struct bintreenode/树结点t data;bintreenode<t> *leftchild;bintreenode<t> *rightchild;bintreenode():leftchild(null), rightchild(null)bintreenode(t x, bintreenode&l

46、t;t> *l = null, bintreenode<t> *r = null):leftchild(l), rightchild(r)data = x;template <typename t>class binarytree/二叉树类定义public:binarytree():root(null)binarytree(t value):root(null)refvalue = value;binarytree(binarytree<t> &s)if (this != &s)root=copy(s.root);binarytree(

47、)bintreenode<t> *parent(bintreenode <t> *t)return (root = null | root = t)?null:parent(root, t);bintreenode<t> *leftchild(bintreenode<t> *t)return (t != null)?t->leftchild:null;bintreenode<t> *rightchild(bintreenode<t> *t)return (t != null)?t->rightchild:nul

48、l;void preorder(void (*visit)(bintreenode<t> *t)preorder(root, visit);void inorder(void (*visit)(bintreenode<t> *t)inorder (root, visit);void postorder(void (*visit)(bintreenode<t> *t)postorder(root, visit);void createcompbintree(t *cbt, int num)/建立完全二叉树createcompbintree(cbt, num,

49、0, root);void levelorder(void (*visit)(bintreenode<t> *t);/层次序遍历void preorder1(void (*visit) (bintreenode<t> *t);/非递归前序遍历void inorder1(void (*visit) (bintreenode<t> *t);/非递归中序遍历void postorder1(void (*visit) (bintreenode<t> *t);/非递归后序遍历friend istream& operator >> (is

50、tream &in, binarytree<t> &tree)/输入二叉树tree.createbintree(in, tree.root);return in;protected:bintreenode<t> *root;/二叉树的根指针t refvalue;/数据输入停止标志void createbintree(istream &in, bintreenode<t> *& subtree);/递归建立二叉树void createcompbintree(t *cbt, int num, int rt, bintreenode

51、<t> *& subtree);/建立完全二叉树bintreenode<t> *copy(bintreenode<t> *r);/复制二叉树rvoid traverse(bintreenode<t> *subtree, ostream &out);/遍历输出void preorder(bintreenode<t> *subtree, void (*visit)(bintreenode<t> *t);/前序遍历void inorder(bintreenode<t> *subtree, void (

52、*visit)(bintreenode<t> *t);/中序遍历void postorder(bintreenode<t> *subtree, void (*visit)(bintreenode<t> *t);/后序遍历;template <typename t>void binarytree<t>:createbintree(istream &in, bintreenode<t> *& subtree)/私有函数: 以递归方式建立二叉树。t item;if (in >> item)if (it

53、em != refvalue)subtree = new bintreenode<t>(item);/create rootassert(subtree);createbintree(in, subtree->leftchild);/ create left child treecreatebintree(in, subtree->rightchild);/ create reght child treeelsesubtree = null;template<typename t>void binarytree<t>:createcompbint

54、ree(t *cbt, int num, int rt, bintreenode<t> *& subtree)/建立完全二叉树if (rt >= num)subtree = null;elsesubtree = new bintreenode<t>(cbtrt);createcompbintree(cbt, num, 2*rt+1, subtree->leftchild);createcompbintree(cbt, num, 2*rt+2, subtree->rightchild);template<typename t>bint

55、reenode<t> *binarytree<t>:copy(bintreenode<t> *r) /递归复制二叉树 if (!r)return null; bintreenode<t> *p=new bintreenode<t>(r->data); p->leftchild = copy(r->leftchild); p->rightchild = copy(r->rightchild); return p;template <typename t>void binarytree<t&

56、gt;:traverse(bintreenode<t> *subtree, ostream &out)/前序遍历输出结点数据if (subtree)out << subtree->data << ' 'traverse(subtree->leftchild, out);traverse(subtree->rightchild, out);template <typename t>void binarytree<t>:preorder(bintreenode<t>* subtree, void (*visit)(bintreenode<t> *t)/递归前序遍历if (subtree != null)visit(subtree);preorde