비귀속 실현 전순, 중순, 후순 두 갈래 트리

// test2.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<iostream>
#include<stack>
using namespace std;

struct ListNode{
	int val;
	ListNode * left;
	ListNode * right;
	ListNode(int x):val(x),left(NULL),right(NULL){
	}
};

void PreTraverseTree(ListNode *root)
{
	if(root == NULL)
		return;
	stack<ListNode *> stack;
	ListNode *p = root;
	stack.push(p);	
	while(!stack.empty())
	{
		while(p)
		{
			stack.push(p);
			cout<<p->val<<"  ";
			p = p->left;
		}
		 p = stack.top();
		 stack.pop();
		 p = p->right;		
	}
}


void InTraverseTree(ListNode * root)
{
	if(root == NULL)
		return;
	stack<ListNode *> stack;
	ListNode *p = root;	
	while(p || !stack.empty())
	{	
		
		while(p)
		{
			stack.push(p);
			p = p->left;
		}
		p = stack.top();
		stack.pop();
		cout<<p->val<<" ";
		p = p->right;
	}
}

void PostTraverseTree(ListNode *root)
{
	if(root == NULL)
		return ;
	stack<ListNode*> stack;
	int flag[20];
	ListNode *p = root;
	while(p)
	{
		stack.push(p);
		flag[stack.size()] = 0;
		p = p->left;
	}
	
	while(!stack.empty())
	{
		p = stack.top();
		while(p->right && flag[stack.size()] == 0)
		{
	    	p = p->right;
			flag[stack.size()] = 1;
	    	while(p)
			{
		    	stack.push(p);
		      	flag[stack.size()] = 0;
		    	p = p->left;
			}
			p = stack.top();
		}
    	p = stack.top();		
	    cout<<p->val<<"   ";
	    stack.pop();
	}

}

int main(int argc, char* argv[])
{
	ListNode * root = new ListNode(10);
	root->left = new ListNode (5);
	root->right = new ListNode(11);
	root->left->right = new ListNode(6);

	cout<<"PreOrderTraverseTree:";
	PreTraverseTree(root);
	cout<<endl;
	cout<<"InOrerTraverseTree:";
	InTraverseTree(root);
	cout<<endl;
	cout<<"PostOrderTraverseTree:";
	PostTraverseTree(root);


	return 0;
}