20. 이진 트리와 이진 검색 트리(2) 탐색, 최대, 최소

최댓값과 최솟값 찾기

이진 탐색 트리에서 최솟값은 항상 왼쪽에 있기 때문에 왼쪽의 None을 찾아 직전의 값을 리턴하면 됩니다. 

최댓값은 반대입니다. 

 

특정값 찾기

현재 노드의 값과 특정값을 비교해서 높으면 오른쪽 낮으면 왼쪽으로 내려가면 됩니다. 

class Node:

    def __init__(self, item):
        self.item = item
        self.left = None
        self.right = None


class BST:

    def __init__(self):
        self.root = None

    def insert(self, item):

        new_node = Node(item)

        if self.root is None:
            self.root = new_node
            return

        current = self.root

        while True:
            parent = current
            if item < current.item:
                current = current.left
                if current is None:
                    parent.left = new_node
                    break
            else:
                current = current.right
                if current is None:
                    parent.right = new_node
                    break

    def get_min(self):
        current = self.root
        while current.left is not None:
            current = current.left
        return current

    def get_max(self):
        current = self.root
        while current.right is not None:
            current = current.right
        return current

    def find(self, item):
        current = self.root
        while True:
            if current is None:
                return None
            if current.item > item:
                current = current.left
            elif current.item < item:
                current = current.right
            else:  # current.item == item
                return current


boo = BST()

boo.insert(5)
boo.insert(2)
boo.insert(3)
boo.insert(1)
boo.insert(9)
boo.insert(8)
boo.insert(7)

print(boo.get_min())
print(boo.get_min().item)
print(boo.get_max())
print(boo.get_max().item)
print(boo.find(8))
print(boo.find(8).item)

<__main__.Node object at 0x0000026C6D8714E0>
1
<__main__.Node object at 0x0000026C6D871518>
9
<__main__.Node object at 0x0000026C6D871550>
8

인서트에 비하면 쉽습니다. 

 

트리 탐색 - 전위(preorder) 탐색, 중위(inorder) 탐색, 후위(postorder) 탐색

 

재귀를 이용할 수 있습니다. 

print 문의 위치에 따라 출력형태가 바뀝니다. 

전위, 중위, 후위로 분류합니다. 

 

class Node:

    def __init__(self, item):
        self.item = item
        self.left = None
        self.right = None


class BST:

    def __init__(self):
        self.root = None

    def insert(self, item):

        new_node = Node(item)

        if self.root is None:
            self.root = new_node
            return

        current = self.root

        while True:
            parent = current
            if item < current.item:
                current = current.left
                if current is None:
                    parent.left = new_node
                    break
            else:
                current = current.right
                if current is None:
                    parent.right = new_node
                    break

    def inorder(self, node):
        if node is not None:
            self.inorder(node.left)
            print(node.item, end=' ')
            self.inorder(node.right)
        # else:
        # print('none', end=' ')

    def preorder(self, node):
        if node is not None:
            print(node.item, end=' ')
            self.preorder(node.left)
            self.preorder(node.right)
        # else:
        # print('none', end=' ')

    def postorder(self, node):
        if node is not None:
            self.postorder(node.left)
            self.postorder(node.right)
            print(node.item, end=' ')
        # else:
        # print('none', end=' ')


boo = BST()

boo.insert(5)
boo.insert(2)
boo.insert(3)
boo.insert(1)
boo.insert(9)
boo.insert(8)
boo.insert(7)

boo.inorder(boo.root)
print()
boo.preorder(boo.root)
print()
boo.postorder(boo.root)

 

결과를 확인합니다. 위 그림을 참고하세요. 

1 2 3 5 7 8 9 
5 2 1 3 9 8 7 
1 3 2 7 8 9 5 

 

이해가 잘 안되실 수도 있습니다. 

그럴 땐 None을 같이 확인해 보는 것도 좋습니다. 

화살표까지 나와있는 친절한 강좌를 같이 보시는 것도 좋습니다. 

none 1 none 2 none 3 none 5 none 7 none 8 none 9 none 
5 2 1 none none 3 none none 9 8 7 none none none none 
none none 1 none none 3 2 none none 7 none 8 none 9 5