[자료구조] 재귀를 이용한 트리운행/스택을 이용한 트리운행

hyo-ue4study.tistory.com/111

[자료구조]트리(Tree) 특징 / 운행 3가지 / C++

#include<iostream>
#include<stack>
#include<algorithm>
using namespace std;
class Node {
public:
	Node()
		: mData(0)
		, mLeft(nullptr)
		, mRight(nullptr)
		, mRoot(nullptr)
	{}

	Node(int data)
		: mData(data)
		, mLeft(nullptr)
		, mRight(nullptr)
		, mRoot(nullptr)
	{}

	void PrintData()
	{
		cout << mData << "/";
	}


	Node* mLeft;
	Node* mRight;
	Node* mRoot;

private:
	int mData;
};

void PostOrder(Node* node)
{
	if (node == nullptr)
	{
		return;
	}
	PostOrder(node->mLeft);
	PostOrder(node->mRight);
	node->PrintData();
}

void PostOrderStack(Node* node)
{
	if (node == nullptr)
	{
		return;
	}

	cout << "스택 : ";
	stack<Node*> st;
	Node* tempNode = node;
	Node* doneNode = nullptr;
	while (1)
	{
		if (tempNode != nullptr && tempNode != doneNode)
		{
			st.push(tempNode);
			do
			{
				if (tempNode->mRight != nullptr)
				{
					st.push(tempNode->mRight);
				}

				if (tempNode->mLeft != nullptr)
				{
					st.push(tempNode->mLeft);
				}

				tempNode = tempNode->mLeft;
			} while (tempNode != nullptr);
		}
		if (!st.empty())
		{
			tempNode = st.top();
			st.pop();
			//예외 처리          
			if (tempNode->mLeft != NULL && tempNode->mRight == NULL && tempNode->mLeft != doneNode)
			{
				if (tempNode != nullptr)
					st.push(tempNode);
				tempNode = tempNode->mLeft;
			}


			if (tempNode->mRight == NULL || tempNode->mRight == doneNode)
			{
				//노드 데이터 출력
				tempNode->PrintData();

				//완료 노드로 지정
				doneNode = tempNode;
			}
		}
		else
			break;
	}

	cout << endl;
}

//중위 운행
void InOrder(Node* node)
{
	if (node == nullptr)
	{
		return;
	}
	InOrder(node->mLeft);
	node->PrintData();
	InOrder(node->mRight);
}
void InOrderStack(Node* node)
{
	cout << "스택 : ";
	if (node == nullptr)
	{
		return;
	}
	stack<Node*> st;

	Node* temp = node;

	while (1) {
		while (temp != nullptr)//제일 좌측 노드로 
		{
			st.push(temp);
			temp = temp->mLeft;
		}
		if (!st.empty())
		{
			temp = st.top();
			st.pop();

			temp->PrintData();
			temp = temp->mRight;
		}
		else
		{
			break;
		}
	}
	cout << endl;

}
//전위 운행
void PreOrder(Node* node)
{
	if (node == nullptr)
	{
		return;
	}
	node->PrintData();
	PreOrder(node->mLeft);
	PreOrder(node->mRight);
}

void PreOrderStack(Node* node)
{
	if (node == nullptr)
	{
		return;
	}
	stack<Node*> st;

	cout << "스택 : ";
	st.push(node);
	while (!st.empty())
	{
		Node* curNode = st.top();
		curNode->PrintData();
		st.pop();

		if (curNode->mRight != nullptr)
			st.push(curNode->mRight);
		if (curNode->mLeft != nullptr)
			st.push(curNode->mLeft);
	}
	cout << endl;
}



int main()
{

	Node* root = new Node(0);
	Node* node1 = new Node(1);
	Node* node2 = new Node(2);
	Node* node3 = new Node(3);
	Node* node4 = new Node(4);



	root->mLeft = node1;
	root->mRight = node2;

	node1->mLeft = node3;
	node1->mRight = node4;

	cout << "전위 운행 : " << endl;
	cout << "재귀 : ";
	PreOrder(root);
	cout << endl;

	PreOrderStack(root);
	cout << "------------" << endl;

	cout << "중위 운행 : " << endl;
	cout << "재귀 : ";
	InOrder(root);
	cout << endl;
	InOrderStack(root);
	cout << "------------" << endl;


	cout << "후위 운행 : " << endl;
	cout << "재귀 : ";
	PostOrder(root);
	cout << endl;
	PostOrderStack(root);
	cout << "------------" << endl;
	return 0;
}

 

입력 된 트리 구성

 

 

결과