首页 > 数据结构 > 树形结构 > 二叉树非递归中序遍历
2014
06-17

二叉树非递归中序遍历

前一篇二叉树非递归先序遍历说了非递归的先序遍历,中序遍历大致类似,但稍微有所区别。递归版本如下:

void preOrder(TNode* root)
{
if (root != NULL)
{
preOrder(root->left);
Visit(root);
preOrder(root->right);
}
}

根据前面的先序遍历,可以类似的构造出中序遍历的两种方式。仔细想一下,只有第二种方法 iterativePreorder2 改过来时最方便的。需要的改动仅仅调换一下节点访问的次序,先序是先访问,再入栈;而中序则是先入栈,弹栈后再访问。伪代码如下。时间复杂度与空间复杂度同先序一致。

#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <stack>

using namespace std;

/* 二叉树节点 */
struct node
{
    int data;
    struct node* left;
    struct node* right;
};

struct node* newNode(int data)
{
    struct node* node = new struct node;
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return(node);
}

void iterativeInorder(node * root){
	stack<node *> s;
	while( root != NULL || !s.empty() ){
		if( root != NULL ){
			s.push(root);
			root = root->left;
		}else{
			root = s.top();
			s.pop();
			cout << root->data << endl;
			root = root->right;
		}
	}
}
//测试
int main()
{
    /*  创建以下的树
            10
          /   \
        8      2
      /  \    /
    3     5  2
  */
  struct node *root = newNode(10);
  root->left        = newNode(8);
  root->right       = newNode(2);
  root->left->left  = newNode(3);
  root->left->right = newNode(5);
  root->right->left = newNode(2);
  iterativePreorder(root);
  return 0;
}

第一个用栈直接模拟的版本却并不容易实现。iterativePreorder 能够很好的执行的原因是,将左右节点压入栈后,根节点就再也用不着了;而中序和后序却不一样,左右节点入栈后,根节点后面还需要访问。因此三个节点都要入栈,而且入栈的先后顺序必须为:右节点,根节点,左节点。但是,当入栈以后,根节点与其左右子树的节点就分不清楚了。因此必须引入一个标志位,表示 是否已经将该节点的左右子树入栈了。每次入栈时,根节点标志位为true,左右子树标志位为false。

伪代码如下:

// 中序遍历伪代码:非递归版本,用栈实现,版本2
void InOrder1(TNode* root)
{
    Stack S;
    while ( root != NULL || !S.empty() )
    {
        while( root != NULL )   // 左子树入栈
        {
            S.push(root);
            root = root->left;
        }
        if ( !S.empty() )
        {
            root = S.pop();
            Visit(root->data);   // 访问根结点
            root = root->right;  // 通过下一次循环实现右子树遍历
        }
    }
}

参考:http://blog.csdn.net/kofsky/article/details/2886453/