2014
06-17

二叉树非递归中序遍历

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

#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;
}

// 中序遍历伪代码：非递归版本，用栈实现，版本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;  // 通过下一次循环实现右子树遍历
}
}
}