C++ 스택을 이용한 트리 전위순회 (Tree C++ with Stack)

재귀함수를 사용하지 않고 STL 스택으로 트리 전위 순회하기

*재귀함수의 이해

/* 자료구조 이진트리 스택으로 구현 (재귀 사용 x) - 2019/12/29 xtar.tistory */

#include <iostream>
#include <stack>
using namespace  std;

template <typename T>
class Node
{
	T vaule;
	Node* left;
	Node* right;
	Node* root;
public:
	Node() : vaule(0), left(nullptr), right(nullptr), root(nullptr) {};
	Node(T _value) :vaule(_value), right(nullptr), root(nullptr) {};
	Node(T _value, Node* _left, Node* _right) : vaule(_value), left(_left), right(_right), root(nullptr)
	{
		//만약 왼쪽 오른쪽노드가 있다면 현재 노드가 부모
		if (nullptr != _left)
			_left->root = this;
		if (nullptr != _right)
			_right->root = this;
	};

	~Node() {};

	void SetLeft(Node* node) { this->left = node; }
	void SetRight(Node* node) { this->right = node; }
	Node* GetLeft() { return left; }
	Node* GetRight() { return right; }
	T GetValue() { return vaule; }
};

//순회함수-스택
template <typename T>
void Preorder(Node<T>* node) //전위
{
	stack<Node<T>*> _stack;
	_stack.push(node);

	while (_stack.size() > 0)
	{
		Node<T>* ptr = _stack.top();
		_stack.pop();

		cout << ptr->GetValue() << " ";
		Node<T>* n = ptr->GetRight();

		if (n != nullptr)
			_stack.push(n);
		n = ptr->GetLeft();
		if (n != nullptr)
			_stack.push(n);
	}
}


int main()
{
	//노드 초기화
	Node<int>* node1 = new Node<int>(1);
	Node<int>* node2 = new Node<int>(2);
	Node<int>* node3 = new Node<int>(3);
	Node<int>* node4 = new Node<int>(4, node1, node2);

	Node<int>* node5 = new Node<int>(5);
	Node<int>* node6 = new Node<int>(6);

	//트리 자식 설정
	node1->SetLeft(node3);
	node1->SetRight(node5);
	node2->SetRight(node6);

	//순회별 출력
	cout << "전위(Preorder):: ";
	Preorder(node4);

	return 0;
}