두 가지 방식으로 두 갈래 나무를 옮겨다니기 - 귀속 방식과 비귀속 방식

귀속적인 방법으로 두 갈래 나무를 두루 훑어보는 것은 매우 간단하지만, 귀속적이지 않은 두 갈래 나무를 두루 훑어보는 것은 비교적 어렵다.비귀속 방법에서, 우리는 창고stack의 도움을 필요로 한다.다음은 각각 귀속방식과 비귀속방식으로 쓴 전, 중, 후 순서로 두 갈래 나무를 두루 훑어보는 방법으로 검증된 결과가 정확하다.
 

#include <iostream>

#include <stack>

using namespace std;

struct Node 

{

	int num;

	Node* pLeft;

	Node* pRight;

};

void insert(Node* &p,int num)

{

	Node* pTmp=new Node();

	pTmp->num=num;

	pTmp->pLeft=pTmp->pRight=NULL;



	if(p==NULL)

	{

		p=pTmp;

		return;

	}

	if(num<p->num)

		insert(p->pLeft,num);

	else if(num>p->num)

		insert(p->pRight,num);

	else

		return;



}

void PreOrder(Node* p)

{

	if(p==NULL)

		return;

	else

	{

		cout<<p->num<<" ";

		PreOrder(p->pLeft);

		PreOrder(p->pRight);

	}

}

void InOrder(Node* p)

{

	if (p==NULL)

		return;

	else

	{

		InOrder(p->pLeft);

		cout<<p->num<<" ";

		InOrder(p->pRight);

	}

}

void PostOrder(Node* p)

{

	if (p==NULL)

		return;

	else

	{

		PostOrder(p->pLeft);

		PostOrder(p->pRight);

		cout<<p->num<<" ";

	}

}

void PreOrderByLoop(Node* p)

{

	stack<Node*> MyStack;

	if(p==NULL)

		return;

	while(p!=NULL||!MyStack.empty())		//p 

	{

		while(p!=NULL)

		{

			MyStack.push(p);

			cout<<p->num<<" ";

			p=p->pLeft;

		}

		if(!MyStack.empty())		//  

		{

			p=MyStack.top();

			MyStack.pop();

			p=p->pRight;			//     

		}

	}

	cout<<endl;

}

void InOrderByLoop(Node* p)

{

	stack<Node*> Mystack;

	while(p!=NULL||!Mystack.empty())

	{

		while(p!=NULL)

		{

			Mystack.push(p);

			p=p->pLeft;

		}

		if(!Mystack.empty())

		{

			p=Mystack.top();

			Mystack.pop();

			cout<<p->num<<" ";

			p=p->pRight;

		}

	}

	cout<<endl;

}

void PostOrderByLoop(Node* p)

{

	stack<Node*> Mystack;

	Node* pre=NULL;						// 

	while(p!=NULL||!Mystack.empty())

	{

		while(p!=NULL)

		{

			Mystack.push(p);

			p=p->pLeft;

		}

		p=Mystack.top();

		if(p->pRight==NULL||p->pRight==pre)			//   

		{

			cout<<p->num<<" ";

			Mystack.pop();

			pre=p;

			p=NULL;									// 

		}

		else

			p=p->pRight;

	}

	cout<<endl;

}

void main()

{

	Node* p=NULL;

	insert(p,10);

	insert(p,6);

	insert(p,14);

	insert(p,4);

	insert(p,8);

	insert(p,12);

	insert(p,16);

	insert(p,1);

	insert(p,5);

	insert(p,15);

	insert(p,17);

	insert(p,7);

	insert(p,9);



 	cout<<"Preorder:"<<endl;

 	PreOrder(p);

	cout<<endl<<"preorderbyLoop:"<<endl;

	PreOrderByLoop(p);



	cout<<endl<<"Inorder:"<<endl;

	InOrder(p);

	cout<<endl<<"InorderbyLoop:"<<endl;

	InOrderByLoop(p);



	cout<<endl<<"Postorder:"<<endl;

	PostOrder(p);

	cout<<endl<<"PostOrderByLoop:"<<endl;

	PostOrderByLoop(p);

}