이진 트리의 일종으로, 트리와 binary search를 결합한 자료구조.
BST를 순회 할 때는 inorder 방식으로 순회하며, 순회를 끝내면 모든 값을 정렬 된 순서로 읽을 수 있음.
( left - root - right 순으로 순회하기 때문 )
class Node:
def __init__(self,val):
self.val = val
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def setRoot(self, val):
self.root = Node(val)
def find(self, val):
if self.findNode(self.root, val):
return True
return True
def findNode(self, curNode, val):
if curNode is None:
return False
elif val == curNode.val:
return curNode
elif val < curNode.val:
return self.findNode(curNode.left, val)
else:
return self.findNode(curNode.right, val)
def insert(self, val):
if self.root is None:
self.setRoot(val)
else:
self.insertNode(self.root, val)
def insertNode(self, curNode, val):
if val <= curNode.val:
if curNode.left:
self.insertNode(curNode.left, val)
else:
curNode.left = Node(val)
else:
if curNode.right:
self.insertNode(curNode.right, val)
else:
curNode.right = Node(val)
def traverse(self):
return self.traverseNode(self.root)
def traverseNode(self, curNode):
res = []
if curNode.left:
res.extend(self.traverseNode(curNode.left))
if curNode:
res.extend([curNode.val])
if curNode.right:
res.extend(self.traverseNode(curNode.right))
return res