c++实现数据结构的二叉树及其遍历二叉树

￡神魔★判官ぃ 2022-05-22 10:10 217阅读 0赞

二叉树的初始化，删除，遍历

注意：看是否满足条件，则必须是在调试的对话框的右下侧观察数据是否满足是一个树及其它的左孩子和右孩子

//二叉树链式存储的实现
    #include<iostream>
    #include<cstring>
    using namespace std;
    
    struct ECS_data  //先定义好一个数据的结构
    {
    	char data;
    	ECS_data *l;
    	ECS_data *r;
    };
    
    class ECS
    {
    private:
    	//int level;            //树高
    	int n;                 //表示有多少个节点数
    	int n1;                //表示的是数组的总长度值，（包括#）,因为后面要进行删除判断
    	ECS_data *temp[1000];
    public:
    	ECS_data *root;
    	ECS()  //初始化
    	{
    		ECS_data *p;
    		char t[1000];int i;
    		int front=0,rear=1;          //front表示有多少个节点，rear表示当前插入的点的父母
    		cout<<"请按正确顺序输入二叉树的数据:";
    		cin.getline(t,1000);         //先把输入的数据输入到一个t数组
    		//cout<<t<<" "<<endl;
    		int n1=strlen(t);          //测量数据的长度
    		n=0;
    		for(i=0;i<n1;i++)
    		{
    			if(t[i]!='#')
    			{
    				p=NULL;
    				if(t[i]!=',')       //满足条件并开辟内存
    				{
    					n++;
    					p=new ECS_data;
    					p->data=t[i];
    					p->l=NULL;
    					p->r=NULL;
    				}
    				front++;
    				temp[front]=p;
    				if(1 == front){root=p;}
    				else
    				{
    					if((p!=NULL)&&(0==front%2))
    					{
    						temp[rear]->l=p;//刚开始把这里写成了==
    					}
    					if((p!=NULL)&&(1==front%2))
    					{
    						temp[rear]->r=p;
    					}
    					if(1==front%2)rear++;       //就当前的数据找这个数据的父母
    				}
    			}
    		}
    	}
    	~ECS()                         //释放内存
    	{
    		int i;
    		for(i=1;i<=n;i++)
    			if(temp[i]!=NULL)
    				delete temp[i];
    	}
    	void JS()                         //记录节点的个数
    	{
    		int s;
    		s=n;
    	cout<<"该二叉树的节点数为:"<<s<<endl;
    	}
    
    	void BL1(ECS_data *t)//先序遍历
    	{
    		if(NULL!=t)
    		{
    			cout<<t->data<<",";
    			BL1(t->l);
    			BL1(t->r);
    		}
    	}
    	void BL2(ECS_data *t)//中序遍历
    	{
    		if(NULL!=t)
    		{
    			BL2(t->l);
    			cout<<t->data<<",";
    			BL2(t->r);
    		}
    	}
    	void BL3(ECS_data *t)//后续遍历
    	{
    		if(NULL!=t)
    		{
    			BL3(t->l);
    			BL3(t->r);
    			cout<<t->data<<",";
    		}
    	}
    };
    
    int main()
    {
    	ECS a;
    	a.JS();
    	a.BL1(a.root);
    	cout<<endl;
    	a.BL2(a.root);
    	cout<<endl;
    	a.BL3(a.root);
    	cout<<endl;
    	return 0;
    }