8.4 이진 탐색 트리의 구현
먼저 몇 가지 필요한 편의 함수와 전위·중위 순회 메서드를 만들어 둡시다.
코드 8-3
class BST:
def __init__(self):
self.root = None
def get_root(self):
return self.root
def preorder_traverse(self, cur, func):
if not cur:
return
func(cur)
self.preorder_traverse(cur.left, func)
self.preorder_traverse(cur.right, func)
# key가 정렬된 상태로 출력
def inorder_traverse(self, cur, func):
if not cur:
return
self.inorder_traverse(cur.left, func)
func(cur)
self.inorder_traverse(cur.right, func)
# 편의 함수
# cur의 왼쪽 자식을 left로 만듭니다.
def __make_left(self, cur, left):
cur.left = left
if left:
left.parent = cur
# 편의 함수
# cur의 오른쪽 자식을 right로 만듭니다.
def __make_right(self, cur, right):
cur.right = right
if right:
right.parent = cur