C++实现二叉树前序中序后续遍历的非递归方法总结

时间：2021-03-20 11:21:06

前序中序相对简单，不废话，直接代码：

二叉树前序遍历非递归实现：

template<class T>
void BinaryTree<T>::PreOrderTraverse(BinaryTreeNode<T> *root) const
{
	stack<BinaryTreeNode<T>*> s;
	BinaryTreeNode<T> *p = root;
	while(!s.empty() || p!=NULL)
	{
		while(p)
		{
			s.push(p);
			cout<<p->GetData();
			p = p->GetLeftChild();
		}
		p = s.top();
		s.pop();
		p = p->GetRightChild();
	}
}

二叉树中序遍历非递归实现：

template<class T>
void BinaryTree<T>::InOrderTraverse(BinaryTreeNode<T> *root) const
{
	stack<BinaryTreeNode<T>*> s;
	BinaryTreeNode<T> *p = root;
	while(!s.empty() || p!=NULL)
	{
		while(p)
		{
			s.push(p);
			p = p->GetLeftChild();
		}
		p = s.top();
		cout<<p->GetData();
		s.pop();
		p = p->GetRightChild();
	}
}

二叉树后续遍历非递归实现方法一：

    后序的话相对前序中序有点难度，因为后序要求父节点在左右子节点被访问后才访问，而以上的前序中序的思路中，父节点在右节点被访问之前已经出栈了。所以要想实现非递归的后续遍历，必须让父节点不能“提前”出栈。这就需要对父节点出现在栈顶的次数进行计数：第一次出现的时候不出栈，第二次再出现，表明右孩子子树已经遍历完毕，这个时候再出栈并完成遍历。

    那么如何对父节点出现在栈顶的次数进行计数或者标记呢？一种方法是构建一个新的结构体，其中包含二叉树节点的指针和一个标记变量。每次对这个结构体的标记变量设置读取，并进行压栈出栈操作。另一种方法是再建立一个栈作为辅助数据结构，其中的内容记录每个节点在栈顶出现的次数。这个栈必须和二叉树节点栈保持同步，即每次一起出栈进栈。代码如下：

template<class T>
void BinaryTree<T>::PostOrderTraverse(BinaryTreeNode<T> *root) const
{
	stack<BinaryTreeNode<T>*> s;
	stack<int> index;//辅助数据结构，用于记录每个栈顶元素出现的次数，需要和栈s操作同步
	BinaryTreeNode<T> *p = root;
	while(!s.empty() || p!=NULL)
	{
		while(p)
		{
			s.push(p);
			index.push(0);//first time 
			p = p->GetLeftChild();
		}		
		if(index.top() == 1)
		{
			cout<<s.top()->GetData();
			s.pop();
			index.pop();
		}
		else
		{
			p = s.top();
			p = p->GetRightChild();
			index.top() = 1;//second time			
		}		
	}
}

二叉树后续遍历非递归实现方法二：

    以上的前序中序后序非递归实现都使用了栈作为辅助数据结构，而且前序中序的节点进栈出栈的次序完全相同，后序的节点进栈出栈顺序略有不同但基本相似，只是调整了父节点出栈的时间。后序遍历还有一种方法，节点进栈出栈的时间跟之前完全不同。为了保证父节点在左子节点和右子节点之后被访问，利用栈的先进后出的原理，每次都让父节点先进栈，然后父节点的右子节点在左子节点之前先进栈，这样就能保证（左-〉右-〉父）的访问顺序。具体实现就是： 要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。代码如下： 

template<class T>
void BinaryTree<T>::PostOrderTraverse(BinaryTreeNode<T> *root) const
{
    stack<BinaryTreeNode<T>*> s;
    BinaryTreeNode<T> *cur;                      //当前结点 
    BinaryTreeNode<T> *pre=NULL;                 //前一次访问的结点 
    s.push(root);
    while(!s.empty())
    {
        cur=s.top();
        if((cur->GetLeftChild()==NULL&&cur->GetRightChild()==NULL)||
           (pre!=NULL&&(pre==cur->GetLeftChild()||pre==cur->GetRightChild())))
        {
            cout<<cur->GetData();  //如果当前结点没有孩子结点或者孩子节点都已被访问过 
              s.pop();
            pre=cur; 
        }
        else
        {
            if(cur->GetRightChild()!=NULL)
                s.push(cur->GetRightChild());
            if(cur->GetLeftChild()!=NULL)    
                s.push(cur->GetLeftChild());
        }
    }
}
    此方法参考http://www.cnblogs.com/dolphin0520/archive/2011/08/25/2153720.html

    按照这种思路，可以将前序和中序的非递归遍历用这种思路实现，有兴趣的朋友可以试一下。

标签：

相关文章