목차

• 트리
• 트리의 기본 개념
  • 트리의 성질
  • 방향 트리
  • 그래프 vs 트리
• 이진트리 Binary Tree
  • 정의
  • 이진 트리 유형 Types of Binary Trees
  • 이진 트리의 최대 노드 수
  • 이진 트리를 표현하는 방법
• 탐방
  • 트리 탐방의 3가지 방법
    • 중순위 탐방 LDR
    • 전순위 탐방 DLR
    • 후순위 탐방 LRD -관련문제

트리

트리의 모든 것을 알아보자
정말 처음부터 끝까지 다 설명해 줄 것이다.

트리의 기본 개념

[트리 (Tree)]

• 사이클이 존재하지 않는 그래프
• 루트 노드가 한 개 존재하고, 루트로부터 다른 모든 노드로 가는 경로가 항상 유일하게 존재함

[루트(root)]

• 주어진 그래프의 시작 노드로서 통상 트리의 가장 높은 곳에 위치
• (예시) 노드 A

[차수(degree)]

• 그 노드의 서브 트리의 개수
• (예시) 노드 A의 차수는 3, B의 차수는 2, F의 차수는 0

[잎 노드(leaf node)]

• 차수가 0인 노드
• (예시) K, L, F, G, M, I, J가 잎 노드

[자식 노드(children node)]

• 어떤 노드의 서브 트리의 루트 노드
• (예시) A의 자식 노드는 B, C, D임

[부모 노드(parent node)]

• 자식노드의 반대 개념
• (예시) B의 부모노드는 A, G의 부모노드는 C임

[형제 노드(sibling node)]

• 동일한 부모를 가지는 노드
• (예시) B, C, D는 모두 형제 노드들이고 K, L도 형제 노드들 임

[중간 노드(internal node)]

• 루트도 아니고 잎 노드도 아닌 노드를 말함

[조상(ancestor)]

• 루트로부터 그 노드에 이르는 경로에 나타난 모든 노드들을 말하는데,
• (예시) F의 조상은 B와 A이며, M의 조상은 H, D, A임

[자손(descendant)]

• 그 노드로 부터 잎 노드에 이르는 경로상에 나타난 모든 노드들
• (예시) B의 자손은 E, F, K, L이고 H의 자손은 M임

[레벨(level)]

• 루트의 레벨을 0으로 놓고 자손 노드로 내려가면서 하나씩 증가
• 즉, 어떤 노드의 레벨이 p라면 그것의 자식 노드의 레벨은 p+1이 됨

[트리의 높이(height)]

• 트리에서 노드가 가질 수 있는 최대 레벨로서 트리의 깊이(depth)라고도 함.
• (예시) 이 트리의 높이는 3이 됨

[숲(forest)]

• 서로 연결되지 않는 트리들의 집합
• 트리에서 루트를 제거하면 숲을 얻음

트리의 성질

• n개의 노드를 가진 트리는 n-1개의 연결선을 가짐

• 그래프 G=(V, E)에서

  V

  =n 이고

  E

  =m일 때 다음의 문장들은 모두 동치

  • G는 트리이다.
  • G는 연결되어 있고 m=n-1 이다.
  • G는 연결되어 있고 어느 한 연결선만을 제거해도 G는 연결되지않는다.
  • G는 사이클을 가지지 않으며 m=n-1이다.
  • G는 어느 한 연결선만 첨가하더라도 사이클을 형성하게 된다.

방향 트리

• 방향이 있고 순서화된 트리로 다음의 성질들을 만족함
  • 선행자가 없는 루트라고 불리는 노드가 존재,
  • 이 루트에서는 모든 노드로 갈 수 있는 경로가 있음
  • 루트를 제외한 모든 노드들은 오직 하나씩만의 선행자를 가짐
  • 각 노드의 후속자들은 통상 왼쪽으로부터 순서화됨
  • 방향 트리를 그릴 때 그 트리의 루트는 가장 위에 있음
  • 아크(연결선)들은 밑을 향하여 그려짐
• 하지만 트리는 항상 한방향 UNi- Directional이기 때문에 생략 가능
  • 화살표는 그리지 않아도 됨

그래프 vs 트리

무엇보다도 가장 두드러지는 큰 차이점은 다음과 같다.
“트리는 순환 구조를 갖지 않는 그래프입니다.”

• 핵심은 순환 구조 Cyclic 가 아니라는 데 있다.
  • 트리는 특수한 형태의 그래프의 일종이며, 크게 그래프의 범주에 포함된다.
    “하지만 트리는 그래프와 달리 어떠한 경우에도 한번 연결된 노드가 다시 연결되는 법이 없다”
• 그래프: 이외에도 단방향 Uni-Directional , 양방향 Bi-Directional 모두 가능
• 트리: 부모 노드에서 자식 노드를 가리키는 단방향뿐
  “트리는 하나의 부모 노드를 갖는다는 차이점이 있으며 루트 또한 하나여야 한다.”*

이진트리 Binary Tree

트리 중에서도 가장 널리 사용되는 트리 자료구조

• 이진 트리
• 이진 탐색 트리 Binary Search Tree (이하 BST)

정의

각 노드가 m개 이하의 자식을 갖고 있으면, m-ary 트리(다항트리, 다진 트리)라고 한다.
여기서 m=2일 경우, 즉 모든 노드의 차수가 2 이하일 때는 특별히 이진 트리 Binary Tree 라고 구분해서 부름

• 왼쪽, 오른쪽, 최대 2개의 자식을 갖는 매우 단순한 형태
• 다진 트리에 비해 훨씬 간결
• 여러 가지 알고리즘을 구현하는 일도 좀 더 간단하게 처리 가능
  즉,
• 공집합이거나
• 루트와 왼쪽 서브트리, 오른쪽 서브트리로 이루어진다.

이진 트리 유형 Types of Binary Trees

[주의] 트리용어는 정확히 표준되어있지 않아, 논문에서도 각기 조금씩 다른 편

• 포화 이진 트리 Perfect Binary Tree
  • 모든 노드가 2개의 자식 노드를 갖고 있으며, 모든 리프 노드가 동일한 깊이 또는 레벨을 갖는다.
  • 문자 그대로, 가장 완벽한 Perfect 유형의 트리다.
• 정 이진 트리 Full Binary Tree : 모든 노드가 0개 또는 2개의 자식 노드를 갖는다.
• 사향 이진 트리 Complete(skewed) Binary Tree
  • 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가장 왼쪽부터 채워져 있다.
  • 왼쪽 또는 오른쪽으로 편향된 트리의 구조를 가짐
    

이진 트리의 최대 노드 수

레벨 i 에서의 최대 노드 수 는 \(2^i\) 개

• 높이가 k 일 때 전체 최대 노드 수는 \(2^{k+1}-1\) 개
• 예: 레벨 2에서의 최대 노드 수는 \(2^2=4\) 개
• 높이가 2일 때 전체 최대 노드 수는 \(2^2+1-1=7\) 개

\(n_0=n_2+1\)의 식이 항상 성립

• \(n_0\): 잎 노드의 개수
• \(n_2\): 차수가 2인 노드의 개수
  

이진 트리를 표현하는 방법

1) 배열(array)에 의한 방법

• 트리의 중간에 새로운 노드를 삽입하거나 기존의 노드를 지울 경우 비효율적임

2) 연결 리스트(linked list)에 의한 방법

• 데이터를 저장하는 중간 부분, 왼쪽 자식(left child), 오른쪽 자식(right child)을 각각 가리키는 포인터(pointer) 부분으로 구성
  

탐방

• 트리에서 각 노드를 꼭 한 번씩만 방문하는 것임
• 탐방의 결과 각 노드에 들어 있는 데이터를 차례로 나열하게 됨

트리 탐방의 3가지 방법

• L: 왼쪽(Left)으로의 이동
• D: 데이터(Data) 프린트
• R: 오른쪽(Right)으로의 이동을 나타냄
• 루트 나올 때 프린트

중순위 탐방 LDR

infix, inorder
1) 트리의 왼쪽 서브 트리를 탐방
2) 노드를 방문하고 데이터 프린트
3) 트리의 오른쪽 서브트리를 탐방
(수도코드)

파이썬 구현

Node class 정의

def inorder(node):
 if node is None:
  return inorder(node.left) 
  print(node.val) 
  inorder(node.right)

자바 구현

Node class 정의

public void traverse_inorder()
{
	traverse_inorder_node(root);
}
		
public void traverse_inorder_node(TNode current)
{
	if(current == null)
		return;
			
	traverse_inorder_node(current.left);
	System.out.println(current.data);
	traverse_inorder_node(current.right);
}

전순위 탐방 DLR

prefix, preorder
1) 노드를 탐방하고 데이터 프린트
2) 트라의 왼쪽 서브트리를 탐방
3) 트리의 오른쪽 서브 트리를 탐방
(수도코드)

파이썬 구현

Node class 정의

def preorder(node):
 if node is None:
  return print(node.val) 
  preorder(node.left) 
  preorder(node.right)

자바 구현

Node class 정의

public void traverse_preorder()
{
	traverse_preorder_node(root);
}
		
//기준이 current인 subtree를 preorder방식으로 traverse하는 일반적인 함수에요 
int count = 0;
public void traverse_preorder_node(TNode current)
{
			
	if(current == null)
		return;
	count+=1;
	System.out.println(current.data+"depth ="+count);
			
	traverse_preorder_node(current.left);
	traverse_preorder_node(current.right);
	count-=1;
}
		

후순위 탐방 LRD

postfix, postorder
1) 트리의 왼쪽 서브트리를 탐방
2) 트리의 오른쪽 서브트리를 탐방
3) 노드를 탐방하고 데이터 프린트
(수도코드)

파이썬 구현

Node class 정의

def postorder(node):
 if node is None:
  return postorder(node.left) 
  postorder(node.right) 
  print(node.val)

자바 구현

Node class 정의

		
public void traverse_postorder()
{
	traverse_postorder_node(root);
}
		
public void traverse_postorder_node(TNode current)
{
	if(current == null)
		return;
			
		traverse_postorder_node(current.left);
		traverse_postorder_node(current.right);
		System.out.println(current.data);
}

[Cheak Cheak]
다음 트리의 중순위, 전순위, 후순위 탐색 순서를 써라

• 중순위 탐방 LDR: (ㄴ->ㄱ->ㄷ) d,b,e,a,f,c,g
• 전순위 탐방 DLR: (ㄱ->ㄴ->ㄷ) a,b,d,e,c,f,g
• 후순위 탐방 LRD: (ㄴ->ㄷ->ㄱ) d,e,b,f,g,c,a

Node class, root 정의

• root는 Cheak Cheak의 예시를 바탕으로 구현

[python]

class Node: i
def __init__(self, val, left=None, right=None):
 self.val = val 
 self.left = left 
 self.right = right

// 자식노드가 없으면 괄호 닫음
root = Node('A', 
            Node('B', 
                Node('D'), Node('E')
                ) 
            Node('C', 
                Node('F'), Node('G')
                ) 
            )

[java]

public class TNode {
	int data;
	TNode left;
	TNode right;
}

root = TNode('A', 
            TNode('B', 
                TNode('D'), TNode('E')
                ) 
            TNode('C', 
                TNode('F'), TNode('G')
                ) 
            )

관련 문제

• leet code_104. Maximum Depth of Binary Tree
• leet code_543. Diameter of Binary Tree