数据结构课程设计二叉树的建立.doc

数据结构课程设计题 目 二叉树的建立 学生姓名 指导教师 学 院 信息学院 专业班级 信息与计算科学一班 完成时间 2014年01月05日 目录第一章 课程设计目的3第二章 课程设计内容和要求32.1后序序列以及中序序列的输入32.2 二叉树的建立32.3 运行环境3第三章 课程设计分析33.1二叉树的构造3第四章 算法（数据结构）描述4第五章 源代码5第六章 运行结果分析8第七章 结束语10第八章 参考文献10第一章 课程设计目的1、 巩固和加深数据结构课程的基本知识，更好的将理论知识与实际相结合；2、 熟悉并掌握C+语言知识；3、 掌握二叉树的遍历方法以及编程；4、 提高编程能力与专业水平；第2章 课程设计内容和要求2.1后序序列以及中序序列的输入根据任意一棵二叉树，分别输入其后序遍历（LRV）以及中序遍历（LVR）。两个遍历都遵循先左后右的法则，后序遍历第三次遇到结点时才访问，中序遍历第二次遇到结点就进行访问。2.2 二叉树的建立根据后序遍历的定义，后序序列的最后一个一定是根。又根据中序序列，根将中序序列分为左子树和右子树，递归的对左子树以及右子树进行判断划分就能求出整棵树的结构，则建立起了一棵二叉树。前序遍历中第一次遇到节点就进行访问。2.3 运行环境 该程序的运行环境为Windows 7系统，Microsoft Visual C+10.0版本。第3章 课程设计分析3.1二叉树的构造为方便进行理解，我以一棵二叉树为例，其他二叉树的构造过程类似。对于以下二叉树，我进行了前序遍历、中序遍历、后序遍历如下：前序遍历：ABDGEHCFIJ中序遍历：GDBHEACIFJA后序遍历：GDHEBIJFCA CBFEDJIHG 二叉树（图1）根据上述给出的遍历，我们将中序以及后序遍历的结果输入，然后头文件中的createBinaryTree函数对中序以及后序进行处理后序遍历的最后一个字母是A，则A一定是根，又根据中序遍历的定义，从A字母把中序划分为两个子列：（GDBHE）A（CIFJ），这样就可以得到对二叉树的第一次近似，然后取后序序列的倒数第二个字母C，它出现在右子树中，应该是右子树的根，它把中序（CIFJ）又划分为两个子序列：（）C（IFJ），这样可以得到对二叉树的第二次近似，将这个过程继续下去就能递归的构造出二叉树。第4章 算法（数据结构）描述这是一个递归的过程，先在后序序列中找到相应的根，然后根据根将中序遍历分为左子树和右子树。再分别对左子树以及右子树执行与上述过程一致的判断以及划分，最后将整颗树构造出来/(1-1)createBinaryTree利用后序序列和中序序列构造二叉树templateThreadNode* ThreadTree:createBinaryTree(T *LRV,T *LVR,int n)if(n=0)return NULL;int k=0;while(LRVn-1!=LVRk)k+; /在中序序列中寻找根ThreadNode*t=new ThreadNode(LRVn-1); /创建根结点t-leftChild=createBinaryTree(LRV,LVR,k);/从后序的LRV开始，对中序的0到k-1左子序列的k个元素地鬼建立左子树 t-rightChild=createBinaryTree(LRV+k,LVR+k+1,n-k-1);/从后序的LRV+k开始，对中序的k+1到n-1右子序列的n-k-1个元素建立右子树return t;执行文件如下：首先进行后序序列以及中序序列的输入，然后构建出二叉树，接着输出前序序列进行验证，看是否程序准确运行。void main()ThreadTree BT;cinBT; /输入后序序列、中序序列、建立二叉树、中序线索化cout前序序列为;BT.PreOrder(visit); /前序输出coutendl; 第五章 源代码Erchashu .h头文件：templatestruct ThreadNodeint ltag,rtag;/线索标志，非零为线索，ltag前驱，rtag后继ThreadNode *leftChild,*rightChild;T data;ThreadNode(const T item):data(item),leftChild(NULL),rightChild(NULL),ltag(0),rtag(0);templateclass ThreadTreeprotected:ThreadNode *root;void destroy(ThreadNode *&subTree);/p196删除使之为空树ThreadNode* createBinaryTree(T *VLR,T *LVR,int n);/利用前序序列和中序序列构造二叉树void createInThread(ThreadNode *current,ThreadNode *&pre);/中序遍历建立线索二叉树，递归p214public:ThreadTree():root(NULL)ThreadTree() if(root) destroy(root); /析构函数friend istream& operator(istream&in,ThreadTree& BT);/调用createBinaryTreevoid PreOrder(void(*visit)(ThreadNode*p);void createInThread();/建立中序线索二叉树，调用同名保护成员函数p214ThreadNode *First(ThreadNode *current);/找子树中序第一个结点p213ThreadNode *Next(ThreadNode *current);/找中序后继结点p213void InOrder(void(*vist)(ThreadNode *p);/中序遍历p214;/输入二叉树template/调用createBinaryTreeistream& operator(istream& in,ThreadTree& BT)if(BT.root!=NULL) BT.destroy(BT.root);/BT是空树或中序线索二叉树coutn;T *LRV=new Tn,*LVR=new Tn;cout输入二叉树的后序序列：;for(int i=0;iLRVi;cout输入二叉树的中序序列：;for(int i=0;iLVRi;BT.root=BT.createBinaryTree(LRV,LVR,n);/建立二叉树deleteLRV; deleteLVR;BT.createInThread();/建立线索二叉树return in; /(1-1)createBinaryTree利用后序序列和中序序列构造二叉树templateThreadNode* ThreadTree:createBinaryTree(T *LRV,T *LVR,int n)if(n=0)return NULL;int k=0;while(LRVn-1!=LVRk)k+; /在中序序列中寻找根ThreadNode*t=new ThreadNode(LRVn-1); /创建根结点t-leftChild=createBinaryTree(LRV,LVR,k);/从后序的LRV开始，对中序的0到k-1左子序列的k个元素地鬼建立左子树 t-rightChild=createBinaryTree(LRV+k,LVR+k+1,n-k-1);/从后序的LRV+k开始，对中序的k+1到n-1右子序列的n-k-1个元素建立右子树return t;/(1-2)destroy删除使之为空树P196templatevoid ThreadTree:destroy(ThreadNode*& subTree)if(subTree!=NULL)if(subTree-ltag=0) destroy(subTree-leftChild);if(subTree-rtag=0) destroy(subTree-rightChild);delete subTree; subTree=NULL;/(1-3)First找子树中序第一个结点函数实现p213templateThreadNode*ThreadTree:First(ThreadNode*current)ThreadNode*p=current;while(p-ltag=0)p=p-leftChild;return p;/(1-4)Next找中序后继结点函数实现p213templateThreadNode *ThreadTree:Next(ThreadNode *current)ThreadNode*p=current-rightChild;if(current-rtag=0)return First(p);else return p;/(1-5)PreOrder先序遍历函数实现p214templatevoid ThreadTree:PreOrder(void(*vist)(ThreadNode *p)ThreadNode*p=root;while(p!=NULL)visit(p);if(p-ltag=0) p=p-leftChild;else if(p-rtag=0) p=p-rightChild;elsewhile(p!=NULL & p-rtag=1)p=p-rightChild;if(p!=NULL) p=p-rightChild;/(1-6)createInThread建立线索二叉树(public)函数实现p214templatevoid ThreadTree :createInThread()ThreadNode*pre=NULL;if(root!=NULL)createInThread(root,pre);pre-rightChild=NULL;pre-rtag=1;/(1-7)createInThread建立线索二叉树(protected)函数实现p214 template void ThreadTree:createInThread(ThreadNode *current, ThreadNode *&pre) if(current=NULL)return; createInThread(current-leftChild,pre); if(current-leftChild=NULL) current-leftChild=pre;current-ltag=1; if(pre!=NULL & pre-rightChild=NULL) pre-rightChild=current;pre-rtag=1; pre=current; createInThread(current-rightChild,pre); ;执行文件：#includeusing namespace std;#includeErchashu .htemplatevoid visit(ThreadNode* p) coutdata; void main()ThreadTree BT;cinBT;/输入后序序列、中序序列、建立二叉树、中序线索化cout前序序列为;BT.PreOrder(visit);/前序输出coutendl;第6章 运行结果分析输入正确的图一的中序序列以及后序序列，则运行结果如下：如果输入结点多于结点数，无法输出前序序列，并且程序将报错！第七章 结束语课程设计是培养理论知识的运用，发现、提出、分析、解决问题。在这次课程设计的过程中我学会了数据结构解决问题的基本步骤，提出问题，进行抽象，数据结构，算法和程序。同时加