Python中的预排序遍历

Question

我想复习一下我的算法技能。那么，b树的预序遍历:这是我的尝试。

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)

Answer 2

您正在形成的树不是您在代码中表示的树。你的python方法工作正常，根据输入给它。

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

根据你正在创建的树，所有的东西都是在左子树中创建的，而不是创建一个平衡的树。