import collections  # 큐(queue) 구조를 위한 패키지

# 이진 트리에 대한 클래스 선언
class TreeNode:
    def __init__(self):
        self.data = 0
        self.left = None
        self.right = None
 
# 이진 트리의 높이를 계산하는 함수
def height(root, node_values, level_labels):
    ans = 0
    queue = collections.deque()
    # 이진 트리의 노드가 하나도 없을 때 0을 반환
    if root is None:
        return ans
 
    queue.append(root)  # 루트 노드를 큐에 삽입
  
    # 선언된 큐에 노드가 있는 동안 계속 반복
    while queue:
        currSize = len(queue)  # 현재의 큐 크기를 대입
        # 큐의 currSize개의 노드들을 디큐
        while currSize > 0:
            currNode = queue.popleft()  # 탑 노드를 디큐
            currSize -= 1               # currSize를 감소시킴
            # 디큐된 노드에 ans를 레벨로 대입
            level_labels[node_values[currNode.data]] = ans
            # 디큐된 노드의 왼쪽 자식 노드와 오른쪽 자식 노드가 있으면 인큐
            if currNode.left is not None:
                queue.append(currNode.left)
            if currNode.right is not None:
                queue.append(currNode.right)
        
        ans += 1   # 레벨값을 증가
    return ans

# 이진 트리를 구성하는 재귀함수
def insert(x, p):
    if p == None:
        p = TreeNode()
        p.data = x
    elif x < p.data:
        p.left = insert(x, p.left)
    else:
        p.right = insert(x, p.right)
    return p

# 트리의 노드 라벨과 각 노드에 대한 값을 나타내는 사전 데이터 구조
node_values = {
    10 :"v1",
    5 : "v2",
    15 :"v3",
    2 : "v4",  
    8 : "v5",
    11 :"v6",
    21 :"v7"
}

# 트리의 노드 라벨과 각 노드에 대한 높이를 나타내는 사전 데이터 구조
level_labels = {
    "v1" : 0,
    "v2" : 0,
    "v3" : 0,
    "v4" : 0,    
    "v5" : 0,
    "v6" : 0,
    "v7" : 0
}

labels = list(node_values.keys())      # node_values의 키값들을 대입
values = list(node_values.values())    # node_values의 값들을 대입
root = None                            # 트리의 루트 노드에 대한 변수 선언

# node_values의 각 노드의 값들에 대해 트리를 구성
for i in range(0, len(labels)):
    root = insert(labels[i], root)

# 해당 프로그램에 대한 안내와 탐색될 이진 트리를 그림
print("\n\t\t\t    \u250c\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2510")
print("\t\t\t    \u2502    트리의 레벨과 높이를 구하는 프로그램     \u2502")
print("\t\t\t    \u2514\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2518\n")

print("\t\t\t\t   트리는 다음 그림과 같다.: \n")
print("\t\t\t                       v\u2081        ")
print("\t\t\t                      / \     ")
print("\t\t\t                    v\u2082    v\u2083    ")
print("\t\t\t                   / \   / \    ")
print("\t\t\t                  v\u2084 v\u2085 v\u2086  v\u2087     \n\n")

# 서브 스크립트 숫자들을 위한 배열 선언 및 초기화
subscripts = ["\u2081","\u2082","\u2083","\u2084","\u2085","\u2086","\u2087" ]

# 구성된 이진 트리를 기반으로 높이를 계산해서 대입
height_of_tree = height(root, node_values, level_labels)

# 이진 트리의 각 노드에 대한 라벨을 출력
for i in range(0,len(values)):
    print(values[i],"\b",subscripts[i], end = ", ", sep = "")

print(end="\b\b의 레벨은 각각 ")
# 이진 트리의 각 노드에 대한 레벨(높이)을 출력
for i in range(0, len(level_labels)):
    print(level_labels[values[i]], end = ", ")

# 마지막으로 이진 트리의 높이를 출력 
print(end="\b\b이다. 그리고 트리의 높이는 ")
print(height_of_tree, "이다." , sep = "", end = "\n\n")
