트리 순회

일단 트리가 구성되어 있따면, 이 트리를 다양한 방법으로 순회하여 원하는 노드에 접근할 수 있습니다. 다양한 순회 방법에 대해 간략히 알아보겠습니다.

전위 순회(pre-order traversal)

이 방법은 현재 노드를 먼저 방문하고, 그다음은 현재 노드의 왼쪽 하위 노드를, 마지막으로는 현재 노드의 오른쪽 하위 노드를 재귀적인 방식으로 방문합니다.

 

중위 순회(in-order traversal)

왼쪽 노드를 먼저 방문하고, 그다음에 현재 노드, 마지막으로 오른쪽 노드를 방문합니다.

 

후위 순회(post-order traversal)

두 자식 노드를 먼저 방문한 후, 현재 노드를 방문합니다.

 

레벨 순서 순회(level-order traversal)

트리의 맨 위 레벨부터 아래 레벨까지, 왼쪽 노드에서 오른쪽 노드 순서로 방문합니다. 즉 트리의 루트 노드부터 단계별로 차례대로 나열하는 것과 같습니다.

 

코드로 구현해보겠습니다.

이전 글의 struct org_tree 구조체 안에 작성하면 됩니다.

// 전위 순회
	static void preOrder(node* start)
	{
		if (!start)
			return;

		std::cout << start->position << ", ";
		preOrder(start->first);
		preOrder(start->second);
	}

	// 중위 순회
	static void inOrder(node* start)
	{
		if (!start)
			return;

		inOrder(start->first);
		std::cout << start->position << ", ";
		inOrder(start->second);
	}

	// 후위 순회
	static void postOrder(node* start)
	{
		if (!start)
			return;

		postOrder(start->first);
		postOrder(start->second);
		std::cout << start->position << ", ";
	}
    
    // 레벨 순서 순회
	static void levelOrder(node* start)
	{
		if (!start)
			return;

		std::queue<node*> q;
		q.push(start);

		while (!q.empty())
		{
			int size = q.size();
			for (int i = 0; i < size; i++)
			{
				auto current = q.front();
				q.pop();

				std::cout << current->position << ", ";
				if (current->first)
					q.push(current->first);
				if (current->second)
					q.push(current->second);
			}

			std::cout << std::endl;
		}

	}

 

전체코드

#include <iostream>
#include <queue>

struct node
{
	std::string position;
	node* first;
	node* second;
};

struct org_tree
{
	node* root;

	// 새로운 트리를 만드는 정적 함수
	static org_tree create_org_structure(const std::string& pos)
	{
		org_tree tree;
		tree.root = new node{ pos, NULL, NULL };
		return tree;
	}

	// 특정 직책 이름에 해당하는 노드를 찾아서 반환하는 함수
	static node* find(node* root, const std::string& value)
	{
		if (root == NULL)
			return NULL;

		if (root->position == value)
			return root;

		auto firstFound = org_tree::find(root->first, value);

		if (firstFound != NULL)
			return firstFound;

		return org_tree::find(root->second, value);
	}

	// 루트 노드의 first와 second 둘 중 빈 곳이 있으면 값을 삽입하는 함수
	bool addSubordinate(const std::string& manager, const std::string& subordinate)
	{
		auto managerNode = org_tree::find(root, manager);

		if (!managerNode)
		{
			std::cout << manager << "을(를) 찾을 수 없습니다: " << std::endl;
			return false;
		}

		if (managerNode->first && managerNode->second)
		{
			std::cout << manager << " 아래에 " << subordinate << "을(를) 추가할 수 없습니다." << std::endl;
			return false;
		}
		if (!managerNode->first)
			managerNode->first = new node{ subordinate, NULL, NULL };
		else
			managerNode->second = new node{ subordinate, NULL, NULL };

		std::cout << manager << " 아래에 " << subordinate << "을(를) 추가했습니다." << std::endl;

		return true;
	}
	// 전위 순회
	static void preOrder(node* start)
	{
		if (!start)
			return;

		std::cout << start->position << ", ";
		preOrder(start->first);
		preOrder(start->second);
	}

	// 중위 순회
	static void inOrder(node* start)
	{
		if (!start)
			return;

		inOrder(start->first);
		std::cout << start->position << ", ";
		inOrder(start->second);
	}

	// 후위 순회
	static void postOrder(node* start)
	{
		if (!start)
			return;

		postOrder(start->first);
		postOrder(start->second);
		std::cout << start->position << ", ";
	}

	static void levelOrder(node* start)
	{
		if (!start)
			return;

		std::queue<node*> q;
		q.push(start);

		while (!q.empty())
		{
			int size = q.size();
			for (int i = 0; i < size; i++)
			{
				auto current = q.front();
				q.pop();

				std::cout << current->position << ", ";
				if (current->first)
					q.push(current->first);
				if (current->second)
					q.push(current->second);
			}

			std::cout << std::endl;
		}

	}
	
};

int main()
{
	auto tree = org_tree::create_org_structure("CEO");

	tree.addSubordinate("CEO", "부사장");       
	tree.addSubordinate("부사장", "IT부장");
	tree.addSubordinate("부사장", "마케팅부장");
	tree.addSubordinate("IT부장", "보안팀장");
	tree.addSubordinate("IT부장", "앱개발팀장");
	tree.addSubordinate("마케팅부장", "물류팀장");
	tree.addSubordinate("마케팅부장", "홍보팀장");
	tree.addSubordinate("부사장", "재무부장");

	std::cout << std::endl << " 전위 순회" << std::endl;
	org_tree::preOrder(tree.root);
	std::cout << std::endl << "---------------------------------------------------------------------------------------" << std::endl;

	std::cout << std::endl << " 중위 순회" << std::endl;
	org_tree::inOrder(tree.root);
	std::cout << std::endl << "---------------------------------------------------------------------------------------" << std::endl;

	std::cout << std::endl << " 후위 순회" << std::endl;
	org_tree::postOrder(tree.root);
	std::cout << std::endl << "---------------------------------------------------------------------------------------" << std::endl;

	std::cout << std::endl << " 레벨 순서 순회" << std::endl;
	org_tree::levelOrder(tree.root);  
	std::cout << std::endl << "---------------------------------------------------------------------------------------" << std::endl;

	
}

실행결과