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

# 전위순위 가->왼->오
def preorder(n):
    # 노드가 None이 아닐 때
    if n is not None:
        # 노드의 데이터를 출력
        print(n.data, end=' ')
        # 왼쪽 서브트리를 전위 순회
        preorder(n.left)
        # 오른쪽 서브트리를 전위 순회
        preorder(n.right)

# 중위순위 왼->가->오
def inorder(n):
    # 노드가 None이 아닐 때
    if n is not None:
        # 왼쪽 서브트리를 중위 순회
        inorder(n.left)
        # 노드의 데이터를 출력
        print(n.data, end=' ')
        # 오른쪽 서브트리를 중위 순회
        inorder(n.right)

# 후위순위 왼->오->가
def postorder(n):
    # 노드가 None이 아닐 때
    if n is not None:
        # 왼쪽 서브트리를 후위 순회
        postorder(n.left)
        # 오른쪽 서브트리를 후위 순회
        postorder(n.right)
        # 노드의 데이터를 출력
        print(n.data, end=' ')


# 노드 수 계산
def count_node(n):
    # 노드가 None일 때
    if n is None:
        return 0
    else:
        # 왼쪽 서브트리의 노드 수와 오른쪽 서브트리의 노드 수를 더한 후, 1을 더함
        return 1 + count_node(n.left) + count_node(n.right)

# 단말 노드 수 계산
def count_leaf(n):
    # 노드가 None일 때
    if n is None:
        return 0
    # 왼쪽 서브트리와 오른쪽 서브트리가 모두 None일 때
    elif n.left is None and n.right is None:
        return 1
    else:
        # 왼쪽 서브트리의 단말 노드 수와 오른쪽 서브트리의 단말 노드 수를 더함
        return count_leaf(n.left) + count_leaf(n.right) 

# 트리의 높이 계산
def calc_height(n):
    if n is not None:
        return 0
    hLeft = calc_height(n.left)
    hRight = calc_height(n.right)
    if hLeft > hRight:
        return hLeft + 1
    else:
        return hRight + 1


# 테스트 프로그램

# 트리의 노드를 만듦
d = TNode('D', None, None)
e = TNode('E', None, None)
b = TNode('B', d, e)
f = TNode('F', d, e)
c = TNode('C', f, None)
root = TNode('A', b, c)

# 전위 순회 출력
print('전위 순회 : ', end=' ')
preorder(root)

# 중위 순회 출력
print('\n중위 순회 : ', end=' ')
inorder(root)

# 후위 순회 출력
print('\n후위 순회 : ', end=' ')
postorder(root)