5.1 二叉树的顺序存储实验

2017-12-12 08:25:43来源:CSDN作者:Vivien_wyx人点击

分享

一、实验目的

1、   熟练理解树和二叉树的相关概念,掌握的存储结构和相关操作实现;

2、   掌握树的顺序结构的实现;

3、   学会运用树的知识解决实际问题

二、实验内容

自己确定一个二叉树(树结点类型、数目和结构自定)利用顺序结构方法存储。实现树的构造,并完成:

1)层序输出结点数据;

2)以合理的格式,输出各个结点和双亲、孩子结点信息;

3)输出所有的叶子结点信息;

4)分析你的算法对于给定的二叉树的存储效率。

三 、实验步骤

1、依据实验内容,先确定具体的二叉树,并说明结点的数据据类型;

2、设计具体的算法;

3、写出完整程序;

4、总结、运行结果和分析算法效率。

5、总体收获和不足,疑问等。

四、实验代码

#include<iostream>#include<string>using namespace std;const int MaxSize=100;class Tree{	private:		char data[MaxSize];		int n;		public:			Tree();			void Insert(char x);			void PerOrder(int root);			void InOrder(int root);	        void PostOrder(int root);};Tree::Tree(){	n=0;}void Tree::Insert(char x){	n++;	data[n]=x;}void Tree::PerOrder(int i){	if (data[i]!='.')	{		cout<<data[i];		if(2*i<=n&&data[2*i]!='.')		PerOrder(2*i);		if(2*i+1<=n&&data[2*i+1]!='.')		PerOrder(2*i+1);	}}void Tree::InOrder(int i){	if (data[i]!='.')	{		if(2*i<=n&&data[2*i]!='.')		InOrder(2*i);		cout<<data[i];		if(2*i+1<=n&&data[2*i+1]!='.')		InOrder(2*i+1);	}}void Tree::PostOrder(int i){	if (data[i]!='.')	{		if(2*i<=n&&data[2*i]!='.')		PostOrder(2*i);		if(2*i+1<=n&&data[2*i+1]!='.')		PostOrder(2*i+1);		cout<<data[i];	}}int main(){	string str;	while(cin>>str)	{		Tree tree;		for(int i=0;i<str.length();i++)		{			tree.Insert(str[i]);		}		cout<<"前序遍历序列:"<<endl; 		tree.PerOrder(1);		cout<<endl;		cout<<"中序遍历序列:"<<endl; 		tree.InOrder(1);		cout<<endl;		cout<<"后序遍历序列:"<<endl;		tree.PostOrder(1); 		cout<<endl;	}}

五、实验运行结果


六、实验总结和心得

树的遍历是指从根结点出发,按照某种次序访问树中所有结点,使得每个结点被访问一次且仅被访问一次。通常有前序遍历,后序遍历和层序遍历三种方式。

微信扫一扫

第七城市微信公众平台