二叉树先序、中序、后续遍历（非递归实现）

二叉树遍历的非递归形式，主要是依靠 栈 来实现的：

对于二叉树的先序遍历，先将根结点压入栈中，然后将树中所有的左子树压入栈中同时访问其值，对于最后一个左子树压入栈中后，它的左子树为NULL ；访问它的右子树，并从栈中将其退出，再以它的右子树为根结点的形式进行访问，当栈中元素第一次全部清空之后，若根结点的右子树不为空，继续进行进栈操作，直到栈再次为空且右子树为NULL时结束；

#include<iostream>
#include<stdio.h>
#include<stack>
#include<string.h>
#include<stdlib.h>
using namespace std ;

struct Node	{
	int data ;
	Node *left ;
	Node *right ;
};

Node* newnode()	{
	Node *root = new Node ;
	root->left = NULL ;
	root->right = NULL ;
	return root ;
};


int main()	{
	Node *root = newnode() ;
	char s[100] ;
	while(cin >> s )	{
		Node *t = root ;
		if(strcmp(s,"()") == 0 )
			break ;
		int data ;
		sscanf(&s[1],"%d",&data);
		char *s1 = (strchr(s,‘,‘)+1) ;
		int len = strlen(s1) ;
		for(int i = 0 ; i < len ; i++)	{
			if(s1[i] == ‘L‘)	{
				if((t->left) == NULL)
					t->left = newnode() ;
				t = t -> left ;
			}	
			else if(s1[i] == ‘R‘)	{
				if((t->right) == NULL)
					t->right = newnode() ;
				t = t -> right ;
			}
		}
		t -> data = data ;
	}
	stack<Node*> ss ;
	Node *r = root ;
	while((!ss.empty())||r!=NULL)	{
		while(r != NULL)	{
			cout << r->data << " ";
			ss.push(r);
			r = r->left ;
			}
		r = ss.top() ;
		r = r->right ;
		ss.pop();
	}
	cout << endl ;
	return 0 ;
}


	

二叉树先序、中序、后续遍历（非递归实现）,布布扣,bubuko.com

二叉树先序、中序、后续遍历（非递归实现）

原文：http://blog.csdn.net/ding_hai_long/article/details/21104081