数据结构作业——二叉树_数据结构二叉树作业
数据结构作业——二叉树由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构二叉树作业”。
数据结构实验报告二
题目：
用先序递归过程监理二叉树（存储结构：二叉链表）
输入数据按先序遍历输入，当某节点左子树或者右子树为空时，输入‘*’号，如输入abc**d**e**时，得到的二叉树为：
并用如下实力测试：
算法思路：
显然，建立一个二叉链表存储的二叉树，如果不考虑效率要求，考虑到程序的简介性，递归建立和递归遍历是一种很好的办法。
利用C++的类模板的方法实现建立，遍历，输出等二叉树操作。首先利用构造函数实现先序遍历建立二叉树，然后调用类模板中已经声明好的四种遍历函数，将遍历结果输出，检验建立好的二叉树是否为要求的二叉树。
初始化：利用构造函数建立二叉树。采用先序递归的调用方法，构造函数主体如下：
template BiTree::BiTree(){ this->root = Creat();//利用this指针调用creat函数 }
template BiNode* BiTree::Creat()//定义构造函数 { BiNode* root;T aa;cout>aa;if(aa==“*”)root = NULL;else{
root = new BiNode;
//生成一个结点 root->data=aa;
root->lchild = Creat();
//递归建立左子树
root->rchild = Creat();
//递归建立右子树
} return root;} 构造这样的函数，可以在输入时，按先序遍历顺序每次输入一个节点的数据，可以实现任意二叉树的构造。
为了检验构造的二叉树是否为预先设想的二叉树，需要遍历二叉树并进行输出。考虑到单一的输出并不能确定唯一的二叉树，因此对遍历二叉树的四种常用发方法，即先序遍历，中序遍历，后续遍历，层次遍历分别实现，通过遍历结果检验构造的二叉树是否为预先设计好的二叉树。
先序遍历：采用递归的方法建立。template voidBiTree::xianxu(BiNode *root){ if(root==NULL)return;//如果节点为空，则返回空 else{ coutdata
xianxu(root->lchild);//先序遍历树的左子树 xianxu(root->rchild);//先序遍历树的右子树
} 中序遍历：递归方法建立： template voidBiTree::zhongxu(BiNode *root){
if(root==NULL)return;
//如果节点为空，则返回空 else{ zhongxu(root->lchild);
//中序递归遍历root的左子树 coutdata
//访问根结点
zhongxu(root->rchild);
//中序递归遍历root的右子树
}
} 后序遍历：递归方法建立： template voidBiTree::houxu(BiNode *root){
if(root==NULL)
return;
//如果节点为空，返回空 else{ houxu(root->lchild);
//后序递归遍历root的左子树 houxu(root->rchild);
//后序递归遍历root的右子树 coutdata
//访问根节点
} } 层序遍历：采用非递归方法。利用队列的方法层序遍历二叉树。建立一个队列，在访问一个节点的时候，把它的左孩子和右孩子入队，并且将这个节点出队。当队列为空时，就完成了对二叉树的层序遍历。
template voidBiTree::cengxu(BiNode *root){ constintMaxSize = 100;int front = 0;int rear = 0;//利用队列的方法对树进行层序遍历 BiNode* Q[MaxSize];BiNode* q;if(root==NULL)return;// 如果节点为空，返回空 else{
Q[rear++] = root;// 若节点不为空，则该节点入队 while(front!= rear)
{
q = Q[front++];//只要队列不为空，则节点依次出队 coutdata
if(q->lchild!= NULL)
Q[rear++] = q->lchild;
if(q->rchild!= NULL)
Q[rear++] = q->rchild;// 同时，该节点的双子入队
} } } 函数主体部分：声明一个类中的对象，调用构造函数，建立二叉树，并输出四种遍历结果，检验输出结果。
int main(){
BiTreeshu;//声明类中一个对象，在构造了一颗树
BiNode* root = shu.Getroot();//获取指向根结点的指针
cout
程序结构：
主函数建立一个类模板定义构造函数，析构函数，以及成员函数声明类中的一个对象调用构造函数，构造一颗二叉树层序遍历二叉树后序遍历二叉树中序遍历二叉树前序遍历二叉树获取该二叉树的根节点将结果输出，人工检验 源代码：
#include using namespace std;
template struct BiNode
{
T data;
BiNode *lchild, *rchild;};
template cla BiTree
{ public: BiTree();
//构造函数，初始化一棵二叉树 ~BiTree(void);
//析构函数，释放二叉链表中各结点的存储空间
BiNode* Getroot();
//获得指向根结点的指针
void xianxu(BiNode *root);
//前序遍历二叉树
void zhongxu(BiNode *root);
//中序遍历二叉树
void houxu(BiNode *root);
//后序遍历二叉树
void cengxu(BiNode *root);
//层序遍历二叉树 private:
BiNode *root;
BiNode *Creat();
void Release(BiNode *root);
};template BiTree::BiTree(){ this->root = Creat();//利用this指针调用creat函数 }
template BiNode* BiTree::Creat()//定义构造函数 { BiNode* root;T aa;cout>aa;
if(aa==“*”)root = NULL;
else{
root = new BiNode;
//生成一个结点
root->data=aa;
root->lchild = Creat();
//递归建立左子树
root->rchild = Creat();
//递归建立右子树
}
return root;}
template BiTree::~BiTree(void){ Release(root);//析构函数，释放存储指针所需要的空间 }
template BiNode* BiTree::Getroot()//获取根节点所在指针的位置 { return root;}
template void BiTree::xianxu(BiNode *root){ if(root==NULL)return;//如果节点为空，则返回空
else{
coutdata
xianxu(root->lchild);//先序遍历树的左子树
xianxu(root->rchild);//先序遍历树的右子树
} }
template void BiTree::zhongxu(BiNode *root){
if(root==NULL)return;
//如果节点为空，则返回空
else{
zhongxu(root->lchild);
//中序递归遍历root的左子树
coutdata
//访问根结点
zhongxu(root->rchild);
//中序递归遍历root的右子树
} }
template void BiTree::houxu(BiNode *root){
if(root==NULL)
return;
//如果节点为空，返回空
else{
houxu(root->lchild);
//后序递归遍历root的左子树
houxu(root->rchild);
//后序递归遍历root的右子树
coutdata
//访问根节点
} }
template void BiTree::cengxu(BiNode *root){
const int MaxSize = 100;int front = 0;int rear = 0;//利用队列的方法对树进行层序遍历
BiNode* Q[MaxSize];
BiNode* q;if(root==NULL)return;// 如果节点为空，返回空
else{
Q[rear++] = root;// 若节点不为空，则该节点入队
while(front!= rear)
{
q = Q[front++];//只要队列不为空，则节点依次出队
coutdata
if(q->lchild!= NULL)
Q[rear++] = q->lchild;
if(q->rchild!= NULL)
Q[rear++] = q->rchild;// 同时，该节点的双子入队
} } }
template void BiTree::Release(BiNode* root)//析构函数，释放存储空间 {
if(root!= NULL){
Release(root->lchild);
//释放左子树
Release(root->rchild);
//释放右子树
delete root;
}
}
int main(){
BiTree shu;//声明类中一个对象，在构造了一颗树
BiNode* root = shu.Getroot();//获取指向根结点的指针
cout
cout
通过对结果的分析，发现输出结果与建立二叉树时的输入完全符合，说明程序的运行结果是正确的。
心得体会：
1)函数递归的方法可以在相当程度上使程序简洁，避免代码的冗长复杂。2)构造函数如果带参数，在声明对象的时候应该将实参指出来。但是本题中构造函数位递归调用，初始的根节点的数据值由键盘输入，因此无法在声明对象时引入实参。所以最后选择了无参但是引用了this指针的构造函数。可见，对于构造函数的含参调用应该小心谨慎。
3)编程时，要不停得检验自己的输入与输出，必要的时候需要人工进行计算，以保证程序的运行按照预先的设想。
