Binary Tree란?

노드가 왼쪽 자식과 오른쪽 자식만을 갖는 트리이다. 자식을 최대 2명을 가진다.

특징

• 왼쪽 자식과 오른쪽 자식을 구분하며, 왼쪽 자식을 루트로 하는 left subtree, 오른쪽 자식을 루트로 하는 right subtree라 한다.
• 대표적인 3가지의 순회 방법이 있다.
  • 전위순회 preoder- root > left subtree > right subtree
  • 중위순회 inorder- left subtree > root > right subtree
  • 후위순회 postorder- left subtree > right subtree > root

구현방법

• 노드번호를 배열의 인덱스로 사용하여 표현한다.

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

class BinaryTree:
    def __init__(self):
        self.root = None

    # 전위순회
    def preorder(self, n):
        if n != None:
            print(n.value,' ', end='')
            if n.left:
                self.preorder(n.left)
            if n.right:
                self.preorder(n.right)

    # 중위순회
    def inorder(self, n):
        if n != None:
            if n.left:
                self.preorder(n.left)
            print(n.value,' ',end='')
            if n.right:
                self.preorder(n.right)

    # 후위순회
    def postorder(self, n):
        if n != None:
            if n.left:
                self.preorder(n.left)
            if n.right:
                self.preorder(n.right)
            print(n.value,' ',end='')

    # 이진트리 높이
    def height(self, root):
        if root == None:
            return 0
        return max(self.height(root.left), self.height(root.right)) + 1

# 테스트코드
from BinaryTree import BinaryTree
from BinaryTree import Node

tree = BinaryTree()

n1 = Node(1)
n2 = Node(2)
n3 = Node(3)
n4 = Node(4)
n5 = Node(5)
n6 = Node(6)
n7 = Node(7)
n8 = Node(8)

tree.root = n1
n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5
n3.left = n6
n3.right = n7
n4.left = n8

tree.preorder(tree.root)
print()
tree.inorder(tree.root)
print()
tree.postorder(tree.root)
print()
print(tree.height(tree.root))

시간복잡도