자료구조 | 이진 트리 구현 (python) | Trees

최종 목표는 프로그램 1, 2를 구현하는 것이다. 프로그램 1. 트리 생성 / 노드의 깊이 / 노드의 높이 / 트리의 깊이 / 트리의 높이 프로그램 2. 허프만 코딩 트리 그러나 이에 앞서서 트리 구조, 이진 트리 구조를 충분히 이해하고 구현하는 과정을 거치고자 한다.

 

먼저 이진 트리에서 구현하고자 하는 목록은 다음과 같다. 

 

• 이진 트리 생성
• 노드의 깊이
• 노드의 높이
• 트리의 노드 최댓값
• 트리의 깊이 최댓값
• 허프만 코딩 트리
• postorder
• preorder
• inorder
• level order
• copy tree
• evaluation tree
• threaded binary tree
• heap
• delete
• insert
• heap sort
• make heap
• priority queue

---

• 이진 트리 생성

이진 트리는 최대 두 개의 자식 노드를 가지는 계층적 트리 형태의 자료구조

값을 저장하는 용도 그 이상으로 탐색, 정렬을 위해 사용된다. 

이진 트리는 Node 클래스와 BinaryTree 클래스를 이용해서 구현한다. 

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

Node 클래스는 data field와 link field로 구성된다. link field에는 left와 right가 있다.

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

BinaryTree 클래스의 경우, 일단 self.root = None의 형태로 초기화해준다.

 

정교한 level 기준 insert 함수를 구현하기 전에, 일단 __init__ 함수에서 노드를 추가해주는 것으로 해두자.

연결 리스트이므로 노드 생성 -> right, left 조정하는 것을 반복한다. 굉장한 노가다 형식의 트리이지만, 일단 임시 방편으로 이렇게 구현해보았다. 

class BinaryTree:
    def __init__(self):
        self.root = None
        
        temp = Node('-')
        self.root = temp
        
        temp = Node('+')
        self.root.left = temp
        
        temp = Node('/')
        self.root.right = temp
        
        temp = Node('*')
        self.root.left.left = temp
        
        temp = Node('C')
        self.root.left.right = temp
        
        temp = Node('D')
        self.root.right.left = temp
        
        temp = Node('E')
        self.root.right.right = temp
        
        temp = Node('A')
        self.root.left.left.left = temp
        
        temp = Node('B')
        self.root.left.left.right = temp

 

그리고 효과적인 이진 트리의 시각화를 위해 printBT 함수를 미리 마련해두고자 한다. 

이때 printBT 함수는 Binary Tree를 inorder로 출력하는 함수를 말한다. 

    def printBT(self, tree):
        if tree:
            self.printBT(tree.left)
            try:
                print("%d" % tree.data)
            except:
                print("%s" % tree.data)
            self.printBT(tree.right)

 

• 노드의 깊이

노드의 depth 는 root node에서 자식 노드로 내려갈 때마다 depth가 1씩 추가된다.

다음 output과 같이 노드를 탐색하면서, 각 노드에 대하여 data, depth로 출력해주면 된다.

- 0
+ 1
* 2
C 2
A 3
B 3
/ 1
D 2
E 2

짠~ printBT의 inorder 출력 형태를 살려서 구현해보았다. 

    def nodeDepth(self, node, d):
        if node:
            self.nodeDepth(node.left, d+1)
            try:
                print("%d %d" % (node.data, d))
            except:
                print("%s %d" % (node.data, d))
            self.nodeDepth(node.right, d+1)

 

• 노드의 높이

HHHHHH
A 0
* 1
B 0
+ 2
C 0
- 3
D 0
/ 1
E 0

재귀함수로 구현하여 효율성은 떨어지지만.. 이렇게 구현해보았다. 

    def nodeCalculate(self, node):
        if node.left or node.right:
            return max(self.nodeCalculate(node.left), self.nodeCalculate(node.right)) + 1
        else:
            return 0
    
    def nodeHeight(self, node):
        if node:
            self.nodeHeight(node.left)
            try:
                print("%d" % (node.data), end=' ')
            except:
                print("%s" % (node.data), end =' ')  
            
            print("%d" % self.nodeCalculate(node))
             
            self.nodeHeight(node.right)
        
        else:
            return 0

 

• 트리의 높이

tree height의 정의 : root node의 height와 같다. 

root node부터 leaf node까지 재귀적으로 진행하며, 최댓값이 나올 때마다 최종 답을 갱신해준다. 

 

 

• 트리의 깊이

 

• 허프만 코딩 트리

 

• postorder

 

• preorder

 

• inorder

 

• level order

 

• copy tree

 

• evaluation tree

 

• threaded binary tree

 

• heap

 

• delete

 

• insert

 

• heap sort

 

• make heap

 

• priority queue