[Tree] 배열로 이진트리 구현하기

배열로 이진트리 구현하기

파이썬으로 이진트리를 표현 방법에 (1) 배열을 이용하는 것과 (2) 연결 리스트를 이용하는 것이 있다.

 

먼저 배열로 이진트리를 나타내보자. 위 트리의 값을 레벨 순서대로 배열에 넣어 보면 다음과 같다.

위에서 보는 것처럼 부모 노드의 인덱스가 n일 때, 왼쪽 자식 노드의 인덱스는 (2 × n + 1)이며, 오른쪽 자식 노드의 인덱스는 (2 × n + 2)이다. 자식 노드가 2개 이하이므로 일정한 규칙에 따라 배열에 넣을 수 있다.

 

반대로 자식 노드의 부모 노드를 찾으려면, 자식 노드의 인덱스에서 1을 뺀 후에 2로 나눈 몫만 취하면 된다. 예를 들어 D의 부모 노드의 인덱스를 찾으면 (3 - 1) // 2 = 1이다.

인덱스 0은 비워두고, 인덱스 1부터 자료를 넣어 트리를 구성하기도 한다. 그렇게 하면 왼쪽 자식 노드의 인덱스는 (2 × n), 오른쪽 자식 노드의 인덱스는 ( 2 × n + 1)이다. 그럼 부모 노드의 인덱스는 자식 노드의 인덱스를 2로 나눈 몫만 취하면 된다.

자식 노드와 부모 노드를 찾기

1) 자식 노드 찾기

위에서 얘기한 방법으로 부모와 왼쪽 자식, 오른쪽 자식을 출력한다.

tree = ["A", "B", "C", "D", "E", "F", None, "G"]

n = len(tree)

for i in range(n):
    if tree[i]:
        print(f"Parent: {tree[i]}", end = ", ")
        left, right = 2*i + 1, 2*i + 2

        if left < n and tree[left] is not None:
            print(f"Left: {tree[left]}",end = ", ")
        if right < n and tree[right] is not None:
            print(f"Right: {tree[right]}",end=" ")
        print()

Parent: A, Left: B, Right: C 
Parent: B, Left: D, Right: E 
Parent: C, Left: F, 
Parent: D, Left: G, 
Parent: E, 
Parent: F, 
Parent: G,

• 배열을 순회한다.
  • 값이 None이 아니면
    • 값을 출력한다.
    • 왼쪽 자식 노드와 오른쪽 자식 노드의 인덱스를 계산한다.
    • 각 인덱스가 배열의 길이보다 작고, 해당 배열의 값이 None이 아니면 출력한다.

2) 부모 노드 찾기

이제 각 노드의 부모 노드를 찾아서 출력한다.

tree = ["A", "B", "C", "D", "E", "F", None, "G"]

n = len(tree)

for i in range(n-1,0,-1):
    if tree[i]:
        print(f"Parent of {tree[i]} -> {tree[(i-1)//2]}")

Parent of G -> D  
Parent of F -> C  
Parent of E -> B  
Parent of D -> B  
Parent of C -> A  
Parent of B -> A

• 배열을 거꾸로 순회한다.
  • 값이 None이 아니면 부모 노드의 인덱스를 계산하여 출력한다.

출처 : https://wikidocs.net/193817

07-01. 배열로 이진트리 표현하기