二叉树非递归于递归遍历

二叉树中的遍历方法有三种，前序遍历，中序遍历，后序遍历

结点结构

template<typename T>
struct BinaryNode
{
    T elem;
    BinaryNode *left;
    BinaryNode *right;
    BinaryNode(T d, BinaryNode *l=NULL, BinaryNode *r=NULL):elem(d), left(l),right(r){}
};

　　

1、递归算法

递归算法比较简单，毕竟二叉树是按照递归的方法定义的

前序遍历递归算法

template<typename T>
void preOrder_recursive(BinaryNode<T>* root)
{
	if(!root)
	{
		visit(root);
		preOrder_recursive(root->lchild);
		preOrder_recursive(root->rchild);
	}
}

　　

中序遍历递归算法

template<typename T>
void inorder_recursive(BinaryNode<T>* root)
{
    if(!root)
    {
    	inorder_recursive(root->left);
    	visit(root);
    	inorder_recursive(root->right);
    }
    else
    	return;
}

　　

后序遍历递归算法

template<typename T>
void preOrder_recursive(BinaryNode<T>* root)
{
	if(!root)
	{
		visit(root);
		preOrder_recursive(root->lchild);
		preOrder_recursive(root->rchild);
	}
}

　　

2、非递归算法比较麻烦

都要利用栈结构来解决问题

前序遍历非递归算法

//前序遍历先访问根结点，再访问孩子结点
/*用栈储存根结点，首先一直往左访问，直至NULL时，从栈中取栈顶元素，开始访问右方结点*/
template<typename T>
void preOrder(BinaryNode<T>* root)
{
	stack<BinaryNode*> bn;
	BinaryNode* p=root;
	while(p!=NULL||!bn.empty())
	{
		while(p!=NULL)
		{
			visit(p);
			bn.push(p);
			p=p->lchild;
		}
		if(!bn.empty())
		{
			p=bn.top();
			bn.pop();
			p=p->rchild;
		}
	}
}

　　

中序遍历非递归算法

template<typename T>
void inorder(BinaryNode<T>*root)
{
    stack<BinaryNode*> bn;
    BinaryNode* p=root;
    
    while(p!=NULL||!bn.empty())
    {
       while(p!=NULL)
       {
       	  bn.push(p);
       	  p=p->lchild;
       }
       if(!bn.empty())
       {
       	  p=bn.top();
       	  bn.pop();
       	  visit(p);
       	  p=p->rchild;
       }
    }
}

　　

后序遍历非递归算法（挺难弄的）

两种方法

（1）法1

template<typename T>
typedef struct BinaryNodewithTag
{
    BinaryNode<T>* bn;
    bool tag;
}BTag;

template<typename T>
void postOrder1(BinaryNode<T>* root)
{
    stack<Btag<T>*> s;
    BinaryNode<T>* p=root;
    BTag<T>* temp;

    while(p!=NULL||!s.empty())
    {
    	while(p!=NULL)
    	{
    		temp = new BTag();
    		temp->bn=p;
    		temp->tag=true;
    		s.push(temp);
    		p=p->lchild;
    	}
    	if(!s.empty())
    	{
    		temp=s.top();
    		s.pop();
    		if(temp->tag)//第一次访问
    		{
    			temp->tag=false;
    			s.push(temp);
    			p=temp->bn->rchild;//访问右孩子
    		}
    		else//第二次访问
    		{
    			visit(temp->bn);
    			p=NULL;
    			delete temp;
    		}
    	}
    } 
}

　　

（2）法2

template<typename T>
void postOrder2(BinaryNode<T>* root)
{
	stack<BinaryNode*> bn;
	BinaryNode *cur;
	BinaryNode *pre=NULL;//上一个被访问的结点
    bn.push(root);

	while(!bn.empty())
	{
		cur=bn.top();
		if((cur->rchild==NULL&&cur->rchild==NULL)||
			(pre!=NULL&&(pre==cur->lchild||pre==cur->rchild)))
		{//如果没有左右孩子或则左右孩子已被访问
			visit(cur);
			bn.pop();
			pre=cur;
		}
		else
		{
			if(cur->rchild!=NULL)
			{
				bn.push(cur->rchild);
			}
			else(cur->lchild!=NULL)
			{
				bn.push(cur->lchild);
			}
		}
	}
}