-
Python BST 바이너리 서치 트리 Traversal + Height컴퓨터/파이썬 2020. 6. 27. 12:50728x90반응형
class BST: def __init__(self, value): self.value = value self.left = None self.right = None def traverse(tree, arr=[]): if tree is not None: #inOrder arr.append(tree.value) traverse(tree.left, arr) #preOrder arr.append(tree.value) traverse(tree.right, arr) #postOrder arr.append(tree.value) return arr
EX) 아래 그래프는
# 그래프 생성 root = BST(10) root.left = BST(5) root.left.left = BST(2) root.left.left.left = BST(1) root.left.right = BST(5) root.right = BST(15) root.right.right = BST(25)
inOrder = [1, 2, 5, 5, 10, 15, 22]
preOrder = [10, 5, 2, 1, 5, 15, 22]
postOrder = [1, 2, 5, 5, 22, 15, 10]
아래는 Max Height를 구하는 방법이다.
def getTreeHeight(tree, height=0): if tree is None: return height leftTreeHeight = getTreeHeight(tree.left, height + 1) rightTreeHeight = getTreeHeight(tree.right, height + 1) return max(leftTreeHeight, rightTreeHeight)
728x90'컴퓨터 > 파이썬' 카테고리의 다른 글
Python Count Sort 카운트 정렬 알고리즘 (0) 2020.06.28 Python %, modulo operator 나머지 연산자 음수 (0) 2020.06.24 Sublime Text 3 nose2 테스트 사용하기 (0) 2020.06.21