이진탐색트리

• 모든 노드는 유일한 키를 갖는다

• 왼쪽 서브 트리의 키들은 루트의 키보다 작다.

• 오른쪽 서브트리의 키들은 루트의 키보다 크다.

• 왼쪽과 오른쪽의 서브트리도 이진탐색트리이다.

• BSTnode class - 생성자로 key 값과 value 값을 받아서 초기화 함

class bstnode:
    def __init__(self,key,value):
        self.key = key
        self.value = value
        self.left = None
        self.right = None

• 이진 탐색트리 생성
• 탐색트리를 만들과 순환구조를 이용해서 최대 키 값을 찾는 함수인 findmax_bst를 만들고 최소 키값을 가지는함수인 findmin_bst를 만듦

def findmax_bst(node):
    if node != None:
        if node.right == None:
            return node
        else:
            return findmax_bst(node.right)

def findmin_bst(node):
    if node != None:
        if node.left == None:
            return node
        else:
            return findmin_bst(node.left)

• 반복문을 이용해서 만든 insert함수

def insert_bst_repeat(compareNode, newNode):

    while(True):

        if newNode.key < compareNode.key:
            if compareNode.left == None:
                compareNode.left = newNode
                return True

            else:
                compareNode = compareNode.left
                # return insert_bst(compareNode.left, newNode)
        elif newNode.key > compareNode.key:
            if compareNode.right == None:
                compareNode.right = newNode
                return True

            else:
                compareNode = compareNode.right
                # return insert_bst(compareNode.right, newNode)
        elif newNode.key == compareNode.key:
            return False

• 이진탬색 트리의 출력을 위해서 이진탐색 트리를 출력하는 함수를 만듦

def showBST(node):

    if node is not None:
        showBST(node.left)
        print(node.key,end='  ')
        showBST(node.right)

• 함수 호출해서 출력하는 부분

showBST(a)#초기에 만든 탐핵이진트리 출력
print()#공간 구문을 위해서 여백출력
newNode = bstnode(9,'H')#삽입을 위해서 노드를 생성
insert_bst_repeat(a,newNode)#반복문을 이용해서 삽입을 진행하는 함수 
showBST(a)#삽입을 진행한 후 탐색트리 다시 출력함.

• 실행결과