数据结构实验五
实验 五：树和二叉树的实验 2
一、实验目的
1、熟练理解树和二叉树的相关概念，掌握的存储结构和相关操作实现；
2、掌握树的顺序结构的实现；
3、学会运用树的知识解决实际问题
二、 实验内容
1、自己确定一个二叉树（树结点类型、数目和结构自定）利用链式存储结构方法存储。实 现树的构造，并完成：
1） 用前序遍历、中序遍历、后序遍历输出结点数据；
2） 以合理的格式，输出各个结点和双亲、孩子结点信息；
3） 输出所有的叶子结点信息； 2、试设计一个程序，将输入的字符串转化为对应的哈夫曼编码，然后再将这个哈夫曼编码 序列进行解码，也就是恢复原来的字符串序列。
（*） 三、实验步骤
1、依据实验内容，先确定具体的二叉树，并说明结点的数据类型；
2、设计具体的算法；
3、写出完整程序；
4、总结、运行结果和分析算法效率。
5、总体收获和不足，疑问等。
#include<iostream>
using namespace std;
struct Node
{
int data;
Node *lchild,*rchild;
};
class BiTree
{
public:
BiTree(){root=Creat(root);} //构造函数，建立一棵二叉树
~BiTree(){Release(root);} //析构函数，释放各结点的存储空间
void PreOrder(){PreOrder(root);} //前序遍历二叉树
void InOrder(){InOrder(root);} //中序遍历二叉树
void PostOrder(){PostOrder(root);} //后序遍历二叉树
void CPmessage(){CPmessage(root,NULL);}//打印结点的双亲和孩子信息函数
void Printleaf(){Printleaf(root);}//打印叶子结点信息函数
private:
Node *root; //指向根结点的头指针
Node *Creat(Node *bt); //构造函数调用
void Release(Node *bt); //析构函数调用
void PreOrder(Node *bt); //前序遍历
void InOrder(Node *bt); //中序遍历
void PostOrder(Node *bt); //后序遍历
void CPmessage(Node *bt,Node *p); //输出孩子双亲结点信息
void Printleaf(Node *bt); //输出叶子结点信息
};
Node *BiTree::Creat(Node *bt)
{
int n;
cin>>n;
if(n==0) return bt=NULL;
else{
bt=new Node; //生成一个新结点
bt->data=n;
bt->lchild=Creat(bt->lchild); //递归建立左子树
bt->rchild=Creat(bt->rchild); //递归建立右子树
}
return bt;
}
void BiTree::Release(Node *bt)
{
if(bt!=NULL)
{
Release(bt->lchild); //释放左子树
Release(bt->rchild); //释放右子树
delete bt;
}
}
void BiTree::PreOrder(Node *bt)
{
if(bt==NULL) return; //递归调用的结束条件
else{
cout<<bt->data<<" "; //访问根结点的数据域
PreOrder(bt->lchild); //前序递归遍历bt的左子树
PreOrder(bt->rchild); //前序递归遍历bt的右子树
}
}
void BiTree::InOrder(Node *bt)
{
if(bt==NULL) return; //递归调用的结束条件
else{
InOrder(bt->lchild); //中序递归遍历bt的左子树
cout<<bt->data<<" "; //访问根结点的数据域
InOrder(bt->rchild); //中序递归遍历bt的右子树
}
}
void BiTree::PostOrder(Node *bt)
{
if(bt==NULL) return; //递归调用的结束条件
else{
PostOrder(bt->lchild); //后序递归遍历bt的左子树
PostOrder(bt->rchild); //后序递归遍历bt的右子树
cout<<bt->data<<" "; //访问根结点的数据域
}
}
void BiTree::CPmessage(Node *bt,Node *p)
{
if(bt!=NULL)
{
cout<<"结点"<<bt->data<<" ";
if(bt->lchild!=NULL) //访问左孩子
cout<<"左孩子为："<<bt->lchild->data<<" ";
else
cout<<"无左孩子"<<" ";
if(bt->rchild!=NULL) //访问右孩子
cout<<"右孩子为："<<bt->rchild->data<<" ";
else
cout<<"无右孩子"<<" ";
if(p!=NULL) //访问双亲
cout<<"双亲为："<<p->data<<" ";
else
cout<<"无双亲"<<" ";
cout<<endl;
CPmessage(bt->lchild,bt);
CPmessage(bt->rchild,bt);
}
}
void BiTree::Printleaf(Node *bt)
{
if(bt!=NULL)
{
if(bt->lchild==NULL&&bt->rchild==NULL) //叶子结点满足的条件
cout<<bt->data<<" ";
Printleaf(bt->lchild);
Printleaf(bt->rchild);
}
}
void main()
{
cout<<"请键盘输入创建一棵二叉树的结点数据，以扩展二叉树前序遍历输入结点信息，以0代表空结点:"<<endl;
BiTree T;
cout<<"--------前序遍历--------"<<endl;
T.PreOrder();
cout<<endl;
cout<<"--------中序遍历--------"<<endl;
T.InOrder();
cout<<endl;
cout<<"--------后序遍历--------"<<endl;
T.PostOrder();
cout<<endl;
//T.Childmessage();
cout<<"各结点的双亲和孩子信息为："<<endl;
T.CPmessage();
cout<<endl;
cout<<"叶子结点信息为：";
T.Printleaf();
cout<<endl;
}
