二叉搜索树操作

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

插入可能有点棘手，特别是因为函数是树本身的一部分。所以，你在树上调用了插入函数，但是指定了一个起点。这默认为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) 

使用按顺序遍历测试插入函数是最好的方法。

这应该工作。如果您每次使用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功能，是不可能的。我修正了代码中的一些错误，现在它应该很好。

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: 
      self.AddHelper(data, self.root) 

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

    def InOrder(self): 
     self.InOrderHelper(self.root) 

    def InOrderHelper(self, startingPoint): 
     if startingPoint is None: 
      return 
     self.InOrderHelper(startingPoint.lLink) 
     print startingPoint.data, 
     self.InOrderHelper(startingPoint.rLink) 

输出测试：

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