데이터 구조의 이 진 트 리 의 비 재 귀적 옮 겨 다 니 기

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

#include "stdafx.h"
#include "stdio.h"
#include "iostream"
#include "stack"

using namespace std;

typedef struct node
{
	int data;
	struct node *lchild;
	struct node *rchild;
}BiTNode, *BiTree;

int CreateBiTree(BiTree &T);
int CreateBiTree(BiTree &T,int &index);
void PreOrder(BiTree root);
void InOrder(BiTree root);
void PostOrder(BiTree root);
int InOrderTraverse(BiTree root);
int InOrderTraverse2(BiTree root);

int element[]={3,7,3,2,1,0,0,7,0,0,0,8,0,10,0,0,17,18,0,0,19,0,27,0,0};
static int index=0;
stack<BiTree> S; //          
int _tmain(int argc, _TCHAR* argv[])
{
	
	BiTree tree;
	//         
	CreateBiTree(tree,index);
	printf("       
");
	printf("    
");
	PreOrder(tree);
	printf("
");
	printf("       
");
	InOrder(tree);
	printf("
");
	printf("        
");
	PostOrder(tree);
	printf("
");
	printf("           
");
	InOrderTraverse(tree);
	printf("
");
	printf("           ,  2
");
	InOrderTraverse2(tree);
	printf("
");

	system("pause");
	return 0;
}

//       ，        
int CreateBiTree(BiTree &T)
{
	int data;
	scanf("%d",&data);
	if (data==0) // 0       
	{
		T=NULL;
	}
	else
	{
		T=(BiTree)malloc(sizeof(BiTNode));
		if (!T)
		{
			return -1;
		}
		else
		{
			T->data=data;
			CreateBiTree(T->lchild);
			CreateBiTree(T->rchild);
		}
	}
	return 1;
}

//       ，        ,             
int CreateBiTree(BiTree &T,int &index)
{
	int data=element[index];
	if (data==0) // 0       
	{
		T=NULL;
	}
	else
	{
		T=(BiTree)malloc(sizeof(BiTNode));
		if (!T)
		{
			return -1;
		}
		else
		{
			T->data=data;
			CreateBiTree(T->lchild,++index);
			CreateBiTree(T->rchild,++index);
		}
	}
	return 1;
}

//        
void PreOrder(BiTree root)
{
	if (root!=NULL)
	{
		printf("%3d",root->data);
		PreOrder(root->lchild);
		PreOrder(root->rchild);
	}
}

//     
void InOrder(BiTree root)
{
	if (root!=NULL)
	{
		InOrder(root->lchild);
		printf("%3d",root->data);
		InOrder(root->rchild);
	}
}

//     
void PostOrder(BiTree root)
{
	if (root!=NULL)
	{
		PostOrder(root->lchild);
		PostOrder(root->rchild);
		printf("%3d",root->data);
	}
}

//          ，    ,  1
int InOrderTraverse(BiTree root)
{
	S.push(root);
	BiTree p;
	while(!S.empty())
	{
		while((p=S.top())&&p) //          
		{
			S.push(p->lchild); //       ,           
		}
		S.pop(); //      
		if (!S.empty())
		{
			p=S.top(); 
			S.pop();//             
			printf("%3d",p->data);  //     
			S.push(p->rchild); //       ，            
		}
	}
	return 1;
}

//         ，    ，  2
int InOrderTraverse2(BiTree root)
{
	stack<BiTree> S;
	BiTree p=root;
	//         ，      ,             ，       
	while(p||!S.empty())
	{
		if (p) //      
		{
			S.push(p); //          ,        
			p=p->lchild;
		}
		else
		{
			//       ,               
			p=S.top();
			S.pop(); //       ，      ，         
			printf("%3d",p->data);
			p=p->rchild; //              ，              
		}
	}
	return 1;
}