数据结构作业——叉树.doc

数据结构实验报告二 题目： 用先序递归过程监理二叉树（存储结构：二叉链表） 输入数据按先序遍历输入，当某节点左子树或者右子树为空时，输入‘*’号，如输入abc**d**e**时，得到的二叉树为： 并用如下实力测试： 算法思路： 显然，建立一个二叉链表存储的二叉树，如果不考虑效率要求，考虑到程序的简介性，递归建立和递归遍历是一种很好的办法。 利用C++的类模板的方法实现建立，遍历，输出等二叉树操作。首先利用构造函数实现先序遍历建立二叉树，然后调用类模板中已经声明好的四种遍历函数，将遍历结果输出，检验建立好的二叉树是否为要求的二叉树。 初始化：利用构造函数建立二叉树。采用先序递归的调用方法，构造函数主体如下： templateclass T BiTreeT::BiTree( ) { this-root = Creat( );//利用this指针调用creat函数 } template class T BiNodeT* BiTreeT::Creat()//定义构造函数 { BiNodeT* root; T aa; cout请按前序序列方式输入节点数据，每次输入一个endl; cinaa; if (aa==*) root = NULL; else{ root = new BiNodeT; //生成一个结点 root-data=aa; root-lchild = Creat(); //递归建立左子树 root-rchild = Creat(); //递归建立右子树 } return root; } 构造这样的函数，可以在输入时，按先序遍历顺序每次输入一个节点的数据，可以实现任意二叉树的构造。 为了检验构造的二叉树是否为预先设想的二叉树，需要遍历二叉树并进行输出。考虑到单一的输出并不能确定唯一的二叉树，因此对遍历二叉树的四种常用发方法，即先序遍历，中序遍历，后续遍历，层次遍历分别实现，通过遍历结果检验构造的二叉树是否为预先设计好的二叉树。 先序遍历：采用递归的方法建立。 templateclass T void BiTreeT::xianxu(BiNodeT *root) { if(root==NULL) return;//如果节点为空，则返回空 else{ coutroot-data ;//访问根节点 xianxu(root-lchild);//先序遍历树的左子树 xianxu(root-rchild);//先序遍历树的右子树 } 中序遍历：递归方法建立： template class T void BiTreeT::zhongxu (BiNodeT *root) { if (root==NULL) return; //如果节点为空，则返回空 else{ zhongxu (root-lchild); //中序递归遍历root的左子树 coutroot-data ; //访问根结点 zhongxu (root-rchild); //中序递归遍历root的右子树 } } 后序遍历：递归方法建立： template class T void BiTreeT::houxu(BiNodeT *root) { if (root==NULL) return; //如果节点为空，返回空 else{ houxu(root-lchild); //后序递归遍历root的左子树 houxu(root-rchild); //后序递归遍历root的右子树 coutroot-data ; //访问根节点 } } 层序遍历：采用非递归方法。利用队列的方法层序遍历二叉树。建立一个队列，在访问一个节点的时候，把它的左孩子和右孩子入队，并且将这个节点出队。当队列为空时，就完成了对二叉树的层序遍历。 template class T void BiTreeT::cengxu(BiNodeT *root) { const int MaxSize = 100; int front = 0; int rear = 0; //利用队列的方法对树进行层序遍历 BiNodeT* Q[MaxSize]; BiNodeT* q; if (root==NULL) return;// 如果节点为空，返回空 else{ Q[rear++] = root;// 若节点不为空