[좌충우돌, 파이썬으로 자료구조 구현하기] 이진트리 표현하기 (배열)

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

트리의 값을 레벨 순서대로 배열에 넣어보면 다음과 같다.

인덱스	0	1	2	3	4	5	6	7
값	A	B	C	D	E	F	None	G

• 루트 A의 인덱스는 0
  • A의 왼쪽 자식인 B의 인덱스: 2 * 0 + 1 = 1
  • A의 오른쪽 자식인 C의 인덱스: 2 * 0 + 2 = 2
• B의 인덱스는 1
  • B의 왼쪽 자식인 D의 인덱스: 2 * 1 + 1 = 3
  • B의 오른쪽 자식인 E의 인덱스: 2 * 1 + 2 = 4
• C의 인덱스는 2
  • C의 왼쪽 자식인 F의 인덱스: 2 * 2 + 1 = 5
• D의 인덱스는 3
  • D의 왼쪽 자식인 G의 인덱스: 2 * 3 + 1 = 7

부모 노드의 인덱스가 n일 때, 왼쪽 자식 노드의 인덱스는 2 * n + 1이고 오른쪽 자식 노드의 인덱스는 2 * n + 2이다.
자식노드가 2개 이하이므로 일정한 규칙에 따라 배열에 넣을 수 있다.

반대로 자식 노드의 부모 노드를 찾으려면, 자식 노드의 인덱스에서 1을 뺀 후 2로 나눈 몫만 취하면 된다.

ex) D의 부모 인덱스를 찾으려면, (3 - 1) // 2 = 1 이다

인덱스 0은 비워두고 1부터 트리를 구성하기도 하는데, 이 경우 왼쪽 자식 노드의 인덱스는 2 * n, 오른쪽 자식 노드의 인덱스는 2 * n + 1이다. 부모 노드의 인덱스는 자식 노드의 인덱스를 2로 나눈 몫만 취하면 된다.

자식 노드와 부모 노드 찾기

자식 노드 찾기

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

i = 0
n = len(tree)

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

        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()
    i += 1

실행결과

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, 

부모 노드 찾기

맨 하위의 노드부터 부모를 찾아서 출력한다.

# 위 코드에 이어서 작성

i = n - 1
while i > 0:
    if tree[i]:
        print(f"Parent of {tree[i]} -> {tree[(i-1)//2]}")
    i -= 1