Data structures (with python) - 8.Tree - 8.4 Complete Binary Tree

Data structures (with python) - 8.Tree - 8.4 Complete Binary Tree

 

💡 A complete binary tree is a special type of binary tree where all the levels of the tree are filled completely except the lowest level nodes which are filled from as left as possible.

완전 이진 트리는 가능한 한 왼쪽부터 채워지는 최하위 레벨 노드를 제외하고 트리의 모든 레벨이 완전히 채워지는 특수한 유형의 이진 트리입니다.

 

Full Binary Tree 와 Complete Binary Tree 의  한글 번역에 조금 주의를 해야하는데,

개인적으로 정리하다보니 번역을 둘다 완전이진으로 잘못 하고 있는 경우도 있었다.

 

정 이진 트리(整二進-, full binary tree, 때로는 proper 또는 plane 이진 트리라고도 함)

완전 이진 트리(完全二進-, Complete binary tree)

포화 이진 트리(飽和二進-, perfect binary tree)

 

완전 이진 트리(Full Binary Tree): 이 트리는 모든 노드가 0개 또는 2개의 자식 노드를 가지는 트리를 말합니다. 이 말은, 한 노드가 자식 노드를 가진다면, 그것은 반드시 두 개의 자식 노드를 가져야 한다는 뜻입니다. 따라서 이 트리에서는 어떤 노드도 하나의 자식만을 가질 수 없습니다.

완전 이진 트리(Complete Binary Tree): 이 트리는 모든 레벨이 완전히 채워져 있고, 마지막 레벨의 노드는 왼쪽부터 오른쪽으로 차례대로 채워져 있는 트리를 말합니다. 이 말은, 트리의 높이 h에 대해 1부터 h-1까지의 각 레벨이 완전히 채워져 있고, 마지막 레벨은 왼쪽부터 차례대로 채워져 있어야 한다는 뜻입니다.

 

이 글에서 다룰 트리는 완전 이진 트리이다.

간략히 정리하자면 , 모든 레벨이 완전히 채워져 있고, 마지막 레벨은 왼쪾부터 시작해 순서대로 채워져 있는 트리이다.

 

In Python

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

# 노드 생성
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)

 

 

graphviz로 생성

 

 

 

 

 

# appendix 로 노드 트리들 시각화 하는것 적기