2012-10-14

关于二叉树非递归遍历

首先，这里先给出二叉树的节点定义以及递归的二叉树先序遍历：

//节点定义
typedef class node
{
public:
	node()
	{
		lchild=NULL;
		rchild=NULL;
	};
	char data;
	class node *lchild;
	class node *rchild;
         //bool isFromRight;//非递归后序遍历用
}BiNode;
//递归先序遍历
void preorder(BiNode* p)
{
	if(p==NULL)
		return;
	cout<<p->data<<" ";//先序遍历
	preorder(p->lchild);
	//cout<<p->data<<" ";//放在这就是中序遍历
	preorder(p->rchild);
	//cout<<p->data<<" ";//放在这就是后序遍历
}

下面我们要将先序遍历由递归形式变成非递归形式。按照常理来说，只要模拟递归函数中的隐含的栈操作，就能够把递归变成非递归。所以，二叉树先序遍历的非递归形式应该是这样的：

//非递归先序遍历
void iterativePreorderClassical(BiNode* p)
{
	stack<BiNode*> s;
	if(p!=NULL)
	{
		s.push(p);
		while(!s.empty())
		{
			p=s.top();
			s.pop();
			cout<<p->data<<" ";//对V节点的访问已经完成
			if(p->rchild!=NULL)
				s.push(p->rchild);//先将右子节点压入栈
			//cout<data<<endl;//放在这并不能实现中序遍历！
			if(p->lchild!=NULL)
				s.push(p->lchild);//将左子节点压入栈
			//cout<data<<endl;//放在这并不能实现后序遍历！
		}
	}
}

这里有一个问题，将输出语句放到两个push()操作之间或者之后，能使二叉树遍历形式变成中序或者后序吗？答案是不能。要注意这里对当前节点的访问和两个子节点的压栈操作是同级别的，而子节点的访问必定在下一次循环中，所以对当前节点的访问必定在子节点之前，所以输出不管放哪儿都是先序遍历。

模拟栈操作的中序遍历

而中序遍历的非递归形式，如果模拟递归函数中的隐含的栈操作，应该是这样的：

//非递归中序遍历
void iterativeInorderClassical(BiNode* p)
{
	stack<BiNode*> s;
	stack<BiNode*> t;
	while(p!=NULL)
	{
		while(p!=NULL)
		{
			if(p->rchild!=NULL) //如果有右子节点，把它先压入栈中
			{
				s.push(p->rchild);
			}
			s.push(p);
			p=p->lchild;
		}
		p=s.top();
		s.pop();//弹出V节点
		while(!s.empty()&&p->rchild==NULL)//一直弹出没有右子节点的节点，直到下一个节点的右子结点不为空为止
		{
			cout<<p->data<<" ";
			p=s.top();
			s.pop();
		}
		cout<data<<endl;
		if(!s.empty())
		{
			p=s.top();
			s.pop();//弹出R节点
		}
		else
			p=NULL;
	}
}

这个代码不详细解释的话很难理解(~~根本记不住嘛~~)。

比较好理解的遍历方式

而现在网上能找到的先序遍历和中序遍历的代码一般是这个样子的：

//另一版本的先序遍历
void iterativePreorder(BiNode* p)
{
	stack<BiNode*> s;
	while(p!=NULL||!s.empty())
	{
		while(p!=NULL)
		{
			cout<<p->data<<" ";//访问V节点
                        s.push(p);
			p=p->lchild;
		}
		if(!s.empty())
		{
			p=s.top();
			p=p->rchild;//访问它的右子节点
			s.pop();
		}
	}
}
//另一版本的中序遍历
void iterativeInorder(BiNode* p)
{
	stack<BiNode*> s;
	while(p!=NULL||!s.empty())
	{
		while(p!=NULL)
		{
			s.push(p);
			p=p->lchild;
		}
		if(!s.empty())
		{
			p=s.top();
			cout<<p->data<<" ";//访问V节点，输出换了个位置
			p=p->rchild;
			//访问它的右子节点
			s.pop();
		}
	}
}

这两段代码我们发现仅仅是输出换了个位置，就实现了先序和中序遍历。我想了一下，应该是这样的。下面定义一种退化树，它的任意节点都没有左子节点，任意节点都无需考虑左子树。在这种退化树的遍历中，先序遍历和中序遍历是没有区别的。通常的3个步骤VLR或者LVR会变成2个步骤,VR。因为节点没有左子节点，所以只需访问该节点，然后处理它的右子结点。那么我们只要想办法把二叉树的遍历拆分成退化树的遍历形式，就可以用很方便地处理先序遍历和中序遍历了。我们依次将节点的左子节点压栈直到该节点的最左侧节点，然后依次弹栈。这样可以保证当前处理的节点，其左子树都已经被访问过，只需访问该节点，然后处理它的右子树，再重复以上步骤。这里先序遍历和中序遍历的唯一区别就是，先序遍历在节点的左子节点压栈之前，即V->L时输出节点，而中序遍历是在左子树节点弹栈之后，即L->http://7sbo5n.com1.z0.glb.cloudV时输出节点。要注意前序和中序里退化树上的节点是即用即删的。而后序遍历的顺序是从下往上的，所以不能立即删除这个节点，所以这个节点一共会弹出2次，一次是从左子节点(L->V)弹栈，另一次是从右子节点弹栈(R->V)上来的（前序和中序中有左边弹栈一次）。这个也好解决，只要我们对节点BiNode加一个isFromRight的属性就行了，代码如下：

//后序遍历非递归
void iterativePosterorder(BiNode* p)
{
	stack<BiNode*> s;
	while(p!=NULL||!s.empty())
	{
		while(p!=NULL&&p->isFromRight==false)//左子树尚未遍历过
		{
			p->isFromRight=false;
			s.push(p);
			p=p->lchild;
		}
		if(!s.empty())
		{
			p=s.top();//看一看是不是从右边上来的
			if(p->isFromRight==false)//如果不是右边上来的
			{
				p->isFromRight=true;
                                p=p->rchild;//访问它的右子节点
				//s.pop();先不弹栈，这个节点没输出呢
			}
			else//如果是从右边上来的
			{
				cout<data<<endl;//访问V节点
				s.pop();//弹栈
			}
		}
	}
}

只多用一个节点记录的后续遍历

上面的方式虽然好理解，但是毕竟每个节点都要添加属性，空间占用较大。我们可以利用一个指针pre来记录刚访问的子节点，然后判断pre是左节点或者右节点。但是这种方法，在理解上麻烦一些。

首先，对于这个pre我们有如下要求：

pre只能指向节点的左右子结点，而不能指向结点的父亲结点。
pre不能指向NULL，否则在叶子结点级别，左右都是NULL，无法辨别，这就要求指针p也不能指向NULL。

因为p不能指向NULL，造成的影响如下：

之前的前序中序遍历，我们是用p==NULL作为左子树是否已经遍历完毕的标识（注意这个和左边弹栈上来还是右边弹栈上来不一样），来避免重新向左压栈，从而能够顺利地弹栈到上一层的父亲结点，再向右走。(后续遍历，用的是p->isFromRight==true)。而现在p不能等于NULL了，pre又起不到这个作用（这里pre等于左或右都有可能），我们必须自己保证在开始向左压栈时，这个结点的左子树没有被访问过。而想要这个结点的左子树没有被访问过，那这个结点必须刚刚由父结点向右访问而来（显而易见，因为向左的话早压到栈里去了）。这样，问题就转化为了需要寻找一个有右节点的父结点的问题，而且这个右节点还得是没访问过的（这里pre就能派上用场了）。最终代码如下：


//后序遍历非递归
void iterativePosterorderAdavanve(BiNode* p)
{
	 stack<BiNode*> s;
	 BiNode* pre;
	 while(p!=NULL)
	 {
	     while(p->lchild!=NULL)
	     {
	    	 //注意这里不计算pre，满足要求1
	         s.push(p);
	         p=p->lchild;
	     }
	     while(p!=NULL&&(p->rchild==NULL||p->rchild==pre))//必须要找到一个有未访问的右节点的父结点，可能需要多次弹出
	     {
			  cout<<p->data<<" ";
			  pre=p;//p不到NULL，满足要求2
			  if(s.empty())//结束的条件放在这里了
				  return;
			  p=s.top();
			  s.pop();
	     }
	     s.push(p);//为了先访问右结点，再压一次
	     p=p->rchild;//访问它的右子节点
	 }
}

参考网址：http://www.cnblogs.com/hicjiajia/archive/2010/08/27/1810055.html

心怀畏惧

Do not go gentle into that good night

关于二叉树非递归遍历

模拟栈操作的中序遍历

比较好理解的遍历方式

只多用一个节点记录的后续遍历