[알고리즘] 이진 트리 (Binary Tree)

[알고리즘] 이진 트리 (Binary Tree)

---

이진트리는 기본적으로 많이 사용되는 비선형 자료구조이다. 기존에 힙에서도 이진트리를 사용했는데 그것은 완전 이진 트리로 배열로 표현이 가능하지만 완전 이진 트리가 아닌 경우는 배열로 표현이 힘들다.

이진 트리의 구조

시간 복잡도

이진트리를 탐색 시 계속 1/2로 나뉘어서 계속 탐색하기 때문에 O(log₂N)의 복잡도를 가진다. 

이진 트리 탐색 방법

1. 전위 순회 (Preorder Traversal) : 자기 자신 - 왼쪽 자식 - 오른쪽 자식

2. 중위 순회 (Inorder Traversal) : 왼쪽 자식 - 자기 자신 - 오른쪽 자식

3. 후위 순회 (Postorder Traversal) : 왼쪽 자식 - 오른쪽 자식 - 자기 자신

후위 순회는 계산기와 같은 수식에 자주 사용된다.

다음 이진트리를 탐색해보자!

전위 순회

0 → 1 → 3 → 4 → 2 → 5 → 6

중위 순회

3 → 1 → 4 → 0 → 5 → 2 → 6

후위 순위

3 → 4 → 1 → 5 → 6 →  2 → 0

소스코드 구현 (C++)

#include <iostream>
using namespace std;
//노드 구조체
struct Node {
	int data;
	Node* leftChild;
	Node* rightChild;
};

//전위 순회
void Preorder(Node* ptr)
{
	if (ptr)
	{
		cout << ptr->data << ' ';
		Preorder(ptr->leftChild);
		Preorder(ptr->rightChild);
	}
}

//중위 순회
void Inorder(Node* ptr)
{
	if (ptr)
	{
		Inorder(ptr->leftChild);
		cout << ptr->data << ' ';
		Inorder(ptr->rightChild);
	}
}

//후위 순회
void Postorder(Node* ptr)
{
	if (ptr)
	{
		Postorder(ptr->leftChild);
		Postorder(ptr->rightChild);
		cout << ptr->data << ' ';
	}
}
int main()
{
	//노드 생성
	Node nodes[8];
	for (int i = 1; i < 8; i++)
	{
		nodes[i].data = i;
		nodes[i].leftChild = NULL;
		nodes[i].rightChild = NULL;
		//cout << nodes[i].data << endl;
	}
	//노드 넣어주기
	for (int i = 1; i < 8; i++)
	{
		if (i % 2 == 0)
		{
			nodes[i / 2].leftChild = &nodes[i];
		}
		else
		{
			nodes[(i / 2)].rightChild = &nodes[i];
		}
	}
	//출력
	cout << "Preorder [ ";
	Preorder(&nodes[1]);
	cout << "]" << endl;

	cout << "Inorder [ ";
	Inorder(&nodes[1]);
	cout << "]" << endl;

	cout << "Postrder [ ";
	Postorder(&nodes[1]);
	cout << "]" << endl;

	return 0;
}

출력 결과

---

완전 이진트리가 아닐 경우를 위해서 포인터를 이용하여 이진트리를 구현해보았다. 이진트리는 O(log₂N)의 시간복잡도를 갖는 것과 세가지의 탐색방법이 있다는 것을 알아두자!!!