이진 트리(Binary Tree)

가계도와 같은 계층적인 구조를 표현할 때 사용할 수 있는 자료 구조

👀 특징

• 기본적으로 가장 많이 사용되는 비선형 자료구조
• 왼쪽과 오른쪽으로만 자식 트리가 구성되는 경우
• 데이터의 탐색 속도 증진을 위해 사용한다.

보통 이렇게 생겼다. 물론 매번 완전한 이진트리가 아닐 수도 있다.

🔨 데이터를 탐색하는 방법

• 포인터를 사용하여 왼쪽 자식과 오른쪽 자식을 가리킬 수 있도록 했다.
• 포인터를 이용하면 완전 이진트리가 아니더라도 안정적으로 탐색이 가능하다.

전위 순회 Preorder Traversal

1. 자기 자신을 처리
2. 왼쪽 자식을 방문
3. 오른쪽 자신을 방문

public void Preorder(Node node) {
	if (node!=null) {
    	System.out.println(node.data);
		preorder(node.left); // 왼쪽 재귀함수
        preorder(node.right); // 오른쪽 재귀함수
	}
}

중위 순회 Inorder Traversal

1. 왼쪽 자식 방문
2. 자기 자신 처리
3. 오른쪽 자식 방문

public void inorder(Node node) {
	if (node!=null) {
		inorder(node.left); // 왼쪽 재귀함수
        System.out.println(node.data);
        inorder(node.right); // 오른쪽 재귀함수
	}
}

후위 순회 Postorder Traversal

계산기와 같이 수식이 있고, 컴퓨터가 이를 처리할 때 주로 사용

1. 왼쪽 자식 방문
2. 오른쪽 자식 방문
3. 자기 자신 처리

public void Postorder(Node node) {
	if (node!=null) {
		postorder(node.left); // 왼쪽 재귀함수
        postorder(node.right); // 오른쪽 재귀함수
        System.out.println(node.data);
	}
}

👿 관련 문제

• 백준: 1991 트리 순회

🖇️ 참고 자료

• 이것이 취업을 위한 코딩테스트다