6

这是我在 Python 中实现二叉树的代码片段。这在我运行 PreOrder 函数时有效。

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

class BinaryTree(Node):
    def __init__(self):
        self.root = None

    def addNode(self,data):
        return Node(data)

    def insert(self,root,data):
        if(root == None):
            root = self.addNode(data)
        else:
            if(data <= root.data):
               root.left = self.insert(root.left,data)
            else:
                root.right = self.insert(root.right,data)
        return root

    def PreOrder(self,root):
        if root == None:
            pass
        else:
            print(root.data)
            self.PreOrder(root.left)
            self.PreOrder(root.right)



a = BinaryTree()
root = a.addNode(2)
#root = None
a.insert(root,4)
a.insert(root,34)
a.insert(root,45)
a.insert(root,46)
a.insert(root,41)
a.insert(root,48)
a.PreOrder(root)

但是将 main 中的第 2 行和第 3 行更改为

#root = a.addNode(2)
root = None

不打印任何东西。我觉得我在这里错过了一些基本的东西。任何澄清将不胜感激。

4

3 回答 3

8

您正在传递None给您定义的函数：

if root == None:
    pass

这就是为什么没有打印任何内容的原因。

另外，这只是个人观点，我实际上会让 PreOrder 只接受 self 参数，然后从那里执行 PreOrder，使得递归定义变得非常简单。

基本上是这样的：

 def PreOrder(self):
     print self.data 
     if self.left:
          print self.left.PreOrder()
     if self.right:
          print self.right.PreOrder()

但这是一个偏好问题，您的解决方案工作得很好。

作为公然的宣传，我最近写了一篇关于用 Python 写一个基本的二叉树的帖子，如果你想看看，可以在这里找到：

http://intothewebs.tumblr.com/post/40256328302/embrace-the-basics-binary-tree

更新：

好的，在您发表评论后，我了解您的疑问。

传递给您的方法的根参数并没有真正改变，因为 Python 中的参数是按值传递的：

如何通过引用传递变量？

阅读这个问题中接受的答案，这太棒了，应该解释我的意思。

你们有：

root = None
a = a.insert(root,4)
a.insert...

依此类推，您的代码应该可以工作。

于 2013-01-21T13:23:35.010 回答
1

你有root = None，然后在PreOrder你的第一行是if root == None: pass所以它不会为你做任何事情。

于 2013-01-21T13:23:48.017 回答
1 
class Node:
def __init__(self,data):
    self.left = None
    self.right = None
    self.data = data

class BinaryTree:

    def __init__(self):
        self.root = None


    def insert_node(self,root,element):
        if self.root is None:
            self.root = Node(element)
        else:

            if root is None:
                root = Node(element)
            elif root.data <= element:
                root.right = self.insert_node(root.right,element)
            elif root.data > element:
                root.left = self.insert_node(root.left,element)


        return root

    def PreOrder(self,root):
        if root is not None:
            print(root.data)
            if root.left is not None:
                self.PreOrder(root.left)
            if root.right is not None:
                self.PreOrder(root.right)



a = BinaryTree()
a.insert_node(a.root,3)
a.insert_node(a.root,4)
a.insert_node(a.root,34)
a.insert_node(a.root,45)
a.insert_node(a.root,46)
a.insert_node(a.root,2)
a.insert_node(a.root,48)
a.PreOrder(a.root)
于 2014-12-17T10:23:08.137 回答