'''

 遍历是访问树的所有节点的过程，也可以打印它们的值。 因为所有节点都通过边(链接)连接，所以始终从根(头)节点开始。

 也就是说，我们不能随机访问树中的一个节点。 这里介绍三种方式来遍历一棵树 -顺序遍历 -前序遍历 -后序遍历

 '''

 class Node:

     def __init__(self, data):

         self.left = None

         self.right = None

         self.data = data

     def insert(self, data):

         if self.data:

             if data < self.data:

                 if self.left is None:

                     self.left = Node(data)

                 else:

                     self.left.insert(data)

             elif data > self.data:

                 if self.right is None:

                     self.right = Node(data)

                 else:

                     self.right.insert(data)

         else:

             self.data = data

     # Left -> Root -> Right  顺序遍历

     def inorderTraversal(self, root):

         res = []

         if root:

             res = self.inorderTraversal(root.left)

             res.append(root.data)

             res = res + self.inorderTraversal(root.right)

         return res

     # Root -> Left ->Right  前序遍历

     def PreorderTraversal(self, root):

         res = []

         if root:

             res.append(root.data)

             res = res + self.PreorderTraversal(root.left)

             res = res + self.PreorderTraversal(root.right)

         return res

     # Left ->Right -> Root  后序遍历

     def PostorderTraversal(self, root):

         res = []

         if root:

             res = self.PostorderTraversal(root.left)

             res = res + self.PostorderTraversal(root.right)

             res.append(root.data)

         return res

 root = Node(27)

 root.insert(14)

 root.insert(35)

 root.insert(10)

 root.insert(19)

 root.insert(31)

 root.insert(42)

 print(root.inorderTraversal(root))

 print(root.PreorderTraversal(root))

 print(root.PostorderTraversal(root))