Algorithm 공부 #20 - 이진 트리(Binary Tree)

 

Algorithm 공부 #20 - 이진 트리

 

 

이진 트리(Binary Tree)

  ● 각 노드의 자식 노드의 개수가 2개 이하인 트리

  ● 편리하고 직관적인 자료구조 형태는 배열

  ● 이진 트리의 종류

      1. 편향 이진 트리 : 트리의 노드들이 한쪽 방향으로만 편향돼 생성된 트리, 탐색 속도가 저하되고 공간이 많이 낭비

      2. 포화 이진 트리 : 트리의 높이가 모두 일정하며 리프 노드가 모두 꽉 찬 트리

      3. 완전 이진 트리 : 마지막 레벨을 제외하고 완전하게 노드들이 채워져 있고, 마지막 레벨은 왼쪽부터 채워진 트리

  ● 이진 트리의 순차 표현

      1. 루트 노드 : index = 1;

      2. 부모 노드 : index = index / 2;  (단, 현재 노드가 루트 노드가 아닐 때)

      3. 왼쪽 자식 노드 : index = index * 2; (단 index*2<=N일 때)

      4. 오른쪽 자식 노드 : index = index *2 + 1; (단, index * 2 + 1 <=N일 때)

       

 

백준 1991번 트리 순회

https://www.acmicpc.net/problem/1991

1991번: 트리 순회

 ● 이차원 배열로 이진 트리 구현 후 탐색하기

#include<iostream>
using namespace std;

int tree[26][2];
int N;
void postorder(int root);
void inorder(int root);
void preorder(int root);
int main() {
	
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;
	for (int i = 0; i < N; i++) {
		char first, left, right;
		cin >> first >> left >> right;
		int node = first - 'A';
		if (left == '.')
			tree[node][0] = -1;
		else
			tree[node][0] = left - 'A';
		if (right == '.')
			tree[node][1] = -1;
		else
			tree[node][1] = right - 'A';
		
	}
	preorder(0);
	cout << '\n';
	inorder(0);
	cout << '\n';
	postorder(0);
	cout << '\n';
}
void preorder(int root) {
	if (root == -1)
		return;

	cout << (char)(root + 'A');
	preorder(tree[root][0]);
	preorder(tree[root][1]);
}
void inorder(int root) {
	if (root == -1)
		return;
	inorder(tree[root][0]);
	cout << (char)(root + 'A');	
	inorder(tree[root][1]);
}
void postorder(int root) {
	if (root == -1)
		return;

	postorder(tree[root][0]);
	postorder(tree[root][1]);
	cout << (char)(root + 'A');

}