Действия двоичного поиска дерева

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) 

Тестирование функции вставки с обходным путем является наилучшим подходом.

Это должно сработать. Вы не спускаетесь по дереву, если используете 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) вы, кажется, вызывая AddNode функцию на экземпляры TreeNode которые не возможно. Я исправил некоторые ошибки в вашем коде, и теперь он отлично работает.

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