二叉树遍历.cpp

树的遍历等数据结构程序代码实现

#include<iostream.h>
#include<string.h>
#include<stdlib.h>
struct btnode
{ 
	char data;
	int tag;
	struct btnode *lchild,*rchild;
};

const int MAX=100;
template<class T>//栈模板
class stack
{ 
	T S[MAX];
	int top;
public:    
	stack(){ top=-1;}
	void push(T& item);
	T pop();
	int stackempty();
};

template<class T>
void stack<T>::push(T& item)//进栈
{ 
	if (top==MAX-1)
	{ 
		cout<<"栈满"<<endl;
		exit(1);
	}
	top++;
	S[top]=item;
}


template<class T>
T stack<T>::pop()//出栈
{ 
	T temp;
	if(top==-1)
	{
		cout<<"栈空"<<endl;
		exit(1);
	}
	temp=S[top];
	top--;
	return temp;
}


template<class T>
int stack<T>::stackempty(){return top==-1;}

btnode *creatbtr(btnode *&t);
void preorder(btnode *t);
void inorder(btnode *t);
void postorder(btnode *t);

btnode *creatbtr(btnode *&t)//建立二叉树
{ 
	//cout<<"输入二叉树先序序列,'#'代表位置为空，输完一个回车:";
	char ch;cin>>ch;
	if(ch=='#')t=NULL;
	else { btnode *p;
	p=(btnode *)new(btnode);
	p->data=ch;
	p->tag=1;
	t=p;
	creatbtr(t->lchild);
	creatbtr(t->rchild);
	} return t;
}
/*void preorder(btnode *t)
{  if(t)
{ cout<<t->data;
preorder(t->lchild);
preorder(t->rchild);
}
}
void inorder(btnode *t)
{ if(t)
{ inorder(t->lchild);
cout<<t->data;
inorder(t->rchild);
}
}
void postorder(btnode *t)
{ if(t)
{  postorder(t->lchild);
postorder(t->rchild);
cout<<t->data;
}
}//递归算法
*/
void preorder(btnode *t)//前序
{
	int i;
	btnode *p;
	stack<btnode*>st;
	if(t==NULL)
		cout<<"空树!"<<endl;
	else
	{
		i=0;
		p=t;
	}
	do
	{ 
		while(p!=NULL)
		{ 
			cout<<p->data;
			if(p->rchild!=NULL)
			{ 
				i++;
				st.push(p->rchild);
			}
			p=p->lchild;
		}
		if(i!=0)
		{
			p=st.pop();
			i--;
		}
	} while((i!=0)||(p!=NULL));
}

void inorder(btnode *t)//中序
{ 
	int i;
	btnode *p;
	stack<btnode*>st;
	if(t==NULL)
		return;
	else
	{ 
		i=0;
		p=t;
	}
	do 
	{ 
		while(p!=NULL)
		{
			i++;
			st.push(p);
			p=p->lchild;
		}
		if(i!=0)
		{
			p=st.pop();
			i--;
			cout<<p->data;
			p=p->rchild;
		}
	}while((i!=0)||(p!=NULL));
}

void postorder(btnode *t)//后序
{
	int i;
	btnode *p;
	stack<btnode *>st;
	if(t==NULL) 
		return;
	else
	{
		i=0;
		p=t;
	}
	do
	{ 
		while(p!=NULL)
		{
			i++;
			st.push(p);
			p=p->lchild;
		}
		while((i!=0)&&(p==NULL))
		{
			p=st.pop();
			i--;
			if(p->tag==1)
			{
				i++;
				st.push(p);
				p->tag=0;
				p=p->rchild;
			}
			else
			{
				cout<<p->data;
				p=NULL;
			}
		}
	}while((i!=0)||(p!=NULL));
}

void main()
{ 
	int m;
	cout<<"首先建立二叉树!"<<endl;
	cout<<"输入二叉树先序序列,'#'代表位置为空，全部输入后回车:";
	btnode *t=NULL;
	t=creatbtr(t);
a:cout<<"选择你想遍历二叉树的方式:1,先序遍历;2,中序遍历;3,后序遍历;其他,退出:";cin>>m;
  switch(m)
  {
  case 1:preorder(t);cout<<endl;goto a;
  case 2:inorder(t);cout<<endl;goto a;
  case 3:postorder(t);cout<<endl;break;
  default:break;
  }
  cout<<"欢迎使用!"<<endl;
}