Python实现二叉树的前序遍历方法

Question

这个Python程序为什么不能正常运行呢？我想建立一个二叉树，然后按照前序遍历的方式来遍历它。当我调用PreOrder这个方法时，它什么都不返回。

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

class BTree:
    def __init__(self, root):
        self.root = root

    def CreateTree(self, root):
        self.root.data = raw_input("Enter data,'*' means empty: ")
        if self.root.data == '*':
            return
        self.root.left = Node()
        self.root.right = Node()
        self.CreateTree(self.root.left)
        self.CreateTree(self.root.right)

    def PreOrder(self, root):
        if self.root != None:
            if self.root.data != '*':
                print self.root.data,
                PreOrder(self, self.root.left)
                PreOrder(self, self.root.right)

if __name__ == '__main__':
    t = Node()
    bt = BTree(t)
    bt.CreateTree(t)
    bt.PreOrder(t)

Answer 1

因为你在 CreateTree 函数里设置了 self.root.data = '*'，是通过这行代码实现的：self.root.data = raw_input("输入数据，' * '表示空：")。为了结束输入提示，你必须在最后输入 '*'。所以你最后得到的 self.root.data 的值就是 '*'。

试试这个

    print self.root.data
    root.data = raw_input("Enter data,'*' means empty: ")
    print self.root.data
    if root.data == '*':
        return

还有这个

    def CreateTree(self,root):
        print self.root.data
        root.data = raw_input("Enter data,'*' means empty: ")
        print self.root.data
        if root.data == '*':
            return
        self.root.left = Node()
        self.root.right = Node()
        self.CreateTree(self.root.left)
        self.CreateTree(self.root.right)

    def PreOrder(self, root):
        print root
        print self.root
        print self.root.data
        if self.root != None:
            if self.root.data != '*':
                print self.root.data,
                PreOrder(self, self.root.left)
                PreOrder(self, self.root.right)
            else:
                print 'what the hell'

if __name__ == '__main__':
    t = Node(10,Node(),Node())
    print t.data
    bt = BTree(t)
    bt.CreateTree(t)
    bt.PreOrder(t)

来找出哪里出了问题。

Answer 2

如果你看看你的 CreateTree 方法，你会发现你从来没有使用过 root，所以 self.root.data 总是会是 *。如果你解决了这个问题，你的代码还有更多问题，都是和 self 以及作用域有关的。你可能想去看看 这个链接。

Answer 3

PreOrder 是 BTree 类中的一种方法，你可能想要修改递归调用的方式，像这样：

def PreOrder(self):
    if self.root != None:
        if self.root.data != '*':
            print self.root.data,
            self.root.left.PreOrder()
            self.root.right.PreOrder()

另外，如果你只是使用在 __init__ 方法中保存的 self.root，那么就不需要把 root 传给 CreateTree。