学步园

/*
43.递归和非递归俩种方法实现二叉树的前序遍历。
*/

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<stack>
#include<queue>  
using namespace std;
#define MAX 20

struct BTreeNode{
	int data;
	BTreeNode *left,*right;
}; 

//建立二叉树 
BTreeNode * CreateTree(int data[],int pos,int len)
{
	BTreeNode *tree;
	if(pos>=len) 
	{
		return NULL;
	}
	else
	{
		tree=(BTreeNode *)malloc(sizeof(BTreeNode));
		tree->data=data[pos];
		tree->left=CreateTree(data,2*pos+1,len);//数组坐标 
		tree->right=CreateTree(data,2*pos+2,len);
		return tree;
	}
	
}

// 递归版本比较简单 
void preOrder(BTreeNode *tree)
{
	if(tree!=NULL)
	{
		printf("%d ",tree->data);
		preOrder(tree->left);
		preOrder(tree->right);
	}
}

void preorderNonrecursive(BTreeNode *tree) 
{
	stack<BTreeNode* > s;
	s.push(tree);
	while(!s.empty()) 
	{
		BTreeNode* n;
		n=s.top();
		s.pop();
		printf("%d ",n->data);//因为是栈，所以先如右边的，后左边的，则先出左边的 
		if(n->right!=NULL) s.push(n->right);
		if(n->left!=NULL) s.push(n->left);		
	}
}


void inorderNonrecursive(BTreeNode* tree) //左根右 
{
	stack<BTreeNode* > s;
	BTreeNode* current=tree;
	
	while(!s.empty()||current!=NULL) 
	{
		if(current!=NULL) 
		{
			s.push(current);// 根先进，在继续左孩子，直到为空 
			current=current->left;
		}
		else 
		{
			current=s.top();
			s.pop();
			printf("%d ",current->data);// 根 
			current=current->right;//右 
		}
	}
}


void postorderNonrecursive(BTreeNode * tree) //左右根 
{
	// visiting occurs only when current has no right child 
	//or last visited is his right child
	stack<BTreeNode *> sTraverse, sVisit;
	sTraverse.push(tree);
	while (!sTraverse.empty()) 
	{
		BTreeNode* p=sTraverse.top();
		sTraverse.pop();
		 
		sVisit.push(p);//左右根 根先进 右进 左进
		if (p->left!=NULL) sTraverse.push(p->left); 
		if (p->right!=NULL) sTraverse.push(p->right);
	}
	while(!sVisit.empty()) 
	{
		printf("%d ",sVisit.top()->data);
		sVisit.pop();
	}
}

int main(){
	/*
			8
		 6     10
	  5   7   9 11
	12 3 1 2 4
	
	前：8 6 5 12 3 7 1 2 10 9 4 11 
	中：12 5 3 6 1 7 2 8 4 9 10 11 
	后：12 3 5 1 2 7 6 4 9 11 10 8 
	*/
	int data[]={8,6,10,5,7,9,11,12,3,1,2,4};
	int len=sizeof(data)/sizeof(int);
	
	BTreeNode *tree=CreateTree(data,0,len);

	printf("前序遍历(递归)：\n");//根左右 
	preOrder(tree);printf("\n");
	printf("前序遍历（非递归）：\n");//根左右 
	preorderNonrecursive(tree);printf("\n");
	
	printf("中序遍历（非递归）：\n");//左根右 
	inorderNonrecursive(tree);printf("\n");
	
	printf("后序遍历（非递归）：\n");//左右根 
	postorderNonrecursive(tree);printf("\n");
	
	return 0;
}