树的非递归实现的中序遍历

向右看齐 2022-05-17 10:15 22阅读 0赞

好纠结，还用了二级指针的传递，记开辟二级指针，刚开始以为好简单，后来写着写着好麻烦！！！还有什么比较好的，简单的请给点意见吧！

//遍历二叉树的非递归实现
    #include<iostream>
    #include<cstring>
    #define STACKlength 100
    #define ADD 10 
    #define ERROR 0
    #define TRUE 1
    using namespace std;
    
    struct ECS_data  //先定义好一个数据的结构
    {
    	char data;
    	ECS_data *l;
    	ECS_data *r;
    };
    
    class SX_Stack
    {
    private:
    	ECS_data **base;//改成二级指针
    	int top;
    	int stacklength;
    public:
    	SX_Stack(int n=STACKlength)
    	{
    		base=new ECS_data *[n];
    		//if(base==NULL)return ERROR;因为用了构造函数，所以没有返回值
    		top=-1;
    		stacklength=n;
    		//return TRUE;
    	}
    	void DestorySX_Stack()  //销毁栈
    	{
    		if(stacklength) delete [] base;
    	}
    	void ClearSX_Stack()   //将栈清空
    	{
    		top=-1;
    	}
    	int SX_StackEmpty()    //检测栈是否为空
    	{
    		if(top==-1)return TRUE;
    		else
    			return ERROR;
    	}
    	int GetTop(ECS_data **e)//（改了这）返回栈顶元素,不能用一级指针否则不会改变指针所指向的数据，或用引用的形式ECS_data *&e
    	{
    		if(top==-1)return ERROR;
    		*e=base[top];//刚开始把&base[0]赋值给了左边
    		return TRUE;
    	}
    	int Push(ECS_data *e)  //进栈并扩大空间
    	{
    		if(top==stacklength-1)
    		{
    			ECS_data **temp;
    			int i;
    			temp=new ECS_data *[stacklength+ADD];//要改成二级的指针
    			if(temp==NULL)return ERROR;
    			for(i=0;i<stacklength;i++)
    				temp[i]=base[i];
    			delete [] base;//把他销毁了是指销毁了他所指的位置，但不是销毁变量
    			base=temp;//所以后面还是可以用到的base
    			stacklength=stacklength+ADD;
    		}
    		top++;
    		base[top]=e;//还要改这，刚开始用了*e赋值
    		return TRUE;
    	}
    	int Out(ECS_data *&e)  //出栈
    	{
    		if(top==-1)return ERROR;
    		e=base[top];
    		top--;
    		return TRUE;
    	}
    	int Length()
    	{
    		return (top+1);
    	}
    	int output(ECS_data *e)//写过输出函数
    	{
    			cout<<e->data<<" ";
    		return TRUE;
    	}
    };
    
    class ECS:public SX_Stack
    {
    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;
    		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;
    	}
    	int BL_FDG() //中序遍历
    	{
    		ECS_data *p;//T是根，p是栈中返回的元素
    		Push(temp[1]);
    		while(!SX_StackEmpty())
    		{
    			while(GetTop(&p) && p)//改了这里，取了地址传递，因为定义的是二级指针作为参数
    			Push(p->l);
    		Out(p);
    		if(!SX_StackEmpty())
    		{
    			Out(p);
    			if(p)
    			{
    			if(!output(p)) return ERROR;
    			Push(p->r);
    			}
    		}
    		}
    	}
    };
    
    int main()
    {
    	ECS a;
    	cout<<"非递归实现的中序排列:";
    	a.BL_FDG();
    	cout<<endl;
    	return 0;
    }

另一种较简单的实现

#include<iostream>
    using namespace std;
    
    const int MAXN = 10001;
    
    char tree[MAXN];
    bool vis[MAXN];
    
    struct s
    {
    	int item[MAXN];
    	int top;
    
    	void push(int u)
    	{item[top++] = u;}
    
    	void pop()
    	{--top;}
    
    	int get()//返回栈顶元素
    	{return item[top-1];}
    
    	bool empty()//判断是否为空
    	{
    		if(top==0)
    			return true;
    		return false;
    	}
    
    	void clear()//清空栈
    	{top=0;}
    }stack;
    
    bool init()//初始化
    {
    	memset(vis,false,sizeof(vis));
    	for(int i=1;i!=MAXN;i++)
    		tree[i] = '*';
    	return true;
    }
    
    int main()
    {
    	while(init())
    	{
    		char ch;
    		int i=1;
    		while(cin>>ch&&ch!='#')//层序输入，以‘#’结尾，无则输入‘，’
    		{
    			tree[i] = ch;
    			++i;
    			vis[i] = true;
    		}
    		stack.clear();
    		stack.push(1);
    		int buff;
    		while(!stack.empty())   //中序遍历，左中右，就是把原来的递归的函数按步骤直接改成了非递归的调用栈中函数实现
    		{
    			buff = stack.get();
    			if(tree[buff*2]!='*'&&buff*2<=1001&&tree[buff*2]!=','&&vis[buff*2])
    			{
    				stack.push(buff*2);
    				vis[buff*2] = false;
    				continue;
    			}
    			else
    			{
    				cout<<tree[stack.get()];
    				stack.pop();
    			}
    				if(tree[buff*2+1]!='*'&&buff*2+1<=1001&&tree[buff*2+1]!=',')
    				{
    					stack.push(buff*2+1);
    					vis[buff*2+1] = false;
    				}
    		}
    	}
    }