삼항 트리(ternary tree)를 이중 연결 리스트(doubly linked list)로 변환해야 하는 경우, 먼저 'Node' 클래스를 생성해야 합니다. 이 클래스에는 노드에 저장되는 데이터(data)와 함께 왼쪽(left), 가운데(mid), 오른쪽(right) 자식 노드를 가리키는 세 개의 참조 속성이 포함됩니다.
다음으로 실제 변환 작업을 담당할 별도의 클래스를 생성합니다. 이 클래스의 초기화 함수(__init__)에서는 루트(root), 헤드(head), 테일(tail) 노드를 모두 None으로 초기화합니다.
이중 연결 리스트의 각 노드는 두 개의 포인터를 가집니다. 즉, 현재 노드는 다음(next) 노드를 가리키는 포인터와 이전(previous) 노드를 가리키는 포인터를 모두 가지므로 양방향 순회가 가능합니다. 리스트의 마지막 노드의 다음 포인터는 None을 가리킵니다.
변환 과정은 트리를 전위(pre-order) 방식으로 순회하면서 방문한 노드를 이중 연결 리스트의 끝에 하나씩 연결하는 방식으로 진행됩니다. 이때 노드의 포인터가 변경되기 전에 자식 노드 참조를 미리 저장해 두는 것이 중요합니다. 아래는 그 예시입니다.
예제
class Node:
def __init__(self, my_data):
self.right = None
self.data = my_data
self.left = None
self.mid = None
class ternary_tree_to_list:
def __init__(self):
self.root = None
self.head = None
self.tail = None
def convert_ternary_tree_to_list(self, node_val):
if node_val is None:
return
left = node_val.left
mid = node_val.mid
right = node_val.right
if self.head == None:
self.head = self.tail = node_val
node_val.mid = None
self.head.left = None
self.head.right = None
else:
self.tail.right = node_val
node_val.left = self.tail
node_val.mid = None
self.tail = node_val
self.tail.right = None
self.convert_ternary_tree_to_list(left)
self.convert_ternary_tree_to_list(mid)
self.convert_ternary_tree_to_list(right)
def print_it(self):
curr = self.head
if self.head == None:
print("리스트가 비어 있습니다")
return
print("노드 값 :")
while curr != None:
print(curr.data)
curr = curr.right
my_instance = ternary_tree_to_list()
print("트리에 노드가 추가되고 있습니다")
my_instance.root = Node(10)
my_instance.root.left = Node(14)
my_instance.root.mid = Node(24)
my_instance.root.right = Node(17)
my_instance.root.left.left = Node(22)
my_instance.root.left.mid = Node(23)
my_instance.root.mid.left = Node(24)
my_instance.root.mid.mid = Node(28)
my_instance.root.mid.right = Node(30)
my_instance.root.right.left = Node(45)
my_instance.root.right.mid = Node(50)
my_instance.root.right.right = Node(80)
my_instance.convert_ternary_tree_to_list(my_instance.root)
my_instance.print_it()
실행 결과
트리에 노드가 추가되고 있습니다 노드 값 : 10 14 22 23 24 24 28 30 17 45 50 80
코드 설명
- 'Node' 클래스를 생성하여 노드의 데이터와 left, mid, right 세 개의 자식 노드 참조를 정의합니다.
- 루트(root), 헤드(head), 테일(tail) 속성을 가지는 'ternary_tree_to_list' 클래스를 생성하고, __init__ 메서드에서 이들을 모두 None으로 초기화합니다.
- 'convert_ternary_tree_to_list' 메서드는 주어진 삼항 트리를 이중 연결 리스트로 변환합니다. 트리를 왼쪽, 가운데, 오른쪽 순서로 재귀적으로 순회하며 방문한 노드를 리스트의 테일에 차례로 연결합니다.
- 'print_it' 메서드는 헤드 노드부터 시작해 오른쪽 포인터를 따라가며 연결 리스트의 모든 노드 값을 화면에 출력합니다.
- 'ternary_tree_to_list' 클래스의 인스턴스를 생성하고, 12개의 노드로 구성된 삼항 트리를 만든 뒤 변환 메서드를 호출합니다.
- 변환이 완료되면 마지막으로 'print_it' 메서드를 통해 변환된 이중 연결 리스트의 내용이 콘솔에 출력됩니다.