数据结构作业——二叉树.docx

数据结构作业——二叉树

第一篇：数据结构作业——二叉树数据结构实验报告二题目：用先序递归过程监理二叉树（存储结构：二叉链表）输入数据按先序遍历输入，当某节点左子树或者右子树为空时，输入‘*’号，如输入abc**d**e**时，得到的二叉树为：并用如下实力测试：算法思路：显然，建立一个二叉链表存储的二叉树，如果不考虑效率要求，考虑到程序的简介性，递归建立和递归遍历是一种很好的办法。利用C++的类模板的方法实现建立，遍历，输出等二叉树操作。首先利用构造函数实现先序遍历建立二叉树，然后调用类模板中已经声明好的四种遍历函数，将遍历结果输出，检验建立好的二叉树是否为要求的二叉树。初始化：利用构造函数建立二叉树。采用先序递归的调用方法，构造函数主体如下：templateBiTree::BiTree(){this->root=Creat();//利用this指针调用creat函数}templateBiNode*BiTree::Creat()//定义构造函数{BiNode*root;Taa;cout>aa;if(aa==“*”)root=NULL;else{root=newBiNode;//生成一个结点root->data=aa;root->lchild=Creat();//递归建立左子树root->rchild=Creat();//递归建立右子树}returnroot;}构造这样的函数，可以在输入时，按先序遍历顺序每次输入一个节点的数据，可以实现任意二叉树的构造。为了检验构造的二叉树是否为预先设想的二叉树，需要遍历二叉树并进行输出。考虑到单一的输出并不能确定唯一的二叉树，因此对遍历二叉树的四种常用发方法，即先序遍历，中序遍历，后续遍历，层次遍历分别实现，通过遍历结果检验构造的二叉树是否为预先设计好的二叉树。先序遍历：采用递归的方法建立。templatevoidBiTree::xianxu(BiNode*root){if(root==NULL)return;//如果节点为空，则返回空else{coutdataxianxu(root->lchild);//先序遍历树的左子树xianxu(root->rchild);//先序遍历树的右子树}中序遍历：递归方法建立：templatevoidBiTree::zhongxu(BiNode*root){if(root==NULL)return;//如果节点为空，则返回空else{zhongxu(root->lchild);//中序递归遍历root的左子树coutdata//访问根结点zhongxu(root->rchild);//中序递归遍历root的右子树}}后序遍历：递归方法建立：templatevoidBiTree::houxu(BiNode*root){if(root==NULL)return;//如果节点为空，返回空else{houxu(root->lchild);//后序递归遍历root的左子树houxu(root->rchild);//后序递归遍历root的右子树coutdata//访问根节点}}层序遍历：采用非递归方法。利用队列的方法层序遍历二叉树。建立一个队列，在访问一个节点的时候，把它的左孩子和右孩子入队，并且将这个节点出队。当队列为空时，就完成了对二叉树的层序遍历。templatevoidBiTree::cengxu(BiNode*root){constintMaxSize=100;intfront=0;intrear=0;//利用队列的方法对树进行层序遍历BiNode*Q[MaxSize];BiNode*q;if(root==NULL)return;//如果节点为空，返回空else{Q[rear++]=root;//若节点不为空，则该节点入队while(front!=rear){q=Q[front++];//只要队列不为空，则节点依次出队coutdataif(q->lchild!=NULL)Q[rear++]=q->lchild;if(q->rchild!=NULL)Q[rear++]=q->rchild;//同时，该节点的双子入队}}}函数主体部分：声明一个类中的对象，调用构造函数，建立二叉树，并输出四种遍历结果，检验输出结果。intmain(){BiTreeshu;//声明类中一个对象，在构造了一颗树BiNode*root=shu.Getroot();//获取指向根结点的指针cout程序结构：主函数建立一个类模板定义构造函数，析构函数，以及成员函数声明类中的一个对象调用构造函数，构造一颗二叉树层序遍历二叉树后序遍历二叉树中序遍历二叉树前序遍历二叉树获取该二叉树的根节点将结果输出，人工检验源代码：#includeusingnamespacestd;templatestructB