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

《数据结构课程设计二叉树的建立》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、《数据结构》课程设计题目二叉树的建立学生姓名指导教师学院信息学院专业班级信息与计算科学一班完成时间2014年01月05日目录第一章课程设计目的3第二章课程设计内容和要求32.1后序序列以及中序序列的输入32.2二叉树的建立32.3运行环境3第三章课程设计分析33.1二叉树的构造3第四章算法（数据结构）描述4第五章源代码5第六章运行结果分析8第七章结束语10第八章参考文献10第一章课程设计目的1、巩固和加深《数据结构》课程的基本知识，更好的将理论知识与实际相结合；2、熟悉并掌握C++语言知识；3、掌握

2、二叉树的遍历方法以及编程；4、提高编程能力与专业水平；第二章课程设计内容和要求2.1后序序列以及中序序列的输入根据任意一棵二叉树，分别输入其后序遍历（LRV）以及中序遍历（LVR）。两个遍历都遵循先左后右的法则，后序遍历第三次遇到结点时才访问，中序遍历第二次遇到结点就进行访问。2.2二叉树的建立根据后序遍历的定义，后序序列的最后一个一定是根。又根据中序序列，根将中序序列分为左子树和右子树，递归的对左子树以及右子树进行判断划分就能求出整棵树的结构，则建立起了一棵二叉树。前序遍历中第一次遇到节点就进行访

3、问。2.3运行环境该程序的运行环境为Windows7系统，MicrosoftVisualC++10.0版本。第三章课程设计分析3.1二叉树的构造为方便进行理解，我以一棵二叉树为例，其他二叉树的构造过程类似。对于以下二叉树，我进行了前序遍历、中序遍历、后序遍历如下：前序遍历：ABDGEHCFIJ中序遍历：GDBHEACIFJA后序遍历：GDHEBIJFCACBFEDJIHG二叉树（图1）根据上述给出的遍历，我们将中序以及后序遍历的结果输入，然后头文件中的createBinaryTree函数对中序以及后

4、序进行处理后序遍历的最后一个字母是A，则A一定是根，又根据中序遍历的定义，从A字母把中序划分为两个子列：（GDBHE）A（CIFJ），这样就可以得到对二叉树的第一次近似，然后取后序序列的倒数第二个字母C，它出现在右子树中，应该是右子树的根，它把中序（CIFJ）又划分为两个子序列：（）C（IFJ），这样可以得到对二叉树的第二次近似，将这个过程继续下去就能递归的构造出二叉树。第四章算法（数据结构）描述这是一个递归的过程，先在后序序列中找到相应的根，然后根据根将中序遍历分为左子树和右子树。再分别对左子树以

5、及右子树执行与上述过程一致的判断以及划分，最后将整颗树构造出来//(1-1)createBinaryTree利用后序序列和中序序列构造二叉树templateThreadNode*ThreadTree::createBinaryTree(T*LRV,T*LVR,intn){if(n==0)returnNULL;intk=0;while(LRV[n-1]!=LVR[k])k++;//在中序序列中寻找根ThreadNode*t=newThreadNode(LRV[n

6、-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个元素建立右子树returnt;};执行文件如下：首先进行后序序列以及中序序列的输入，然后构建出二叉树，接着输出前序序列进行验证，看是否程序准确运行。

7、voidmain(){ThreadTreeBT;cin>>BT;//输入后序序列、中序序列、建立二叉树、中序线索化cout<<"前序序列为";BT.PreOrder(visit);//前序输出cout<structThreadNode{intltag,rtag;//线索标志，非零为线索，ltag前驱，rtag后继ThreadNode*leftChild,*rightChild;Tdata;Thre

8、adNode(constTitem):data(item),leftChild(NULL),rightChild(NULL),ltag(0),rtag(0){}};templateclassThreadTree{protected:ThreadNode*root;voiddestroy(ThreadNode*&subTree);//p196删除使之为空树ThreadNode*createBinaryTree(T*VLR,T*LVR,i