트리

트리

 

• 루트(Root): 트리 구조에서 가장 위에 있는 노드입니다.
• 부모-자식 관계: 한 노드 아래에 연결된 노드를 ‘자식 노드’라고 하며, 연결 위쪽의 노드를 ‘부모 노드’라고 합니다.
• 형제 노드: 동일한 부모를 가진 노드들을 형제(sibling)라고 합니다.
• 리프(Leaf) 노드: 자식 노드가 없는 노드입니다. 트리의 말단에 위치합니다.
• 조상-자손 관계: 부모-자식 관계를 확장한 개념으로, 조상은 부모의 부모까지 포함하며, 자손은 자식의 자식까지 모두 포함합니다.

 

이진트리

이진트리는 모든 노드가 최대 두 개의 자식 노드를 가지는 트리입니다. 각각의 자식 노드는 왼쪽 자식(left child) 또는 오른쪽 자식(right child)으로 구분됩니다. 자식이 하나뿐인 경우에도 해당 자식이 왼쪽인지 오른쪽인지를 명확히 구분해야 합니다.

 

 

Full and Complete Binary tree

 

• Full Binary Tree: 모든 내부 노드가 정확히 두 개의 자식을 가지는 이진트리입니다.
• Complete Binary Tree: 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 노드들은 왼쪽부터 채워지는 이진트리입니다.

 

참고:
높이가 h인 Full Binary Tree는 최대 2^h - 1개의 노드를 가질 수 있습니다.
노드 수가 N인 Full 혹은 Complete 이진트리의 높이는 O(log N)입니다.
하지만 일반적인 이진트리는 최악의 경우 높이가 N이 될 수도 있습니다 (예: 한쪽으로만 치우친 트리).

 

🔗 이진트리의 연결 구조

일반적인 이진트리는 배열로 표현하기엔 규칙성이 부족하므로, 보통 연결 구조를 사용합니다. 이는 연결 리스트와 유사하게, 각 노드가 다음 정보를 갖습니다:

• 왼쪽 자식 노드의 주소
• 오른쪽 자식 노드의 주소
• (선택적으로) 부모 노드의 주소

이 때, 루트 노드는 어떤 노드에도 부모로 저장되어 있지 않기 때문에 별도로 보관해 두어야 합니다.

 

이진트리의 순회(traversal)

트리 순회는 트리의 모든 노드를 일정한 순서로 한 번씩 방문하는 과정을 말합니다. 이진트리에는 대표적으로 다음과 같은 순회 방법이 있습니다:

• 중순위 순회
• 선순위 순회
• 후순위 순회
• 레벨오더 순회

 

Inorder-순회

T_L을 inorder로 순회하고, r을 순회하고 T_r을 inorder로 순회합니다. 왼쪽을 먼저 순회하고 r을 순회, 그 다음 오른쪽 부트리를 나누어 생각합니다. 

이걸 inorder 해보면 먼저 2, 3, 5를 먼저 traverse하고 그 다음 r 인 6를 방문하고 그 다음 오른쪽 부트리인 7 8 순회합니다. 

INORDER-TREE-WALK(x)
	if x != NULL
    	then INORDER-TREE-WALKL(left[x])
        	print key[x]
            INORDER-TREE-WALK(right[x])

x를 루트로 하는 서브트리를 inorder로 순회하는 것입니다. x 가 null이라는 것은 노드가 아무것도 없다는 것이기에 이 경우에는 끝내면 됩니다. x가 null이 아니라면 x의 왼쪽 자식을 루트로 하는 서브트리를 recursion으로 하고 그 다음에 x를 방문합니다. 각 노드를 방문하면 그 노드에 저장된 key[x]값을 출력하는 것으로 하겠습니다.

 

그 다음 x의 오른쪽 자식을 봅니다. 

 

PREORDER-TREE-WALK(x)
	if x != NIL
    	then PRINT key[x]
        	PRE-ORDER-TREE-WALK(left[x])
            PRE-ORDER-TREE-WALK(right[x]).
            
POSTORDER-TREE-WALK(x)
	if x != NIL
    then POST-ORDER-TREE-WALK(left[x])
    	 POST-ORDER-TREE-WALK(right[x])
         print key[x];

preorder는 루트부터 먼저 출력하는 것이고 postorder는 루트를 맨 마지막에 출력하는 것입니다. 

 

Expression Trees

수식(Expression)을 표현하는 트리입니다.
예를 들어, x + y * a + b / c 라는 식을 트리로 표현하면 다음과 같은 결과가 나옵니다:

• Inorder 순회: 괄호를 이용해 표현
  ((x + y) * ((a + b) / c))
• 각 부트리를 순회할 때 시작과종료시에 괄호를 추가 (x+y) * ((a+b) / c)
• Postorder 순회: 후위 표기식
  x y + a b + + c / *

 

Level-Order 순회

레벨 순서대로 방문한다는 뜻입니다. 레벨 순으로 방문, 동일 레벨에서는 왼쪽에서 오른쪽 순서로 하며 큐를 이용하여 구현합니다. 하나의 큐를 이용해서 구현할 수 있는데 큐에서 왼쪽에서 오른쪽으로 나누고 큐에서 하나를 꺼내고 2의 왼쪽에서 오른쪽으로 7과 8을 출력하고 큐에 넣고 4, 6 꺼내고 순서대로 꺼내고 자식 꺼내소ㅓ 됐고 이렇게 비게되면 종료됩니다. 

 

LEVEL-ORDER-TREE-TRAVERSAL()
	visit the root;
    Q <- root; //Q is a queue
    while Q is not empty do
    	v <- dequeue(Q);
        visit children of v;
        enqueue children of v into Q;
    END.
END.

트리는 다양한 문제를 효율적으로 해결할 수 있는 강력한 자료구조입니다. 특히 이진트리는 많은 알고리즘과 자료구조에서 핵심적인 역할을 하니, 순회 방식과 구조를 잘 익혀두면 실전에서도 큰 도움이 될 것입니다.