Binary Tree

Traversal

• Traversal이란 Tree 내부의 모든 노드를 1번씩 방문 하여 값을 확인할 수 있도록 하는 것
• 선형 자료구조는 단방향의 순회만 가능하지만 Tree 구조에서는 여러 방향의 순회 방법을 사용할 수 있음
• 각각의 노드가 각자의 left와 right에 해당하는 포인터를 갖고 있으므로 재귀 방식을 통해 단순한 코드로 순회를 구현할 수 있음
• Preorder, Inorder, Postorder 방법이 있으며 순서가 중요하지 않다면 셋 중 어떤 것을 사용해도 관계 없음

1. Preorder Traversal

• root → left → right 순서로 방문
  
• 자식 노드를 방문하기 전에 해당 노드의 부모 노드를 무조건 방문해야 하는 경우 사용
  Ex) 모든 노드의 레벨을 확인할 때(자식 노드들은 부모 노드보다 레벨이 1 높기 때문)

2. Inorder Traversal

• left → root → right 순서로 방문
  

3. Postorder Traversal

• left → right → root순서로 방문
  
• 자식 노드를 먼저 방문해야 하는 경우에 사용
  Ex) 저장공간 크기 측정, Binary Tree의 메모리 해제

순회 방식 구현

1. Tree Class에서 구현

• Tree 클래스에서 모든 노드들은 관망하며 관리
• 재귀 방식을 사용하지만 외부에서 관리됨
  Like 선생님이 모든 학생의 이름을 순서대로 부르는 것

	void inorder(BinaryNode *node) {
		if( node != NULL ) {
			if( node->getLeft() != NULL ) inorder(node->getLeft());
			printf( " [%c] ", node->getData());
			if( node->getRight()!= NULL ) inorder(node->getRight());
		}
	}
	void preorder(BinaryNode *node) {
		if( node != NULL ) {
			printf( " [%c] ", node->getData());
			if( node->getLeft() != NULL ) preorder(node->getLeft());
			if( node->getRight()!= NULL ) preorder(node->getRight());
		}
	}
	void postorder(BinaryNode *node) {
		if( node != NULL ) {
			if( node->getLeft() != NULL ) postorder(node->getLeft());
			if( node->getRight()!= NULL ) postorder(node->getRight());
			printf( " [%c] ", node->getData());
		}
	}

• 매개변수로 시작 노드를 지정

2. Node Class에서 구현

• Node가 자신의 다음 노드들을 순차적으로 순회
• 모든 노드가 각각의 책임을 갖고 재귀적으로 다음 노드를 호출
• 캡슐화에 유리
  Like 학생들이 서로 자신 다음에 있는 학생의 출석을 확인

	void inorder(BinaryNode *node)
	{
		if (node != NULL)
		{
			node->inorder();
		}
	}
	void preorder(BinaryNode *node)
	{
		if (node != NULL)
		{
			node->preorder();
		}
	}
	void postorder(BinaryNode *node)
	{
		if (node != NULL)
		{
			node->postorder();
		}
	}

• 구체적인 로직은 노드에 구현하고 트리에서는 함수를 호출하기만 함

추가

4. Level-Order Traversal

• 일반적인 순회 방법은 아니지만 BFS 탐색을 위해 필요
• 같은 레벨에 있는 노드들을 순회
• 앞선 3개의 순회 방법은 재귀 방식으로 구현할 수 있지만 (내부적으로 Stack을 사용) Level-Order는 Queue를 사용해야함
• 한 노드가 dequeue될 때, 해당 노드의 자식들을 enqueue
• 자식이 없다면 enqueue하지 않고 있다면 left-right순서로 처리
• 이러한 과정을 Queue가 빌 때까지 반복
• Tree에서 구현하는 것은 쉽지만 노드 내부에 Level-Order를 구현하는 것은 어려움
  (전체 과정을 총괄하는 Queue가 필요하기 때문)