学步园

1：递归：

//先序 
void PreOrder(BTNode *p)
{
	if( p != NULL)//注意不要忽略掉 
	{
		cout<<p->data;
		PreOrder(p->left);
		PreOrder(p->right);
	}
}
//中序 
void InOrder(BTNode *p)
{
	if( p!=NULL )//注意不要忽略掉
	{
		InOrder(p->left);
		cout<<p->data;
		InOrder(p->right);
	}
}
//后序 
void PostOrder(BTNode *p)
{
	if( p!=NULL )//注意不要忽略掉
	{
		PostOrder(p->left);
		PostOrder(p->right);
		cout<<p->data;	
	}
}

2：非递归

//非递归的先序序遍历 
void PreOrder(BTNode *root)
{
	stack<BTNode*>S;
	BTNode *p;
	if( root!=NULL )//如果二叉树不为空
	{	
		S.push(root);
		while( !S.empty())
		{ 	
			p=S.top();
			S.pop();
			
			cout<<p->data;
			if( p->right!=NULL )//先将右儿子入栈
			{
				 S.push(p->right);
			}

			if( p->left!=NULL )//将左儿子入栈
			{
				S.push(p->left);
			}
		}
	}
	cout<<endl;
}

//非递归的中序序遍历 
void InOrder(BTNode *root)
{
	stack<BTNode*>S;
	BTNode *p;
	if( root!=NULL )//如果二叉树不为空
	{	
		p=root;
		while( !S.empty() || p!=NULL )
		{ 
			while( p!=NULL )//先扫描*p的所有左节点， 并入栈
			{
		    	S.push(p);
				p=p->left;
			}
            
			//此时， 栈顶元素没有左孩子或左孩子均已访问过
			if( !S.empty() )//
			{
				p=S.top();
				S.pop();
				cout<<p->data;

				p=p->right;
			}
		}
	}
	cout<<endl;
}

//非递归的后序遍历 
void PostOrder(BTNode *root)
{
    stack<BTNode*>S;
	BTNode *p, *pre;
	int flag;//标记 
	
	if( root!=NULL ) //二叉树非空 
	{
		p=root;
		do
		{
			while( p!=NULL)//将*p的所有左节点入栈
			{
				S.push(p);
				p=p->left; 
			} 
			
			//执行到此处时，栈顶元素没有左儿子或左子树均已访问过
			pre=NULL;//pre指向栈顶元素的前一个已访问的节点 
			flag=1; //表示*b的左孩子已访问过， 或为空
			
			while( !S.empty() && flag)
			{
				p=S.top();//取出当前的栈顶元素 
				
				if( p->right==pre )//当*p的右儿子已访问过，或pre=NULL即*p的右儿子为空 
				{
					S.pop();//将p出栈 
					
					pre=p;//pre指向刚访问过的节点 
					cout<<p->data;	
				}
				else//
				{
				    p=p->right;//p指向右儿子 
					flag=0;	//表示*b的左儿子尚未访问过 
				}
			} 
		}while( !S.empty()); 
	}
	cout<<endl;
} 

3：层次遍历

//层次遍历：其实就是BFS
void LevelOrder(BTNode *p) 
{
	queue<BTNode *> Q;
	BTNode *temp=NULL;//注意 
	Q.push( p );
	while( !Q.empty() )
	{
		temp=Q.front();
		Q.pop();
		cout<<temp->data;
		if( temp->left!=NULL)
		    Q.push( temp->left);
        if( temp->right!=NULL)
		    Q.push( temp->right);
	}
	cout<<endl;
}

完整程序：

#include<iostream> 
#include<stack>
#include<queue>
using namespace std;
typedef struct Node
{
	char data;
	Node *left;
	Node *right;
}BTNode;

void CreateBTree(  BTNode *&root, char str[])//参数：传入根节点的指针，二叉树的括号表示 
{
	int j=0, flag=0;
	stack<BTNode *> S;
	BTNode *p=NULL, *temp=NULL; 
	while( str[j]!='\0')
	{
		switch( str[j] )
		{
			case '(':flag=1;S.push(p);break;//若遇到左括号,则把前面刚刚创建的那个节点入栈 
			case ',':flag=2;break;//若遇到逗号，说明其后创建的节点为右孩子节点， flag=2
			case ')':S.pop();break;//若遇到右括号，说明栈顶结点的左右孩子处理完毕， 栈顶结点出栈
			
			default://遇到元素
			p=new Node;//创建新节点
			p->data=str[j]; p->left=p->right=NULL;//为新建节点赋值：且此时栈顶结点是p的父节点 
			
			if( root==NULL ) //如果根节点为空
			{
			    root=p;
			}
			else 
			{
				temp=S.top();
		    	switch( flag )
			   {
			    	case 1:temp->left=p;break;//flag=1说明p为栈顶元素左儿子
				    case 2:temp->right=p;break;//p为栈顶元素右儿子
			   }
			}	 
		}
		
		j++;
	}
}
//非递归的先序序遍历 
void PreOrder(BTNode *root)
{
	stack<BTNode*>S;
	BTNode *p;
	if( root!=NULL )//如果二叉树不为空
	{	
		S.push(root);
		while( !S.empty())
		{ 	
			p=S.top();
			S.pop();
			
			cout<<p->data;
			if( p->right!=NULL )//先将右儿子入栈
			{
				 S.push(p->right);
			}

			if( p->left!=NULL )//将左儿子入栈
			{
				S.push(p->left);
			}
		}
	}
	cout<<endl;
}
//非递归的中序序遍历 
void InOrder(BTNode *root)
{
	stack<BTNode*>S;
	BTNode *p;
	if( root!=NULL )//如果二叉树不为空
	{	
		p=root;
		while( !S.empty() || p!=NULL )
		{ 
			while( p!=NULL )//先扫描*p的所有左节点， 并入栈
			{
		    	S.push(p);
				p=p->left;
			}
            
			//此时， 栈顶元素没有左孩子或左孩子均已访问过
			if( !S.empty() )//
			{
				p=S.top();
				S.pop();
				cout<<p->data;

				p=p->right;
			}
		}
	}
	cout<<endl;
}
//非递归的后序遍历 
void PostOrder(BTNode *root)
{
    stack<BTNode*>S;
	BTNode *p, *pre;
	int flag;//标记 
	
	if( root!=NULL ) //二叉树非空 
	{
		p=root;
		do
		{
			while( p!=NULL)//将*p的所有左节点入栈
			{
				S.push(p);
				p=p->left; 
			} 
			
			//执行到此处时，栈顶元素没有左儿子或左子树均已访问过
			pre=NULL;//pre指向栈顶元素的前一个已访问的节点 
			flag=1; //表示*b的左孩子已访问过， 或为空
			
			while( !S.empty() && flag)
			{
				p=S.top();//取出当前的栈顶元素 
				
				if( p->right==pre )//当*p的右儿子已访问过，或pre=NULL即*p的右儿子为空 
				{
					S.pop();//将p出栈 
					
					pre=p;//pre指向刚访问过的节点 
					cout<<p->data;	
				}
				else//
				{
				    p=p->right;//p指向右儿子 
					flag=0;	//表示*b的左儿子尚未访问过 
				}
			} 
		}while( !S.empty()); 
	}
	cout<<endl;
} 

//层次遍历：其实就是BFS
void LevelOrder(BTNode *p) 
{
	queue<BTNode *> Q;
	BTNode *temp=NULL;//注意 
	Q.push( p );
	while( !Q.empty() )
	{
		temp=Q.front();
		Q.pop();
		cout<<temp->data;
		if( temp->left!=NULL)
		    Q.push( temp->left);
        if( temp->right!=NULL)
		    Q.push( temp->right);
	}
	cout<<endl;
}
 
int main()
{
	char str[100];
	BTNode *root=NULL;//注意一定要对指针赋初值，否则会出现各种诡异的错误
	cout<<"输入二叉树的括号表示："; 
	cin>>str;
	CreateBTree(root, str);
	cout<<"先序遍历结果为："; 
	PreOrder(root);
	cout<<"中序遍历结果为：";
	InOrder(root);
	cout<<"后序遍历结果为：";
	PostOrder(root);
	cout<<"层次遍历结果为：";
	LevelOrder(root);
	
}