이진트리(BinaryTree) 개념과 파이썬 구현

 이진트리(BinaryTree)

 

이진트리(BinaryTree)는 각 노드의 자식수가 2 이하인 트리입니다.

 

이진트리에는 4가지 순회방식이 존재합니다. 방식은 각각 다르지만 항상 트리의 루트부터 시작한다는 공통점이 있습니다. 또한 모든 순회 방식은 트리의 모든 노드들을 반드시 1번씩 방문하고 순회를 종료합니다.

 

1. 전위순회(Preorder Traversal)

 

전위순회의 순회방법입니다.

• 현재 노드 n를 먼저 방문합니다.
• 현재 노드의 왼쪽 서브트리를 순회합니다.
• 현재 노드의 오른쪽 서브트리를 순회합니다.

전위순회의 순서는 NLR입니다. (N은 현재 노드, L은 왼쪽 서브트리, R은 오른쪽 서브트리)

def preorder(self, n):
        if n != None:
            print(n.item,' ',end='') # 노드 방문
            if n.left:
                self.preorder(n.left) # 왼쪽 서브트리 순회
            if n.right:
                self.preorder(n.right) # 오른쪽 서브트리 순회

 

2. 중위순회(Inorder Traversal)

 

중위순회의 순회방법입니다.

• 현재 노드의 왼쪽 서브트리를 순회합니다.
• 현재 노드 n을 방문합니다.
• 현재 노드의 오른쪽 서브트리를 순회합니다.

중위순회의 순서는 LNR입니다.

def inorder(self, n):
        if n != None:
            if n.left:
                self.preorder(n.left) # 왼쪽 서브트리 순회
            print(n.item,' ',end='') # 노드 방문
            if n.right:
                self.preorder(n.right) # 오른쪽 서브트리 순회

 

3. 후위순회(Postorder Traversal)

 

후위순회의 순회방법입니다.

• 현재 노드의 왼쪽 서브트리를 순회합니다.
• 현재 노드의 오른쪽 서브트리를 순회합니다.
• 현재 노드 n을 방문합니다.

후위순회의 순서는 LRN입니다.

def postorder(self, n):
        if n != None:
            if n.left:
                self.preorder(n.left) # 왼쪽 서브트리 순회
            if n.right:
                self.preorder(n.right) # 오른쪽 서브트리 순회
            print(n.item,' ',end='') # 노드 방문

 

4. 레벨순회(Level-order Traversal)

 

레벨순회의 순회방법입니다.

• 루트가 있는 곳부터 각 레벨마다 좌에서 우로 노드들을 방문합니다.

def levelorder(self, root):
        q=[] # 리스트 구현(큐로 사용하기 위해)
        q.append(root)
        while q:
            t=q.pop(0)
            print(t.item,' ',end='') # 큐에서 첫 항목 삭제하고 삭제한 노드 방문
            if t.left != None:
                q.append(t.left) # 왼쪽 자식 큐에 삽입
            if t.right != None: 
                q.append(t.right) # 오른쪽 자식 큐에 삽입

 

위 트리 형태를 4가지 방법으로 순회해보겠습니다.

 

이진트리 전체 파이썬 코드입니다.

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

class BinaryTree():
    def __init__(self): # 트리 생성
        self.root = None

    # 전위순회
    def preorder(self, n):
        if n != None:
            print(n.item,' ',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.item,' ',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.item,' ',end='') # 노드 방문

    # 레벨순회
    def levelorder(self, root):
        q=[] # 리스트 구현(큐로 사용하기 위해)
        q.append(root)
        while q:
            t=q.pop(0)
            print(t.item,' ',end='') # 큐에서 첫 항목 삭제하고 삭제한 노드 방문
            if t.left != None:
                q.append(t.left) # 왼쪽 자식 큐에 삽입
            if t.right != None: 
                q.append(t.right) # 오른쪽 자식 큐에 삽입

    def height(self, root):
        if root == None:
            return 0
        # 루트 노드를 기준으로 두 자식노드의 높이 중 큰 높이 
        return max(self.height(root.left), self.height(root.right)) + 1


tree=BinaryTree()
n1=Node(10)
n2=Node(20)
n3=Node(30)
n4=Node(40)
n5=Node(50)
n6=Node(60)
n7=Node(70)
n8=Node(80)

# 트리 만들기
tree.root=n1
n1.left=n2
n1.right=n3
n2.left=n4
n2.right=n5
n3.left=n6
n3.right=n7
n4.left=n8

# 출력>>트리 높이 : 4
print('트리 높이 :', tree.height(tree.root))

# 출력>>전위순회 : 10  20  40  80  50  30  60  70  
print('전위순회 : ',end='')    
tree.preorder(tree.root)

# 출력>>중위순회 : 20  40  80  50  10  30  60  70  
print('\n중위순회 : ',end='')
tree.inorder(tree.root)

# 출력>>후위순회 : 20  40  80  50  30  60  70  10  
print('\n후위순회 : ',end='')
tree.postorder(tree.root)

# 출력>>레벨순회 : 10  20  30  40  50  60  70  80  
print('\n레벨순회 : ',end='')
tree.levelorder(tree.root)