二叉树搜索操作

Question

我尝试在python中实现二进制搜索树操作。到目前为止，我已经编写了一些代码来向这个搜索树添加节点（已排序）。 我的代码如下：

class TreeNode:

    def __init__(self, data):
        self.data = data
        self.lLink = None
        self.rLink = None

class BinaryTree:

    def __init__(self):
        self.root = None

    def AddNode(self, data):
        if self.root is None:
            self.root = TreeNode(data)
        else:
            if data < self.root.data:
                if self.root.lLink is None:
                    self.root.lLink = TreeNode(data)
                else:
                    AddNode(self.root.lLink, data)
            else:
                if self.root.rLink is None:
                    self.root.rLink = TreeNode(data)
                else:
                    AddNode(self.root.rLink, data)

    def InOrder(self, head):
        if self.root.lLink is not None:
            InOrder(self.root.lLink)
        print self.root.data,
        if self.root.rLink is not None:
            InOrder(self.root.rLink)

    myTree = BinaryTree()
    myTree.AddNode(15)
    myTree.AddNode(18)
    myTree.AddNode(14)

如何测试我的AddNode()方法是否正确？我知道算法，但只是想确定一下。 我想的是创建一个InOrder（）方法，并尝试通过这个InOrder遍历打印元素。因此，添加到树中的数据应按排序顺序显示。如果它以排序顺序显示，我将确保AddNode（）和InOrder（）方法都是正确的。在

Answer 1

插入可能有点棘手，特别是因为函数是树本身的一部分。因此，在树上调用insert函数，但是指定一个起始点。这默认为root，因此您可以在调用函数时保留参数。在

另外，我认为您对self在函数中是如何工作的有点不清楚。您不能将它作为参数传递给函数，这似乎是您所做的。在

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.rLink = None
        self.lLink = None

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

    def AddNode(self, data, node=None):
        if not node :
            node = self.root
        if self.root is None:
            self.root = TreeNode(data)
        else:
            if data < node.data:
                if node.lLink is None:
                    node.lLink = TreeNode(data)
                else:
                    self.AddNode(data, self.root.lLink)
            else:
                if node.rLink is None:
                    node.rLink = TreeNode(data)
                else:
                    self.AddNode(data, self.root.rLink)

    def InOrder(self, head):
        if head.lLink is not None:
            self.InOrder(head.lLink)
        print head.data,
        if head.rLink is not None:
            self.InOrder(head.rLink)

myTree = BinaryTree()
myTree.AddNode(14)
myTree.AddNode(15)
myTree.AddNode(18)
myTree.InOrder(myTree.root)

用顺序遍历测试insert函数是最好的方法。在

这应该行得通。如果每次都使用self.root.lLink，则不会从树上下来。 或者，您可以再编写一行代码来检查输出是否确实是按升序排列的。在

Answer 2

您的BinaryTree类有问题，将插入顺序更改为

myTree.AddNode(14)
myTree.AddNode(18)
myTree.AddNode(15)

引发错误-NameError: global name 'AddNode' is not defined。在

这是因为在AddNode(self.root.rLink, data)和AddNode(self.root.lLink, data)行中，您似乎在调用TreeNode的实例上的AddNode函数，这是不可能的。我修正了你代码中的一些错误，现在应该可以很好地工作了。在

^{pr2}$

输出测试：

>>> myTree = BinaryTree()
>>> myTree.AddNode(14)
>>> myTree.AddNode(18)
>>> myTree.AddNode(15)
>>> myTree.InOrder()
14 15 18