[python] 이진탐색트리 검사 프로그램

임의의 이진트리에 대해 이진탐색트리인지 확인하는 검사 프로그램을 작성해 보자.

 

---

class Tree:
    def __init__(self, data): 
        self.data = data 
        self.left = None
        self.right = None

    # Tree 객체의 값을 보기 위한 Magic Method
    def __str__(self):
        return str(self.data)

def isBST(root, left = None, right = None):

    if (root == None) :
        return True

    # left node에 데이터가 있는지 확인 && left node가 root node 보다 작은지 확인
    if (left != None and root.data <= left.data):
        return False

    # right node에 데이터가 있는지 확인 && right node가 root node 보다 큰지 확인
    if (right != None and root.data >= right.data):
        return False

    # 임의의 트리의 모든 노드를 탐색할 수 있도록 재귀적으로 호출
    return isBST(root.left, left, root) and isBST(root.right, root, right)   

# case 1 ==> 이진탐색트리
# root = Tree(6) 
# root.left = Tree(3) 
# root.right = Tree(9) 
# root.left.left = Tree(1) 
# root.left.right = Tree(5) 
# root.right.left = Tree(7)
# root.right.right = Tree(11)

# case 2 ==> not 이진탐색트리
root = Tree(3)
root.left = Tree(2)
root.right = Tree(5)
root.right.left = Tree(1)
root.right.right = Tree(4)

if(isBST(root)):
    print("이진탐색트리가 맞습니다.")
else:
    print("이진탐색트리가 아닙니다.")