数据结构课程设计1

1、摘要现代社会中广泛地存在着具有层次特征或是具有分支关系的对象，而对于解决这些复杂繁琐的数据，就需要我们用更简化、更直观的去表达出来，以便达到简单易懂的目的。一般的线性结构难以简单明了地实现此类操作，如操作系统的文件构成、人工智能和算法分析的模型表示以及数据库系统的信息组织形式等，用线性结构难以把其中的逻辑关系表达出来，必须借助于数和图这样的非线性结构，因此在以模拟客观世界问题，解决客观世界问题为主要任务的计算机领域中树型结构是信息的一种重要组织形式，树有着广泛应用。在树型结构的应用中又以二叉树最为常用。二叉树是一种非常重要的非线性结构，所描述的数据有明显的层次关系，其中的每个元素只有一个前驱。

2、二叉树是最为常用的数据结构，有着非常广泛的运用。二叉树的遍历方式有三种：先序遍历、中序遍历和后序遍历。先序遍历的顺序为：先访问根结点，先序遍历左子树，先序遍历右子树（根左右）；中序遍历顺序为：中序遍历左子树，访问根结点，中序遍历右子树（左根右）；后序遍历顺序为：后序遍历左子树，后序遍历右子树，访问根结点（左右根）。由先序遍历和中序遍历，由中序遍历和后序遍历序列可以唯一确定一棵二叉树。该课设是对二叉树的各种功能的实现的编写，理解二叉树各种性质，掌握三种遍历二叉树的实现顺序和过程。关键字：二叉树、遍历二叉树、递归、Microsoft Visual C+软件1 问题概述1.1 问题分析所谓遍历是指沿

3、着某条搜索路线，一次对树中每个结点均做一次且仅做一次访问。遍历是二叉树上最重要的运算之一，是二叉树上进行其他运算的基础。二叉树的遍历是通过编写程序来实现二叉树的先序、中序和后序遍历，统计二叉树的结点个数，求二叉树的深度和销毁二叉树。1.2 可行性分析 此程序主要是根据给定二叉树的先序遍历结果，构造出二叉树并输出按中，后序遍历的结果，以及求二叉树的叶子个数等。其中二叉树的结点用字符表示。 1.先创建二叉树：按先序次序输入，构造二叉链表表示的二叉树。 2.设计算法：先序遍历、中序遍历、后序遍历。基于二叉树的递归定义，得到遍历二叉树的操作定义。(1)先序遍历二叉树的操作定义： 若二叉树为空，则空操作

4、；否则 .访问根结点；.先序遍历左子数；.先序遍历右子数。 (2)中序遍历二叉树的操作定义： 若二叉树为空，则空操作；否则 .中序遍历左子树；.访问根结点；.中序遍历右子数。 (3)后序遍历二叉树的操作定义： 若二叉树为空，则空操作；否则 .后序遍历左子数； .后序遍历右子数； .访问根结点。3.再加入求二叉树的深度，叶子节点个数及二叉树的销毁等算法。4.设计main()函数调用以上步骤实现相关功能1.3 系统流程图系统的流程图如图1.1所示。图1.1 系统流程图系统二叉链表模拟图如图1.2所示。图1.2 二叉链表图2 系统设计2.1 逻辑设计2.1.1. 二叉树结点数据类型定义templat

5、e <typename T> struct BiNode  BiNode<T>*rchild,*lchild;/指向左孩子的指针T data;/结点数据信息 2.1.2. 二叉树数据类型定义template <typename T> class BiTree  template <typename T> friend ostream & op

6、erator <<(ostream &os ,BiTree<T> &bt)  public: BiTree();/无参构造函数 BiTree(int m);/有参空构造函数 BiTree(T ary,int num,T none);/有参构造函数  BiTree();/析构函数 void preorder();/递归前序遍历  void inorder();/递归中序

7、遍历  void postorder();/递归后续遍历 void levelorder();/层序遍历 int  count();/计算二叉树的结点数  void display(ostream &os);/打印二叉树，有层次  void LevelNum();/计算每一层结点数  void PreOrder();/非递归前序遍历  void PostOrder();/非递归后

8、序遍历  void creat();/创建二叉树 protected: /以下函数供上面函数调用  /对应相同功能 Voidcreat(BiNode<T>*&root);/创建  void release(BiNode<T>* &root);/删除 BiNode<T> * Build(T ary,int num,T none,int idx);/用数组创建

9、二叉树  void PreOrder(BiNode<T>* root);/前序遍历  void PostOrder(BiNode<T>* root);/后续遍历  void LevelNum(BiNode<T>* root);/层序遍历  void preorder(BiNode<T>* root);/递归前序遍历  void inorder(BiNode&l

10、t;T>* root);/递归中序遍历  void postorder(BiNode<T>* root);/递归后续遍历  void levelorder(BiNode<T>*root);/层序遍历  int count(BiNode<T>* root);/计算结点数   void display(ostream& os,BiNode<T>* root,i

11、nt dep);/打印 static bool leastCommanAncestor(BiNode<T> *root, T va, T vb, BiNode<T>                       private:BiNode<

12、T> *rootptr; 2.2 详细设计本系统的基本功能有：建立二叉树、使用递归算法实现三种遍历、统计二叉树中结点的个数、输出叶子结点的个数、二叉树的深度及销毁操作。各模块的程序代码如下。（1）二叉树的创建：template <class T>void createBinTree(BTNode<T> * &root ) BTNode<T>* p = root; BTNode<T>* k; T nodeValue ; cin>>nodeValue; if(nodeValue=-1) root=NULL

13、; else root=new BTNode<T>(); root->data = nodeValue; createBinTree(root->Lchild); createBinTree(root->Rchild); （2）三种遍历二叉树先序遍历二叉树：template <class T>void preOrder( BTNode<T> * & p) if(p) cout<<p->data<<" " preOrder(p->Lchild); preOrder(p->R

14、child); 中序遍历二叉树：template <class T>void inOrder(BTNode<T> * & p) if(p) inOrder(p->Lchild); cout<<p->data<<" " inOrder(p->Rchild); 后序遍历二叉树：template <class T>void levelOrder(BTNode<T> *& p) if(p) levelOrder(p->Lchild); levelOrder(p->R

15、child); cout<<p->data<<" " 统计二叉树中结点的个数：template<class T>int countNode(BTNode<T> * & p) if(p = NULL) return 0; return 1+countNode(p->Lchild)+countNode(p->Rchild);二叉树的深度：template<class T>int depth(BTNode<T> *& p) if(p = NULL) return -1; in

16、t h1 = depth(p->Lchild); int h2 = depth(p->Rchild); if(h1>h2)return (h1+1); return h2+1;二叉树的销毁操作：template<class T>BTNode<T>* destroy(BTNode<T>* p) /消毁函数，用来消毁二叉树中的各个结点 if(p) return destroy(p->Lchild); return destroy(p->Rchild); delete p; 2.3 源程序代码#include <iostream

17、>using namespace std;/*/二叉树结点类的定义template<class T>struct BTNodeT data; BTNode <T> * Lchild,*Rchild; BTNode(T nodeValue = T(),BTNode<T>* leftNode = NULL,BTNode<T>* rightNode = NULL ) :data(nodeValue),Lchild(leftNode),Rchild(rightNode) /可选择参数的默认构造函数;/*/二叉树的建立template <cla

18、ss T>void createBinTree(BTNode<T> * &root ) BTNode<T>* p = root; BTNode<T>* k; T nodeValue ; cin>>nodeValue; if(nodeValue=-1) root=NULL; else root=new BTNode<T>(); root->data = nodeValue; createBinTree(root->Lchild); createBinTree(root->Rchild); /*/二叉树的先

19、序遍历template <class T>void preOrder( BTNode<T> * & p) if(p) cout<<p->data<<" " preOrder(p->Lchild); preOrder(p->Rchild); /*/二叉树的中序遍历template <class T>void inOrder(BTNode<T> * & p) if(p) inOrder(p->Lchild); cout<<p->data<<

20、;" " inOrder(p->Rchild); /*/二叉树的后序遍历template <class T>void levelOrder(BTNode<T> *& p) if(p) levelOrder(p->Lchild); levelOrder(p->Rchild); cout<<p->data<<" " /*/统计二叉树中结点的个数template<class T>int countNode(BTNode<T> * & p) if(p

21、= NULL) return 0; return 1+countNode(p->Lchild)+countNode(p->Rchild);/*/求二叉树的深度template<class T>int depth(BTNode<T> *& p) if(p = NULL) return -1; int h1 = depth(p->Lchild); int h2 = depth(p->Rchild); if(h1>h2)return (h1+1); return h2+1;/*/二叉树的消毁操作template<class T>

22、;BTNode<T>* destroy(BTNode<T>* p) /消毁函数，用来消毁二叉树中的各个结点 if(p) return destroy(p->Lchild); return destroy(p->Rchild); delete p; /*/主函数的设计 int main () BTNode<int> * rootNode = NULL; int choiced = 0; while(true) system("cls"); cout<<"nnn -主界面-nnn" cout<

23、<" 1、创建二叉树 2、先序遍历二叉树n" cout<<" 3、中序遍历二叉树 4、后序遍历二叉树n" cout<<" 5、统计结点总数 6、查看树深度 n" cout<<" 7、消毁二叉树 0、退出nn" cout<<" 请选择操作：" cin>>choiced; if(choiced = 0) return 0; else if(choiced = 1) system("cls"); cout<&l

24、t;"请输入每个结点，回车确认，并以-1结束：n" createBinTree(rootNode ); else if(choiced = 2) system("cls"); cout<<"先序遍历二叉树结果：n" preOrder(rootNode); cout<<endl; system("pause"); else if(choiced = 3) system("cls"); cout<<"中序遍历二叉树结果：n" inOrder(r

25、ootNode); cout<<endl; system("pause"); else if(choiced = 4) system("cls"); cout<<"后序遍历二叉树结果：n" levelOrder(rootNode); cout<<endl; system("pause"); else if(choiced = 5) system("cls"); int count = countNode(rootNode); cout<<"二叉树中结点总数为"<<count<<endl; system("pause"); else if(choiced = 6) system("cls"); int dep = depth(rootNode); cout<<"此二叉树的深度为"<<de