𝘽𝙞𝙣𝙖𝙧𝙮 𝙏𝙧𝙚𝙚

uuuouuo·2022년 7월 21일

이분트리 트리

📖 이분 트리

특징

모든 노드들이 2개의 부트리를 갖는 트리
노드가 자식 노드를 최대한 2개까지만 가질 수 있는 트리
- 왼쪽 자식 노드, 오른쪽 자식 노드가 있음
레벨 i에서의 노드의 최대 개수는 2^i
-높이가 h인 이분 트리가 가질 수 있는 노드의 최소 개수는 (h+1)개, 최대 개수는 (2^h+1-1)개

💬 종류

Full Binary Tree (포화 이진 트리)
Complete Binary Tree (완전 이진 트리)
Skewed Binary Tree (편향 이진 트리)

◾ Full Binary Tree (포화 이진 트리)

최대 노드 개수인 (2^h+1-1)의 노드를 가진 이진 트리
루트를 1번으로 해서 (2^h+1-1)까지 정해진 위치에 대한 노드 번호 가짐

◾ Complete Binary Tree (완전 이진 트리)

높이가 h이고 노드의 수가 n개 일 때 (단, h+1 <= n < (2^h+1-1)) Full Binary Tree의 노드가 1번부터 n번까지 빈자리가 없는 이진 트리
노드가 10개인 완전 이진 트리

◾ Skewed Binary Tree (편향 이진 트리)

높이 h에 대한 최소 개수의 노드를 가지면서 한쪽 방향의 자식 노드만 가진 이진 트리

💬 순회

트리의 각 노드를 중복되지 않게 전부 방문하는 것을 말함
트리는 비선형 구조라서 선형 구조에서와 같이 선후 연결 관계를 알 수 없음

3가지 기본적인 순회 방법

전위 순회 (Preorder traversal)
중위 순회 (Inorder traversal)
후위 순회 (Postorder traversal)

◾ 전위 순회 (Preorder traversal)

VLR (루트-왼쪽-오른쪽)
자손 노드보다 루트 노드를 먼저 방문
수행 방법
- 현재 노드 n 방문 : V
- 현재 노드 n의 왼쪽 부트리 이동 : L
- 현재 노드 n의 오른쪽 부트리 이동 : R

알고리즘

// 노드 클래스
class Node {
	String data;
    int left;
    int right;

	public Node(String data, int left, int right) {
		this.data = data;
        this.left = left;
        this.right = right;
	}
}

public void inOrder(Node node) {
    System.out.println(node.data); // 전위 순회 순서 출력
	if (node.left != 0) // 왼쪽 노드가 있다면 순회
		inOrder(node.left);
	if (node.right != 0) // 오른쪽 노드가 있다면 순회
       inOrder(node.right);
}

예시

◾ 중위 순회 (Inorder traversal)

LVR(왼쪽-루트-오른쪽)
루트 노드를 중간에 방문
수행 방법
- 현재 노드 n의 왼쪽 부트리 이동 : L
- 현재 노드 n 방문 : V
- 현재 노드 n의 오른쪽 부트리 이동 : R

알고리즘

// 노드 클래스
class Node {
	String data;
    int left;
    int right;

	public Node(String data, int left, int right) {
		this.data = data;
        this.left = left;
        this.right = right;
	}
}

public void inOrder(Node node) {
	if (node.left != 0) // 왼쪽 노드가 있다면 순회
		inOrder(node.left);
    System.out.println(node.data); // 중위 순회 순서 출력
	if (node.right != 0) // 오른쪽 노드가 있다면 순회
       inOrder(node.right);
}

예시

◾ 후위 순회 (Postorder traversal)

LRV(왼쪽-오른쪽-루트)
루트 노드보다 자손을 먼저 방문
수행 방법
- 현재 노드 n의 왼쪽 부트리 이동 : L
- 현재 노드 n의 오른쪽 부트리 이동 : R
- 현재 노드 n 방문 : V

알고리즘

// 노드 클래스
class Node {
	String data;
    int left;
    int right;

	public Node(String data, int left, int right) {
		this.data = data;
        this.left = left;
        this.right = right;
	}
}


public void postOrder(Node node) {
	if (node.left != 0) // 왼쪽 노드가 있다면 순회
		inOrder(node.left);
	if (node.right != 0) // 오른쪽 노드가 있다면 순회
       inOrder(node.right);
	System.out.println(node.data); // 후위 순회 순서 출력
}