python - Python中的前序遍历

Question

我正在努力提高我的算法技能。所以，btree的前序遍历:这是我的尝试。

class Node(object):
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def preorder(node):
    if not node: return None
    print node.val
    preorder(node.left)
    preorder(node.right)


root = Node(20)
root.left = Node(8)
root.right = Node(22)
root.left.left = Node(4)
root.left.right = Node(12)
root.left.right.left = Node(10)
root.left.right.right = Node(14)
tree ="""
     20
   8    22
 4  12 10  14
"""
print tree
preorder(root)

20
8
4
12
10
14
22

但这是错误的..因为 22 应该在 12.. 之后，对吧？

Answer 1

问题出在您的 Node 作业中 -

root = Node(20)
root.left = Node(8)
root.right = Node(22)
root.left.left = Node(4)
root.left.right = Node(12)
root.left.right.left = Node(10)
root.left.right.right = Node(14)

这创建的树看起来像 -

       20
    8      22
 4    12
   10     14

为此，你得到的前序遍历是正确的。

---

对于你想要的树——

     20
   8    22
 4  12 10  14

你应该将 10 和 14 分配给 root.right.left 和 root.right.right ，不是 root.left.right.left 等。示例 -

root = Node(20)
root.left = Node(8)
root.right = Node(22)
root.left.left = Node(4)
root.left.right = Node(12)
root.right.left = Node(10)
root.right.right = Node(14)