# -*- coding: UTF-8 -*-


class Node(object):
    def __init__(self, val):
        self.__val = val
        self.__left = None  # 聲明一個成員屬性
        self.__right = None

    def set_val(self, val):
        self.__val = val

    def set_left(self, left):
        self.__left = left

    def set_right(self, right):
        self.__right = right

    def get_val(self):
        return self.__val

    def get_left(self):
        return self.__left

    def get_right(self):
        return self.__right


# 前序遍歷
def pre_order_traverse(root):
    if root is None:
        return

    print(root.get_val())
    pre_order_traverse(root.get_left())
    pre_order_traverse(root.get_right())


# 中序遍歷
def in_order_traverse(root):
    if root is None:
        return

    in_order_traverse(root.get_left())
    print(root.get_val())
    in_order_traverse(root.get_right())


# 后序遍歷
def post_order_traverse(root):
    if root is None:
        return

    post_order_traverse(root.get_left())
    post_order_traverse(root.get_right())
    print(root.get_val())


# 定義一棵二叉樹
#       1
#       /\
#      2  3
#      /\  \
#     4  5  6

node1 = Node(1)
node2 = Node(2)
node1.set_left(node2)
node3 = Node(3)
node1.set_right(node3)
node4 = Node(4)
node2.set_left(node4)
node5 = Node(5)
node2.set_right(node5)
node6 = Node(6)
node3.set_right(node6)

# 前序遍歷
print("前序遍歷")
pre_order_traverse(node1)

# 中序遍歷
print("中序遍歷")
in_order_traverse(node1)

# 后序遍歷
print("后序遍歷")
post_order_traverse(node1)