二叉搜索樹操作

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