Given an expression 1+2*(3-1)/5+6,

First draw an expression tree for it, a binary tree.

Operators at the same level, they will be in a ladder position, climbing up and in a sequence.

Next, look at pre-order traversal, in-order, post-order.

class TreeNode:
   def __init__(self, value):
       self.value = value
       self.left = None
       self.right = None

def preorder_traversal(root):
   if root is None:
       return
   print(root.value, end=' ')
   preorder_traversal(root.left)
   preorder_traversal(root.right)

def inorder_traversal(root):
   if root is None:
       return
   inorder_traversal(root.left)
   print(root.value, end=' ')
   inorder_traversal(root.right)

def postorder_traversal(root):
   if root is None:
       return
   postorder_traversal(root.left)
   postorder_traversal(root.right)
   print(root.value, end=' ')

# 创建表达式树
#       +
#      / \
#     *   -
#    / \ / \
#   3  2 1  4

root = TreeNode('+')
root.left = TreeNode('*')
root.right = TreeNode('-')
root.left.left = TreeNode(3)
root.left.right = TreeNode(2)
root.right.left = TreeNode(1)
root.right.right = TreeNode(4)

# 执行前序遍历
print("Pre-order Traversal:")
preorder_traversal(root)
print()

# 执行中序遍历（对于表达式树通常不是很有意义，但为了示例我们还是实现）
print("In-order Traversal:")
inorder_traversal(root)
print()

# 执行后序遍历
print("Post-order Traversal:")
postorder_traversal(root)
print()

# 执行前序遍历的非递归版本
print("Pre-order Traversal (Iterative):")
preorder_traversal_iterative(root)
print()

输出将是：

Pre-order Traversal:
+ * 3 2 - 1 4 

In-order Traversal:
3 2 * 1 4 - + 

Post-order Traversal:
3 2 * 1 4 - + 

Pre-order Traversal (Iterative):
+ * 3 2 - 1 4 

So, how to we understand this, each node has 2 children which is unlike trees that have more than 2 children, the process of tree node is in left-right order, each processing there are only 3 nodes, i.e. left,parent,right. Depending on the order of left-parent-right three, the traverse result will be different.The design pattern used here is the composite pattern, for recursion or iteration.