이진 트리와 이중 연결 리스트의 이해
주어진 이진 트리(binary tree)를 이중 연결 리스트(doubly linked list)로 변환하려면 먼저 'Node' 클래스를 생성해야 합니다. 이 클래스에는 노드에 저장될 데이터(data)와 다음 노드에 대한 참조라는 두 가지 핵심 속성이 있습니다.
또한 초기화 함수를 포함하는 별도의 클래스가 필요하며, 이 클래스에서는 리스트의 head 노드를 'None'으로 초기화합니다.
이중 연결 리스트의 각 노드는 포인터를 가집니다. 현재 노드는 다음 노드를 가리키는 포인터와 이전 노드를 가리키는 포인터를 모두 가지며, 리스트의 마지막 노드는 next 포인터에 'NULL' 값을 갖습니다. 덕분에 리스트를 양방향으로 자유롭게 순회할 수 있습니다.
이진 트리는 비선형(non-linear) 자료 구조입니다. 하나의 루트(root) 노드를 가지며, 루트를 제외한 모든 노드는 하나의 부모 노드만 가질 수 있고, 각 노드는 최대 두 개의 자식 노드를 가질 수 있습니다.
이 글에서는 주어진 이진 트리를 이중 연결 리스트로 변환하는 메서드와, 노드 값을 출력하는 메서드를 직접 정의하여 구현해 보겠습니다.
아래는 전체 구현 예시입니다.
예제 코드
class Node:
def __init__(self, my_data):
self.right = None
self.data = my_data
self.left = None
class binary_tree_to_list:
def __init__(self):
self.root = None
self.head = None
self.tail = None
def convert_tree_to_list(self, node_val):
if node_val is None:
return
self.convert_tree_to_list(node_val.left)
if (self.head == None):
self.head = self.tail = node_val
else:
self.tail.right = node_val
node_val.left = self.tail
self.tail = node_val
self.convert_tree_to_list(node_val.right)
def print_it(self):
curr = self.head
if (self.head == None):
print("The list is empty")
return
print("The nodes are :")
while curr != None:
print(curr.data)
curr = curr.right
my_instance = binary_tree_to_list()
print("Elements are being added to the list")
my_instance.root = Node(10)
my_instance.root.left = Node(14)
my_instance.root.right = Node(17)
my_instance.root.left.left = Node(22)
my_instance.root.left.right = Node(29)
my_instance.root.right.left = Node(45)
my_instance.root.right.right = Node(80)
my_instance.convert_tree_to_list(my_instance.root)
my_instance.print_it()출력 결과
Elements are being added to the list The nodes are : 22 14 29 10 45 17 80
코드 설명
- 'Node' 클래스가 생성됩니다. 각 노드는 left, right 포인터와 data 속성을 가집니다.
- 트리 변환에 필요한 속성들을 담은 'binary_tree_to_list' 클래스가 생성됩니다.
- 'convert_tree_to_list' 메서드는 중위 순회(in-order traversal) 방식으로 이진 트리를 순회하며 노드들을 이중 연결 리스트로 연결합니다.
- 'print_it' 메서드는 변환된 연결 리스트의 노드 값을 처음부터 끝까지 출력합니다.
- 'binary_tree_to_list' 클래스의 객체가 생성되고, 이 객체를 통해 트리 변환 및 출력 메서드가 호출됩니다.
- '__init__' 메서드는 이중 연결 리스트의 root, head, tail 노드를 None으로 초기화합니다.
- 'convert_tree_to_list' 메서드가 호출되면 이진 트리를 재귀적으로 순회하면서 각 노드를 이중 연결 리스트에 순서대로 연결합니다.
- 최종 결과는 'print_it' 메서드를 통해 콘솔에 출력됩니다.
마무리
이처럼 중위 순회를 활용하면 이진 탐색 트리의 노드들이 오름차순으로 정렬된 이중 연결 리스트로 자연스럽게 변환됩니다. 트리의 노드 수를 n이라 할 때 시간 복잡도는 O(n)이며, 새로운 노드를 생성하지 않고 기존 노드의 포인터만 재조정하므로 추가 공간 복잡도는 O(1)입니다. 이 알고리즘은 트리 구조를 선형 구조로 변환해야 하는 다양한 실무 시나리오에서 유용하게 활용될 수 있습니다.