реализация дерева поиска в Python

Я знаю, что есть уже несколько вопросов по этой теме, но ни один из них не имеет решения моей проблемы.

Я пытаюсь построить дерево поиска, которое имеет два варианта:

  1. построить дерево

  2. получить от пользователя дерево и искать в нем (например, как список, Словарь, …)

Моя проблема со вторым вариантом ,поскольку он кажетсяAttributeError.

Когда я запускаю свой код без заданного дерева, он работает хорошо, но когда я пробую его со списком, появляется сообщение об ошибке:

    self.root.add(i)
AttributeError: 'NoneType' object has no attribute 'add'

Мой код:

import unittest
class Testfunction(unittest.TestCase):
  def test(self):
    init = SearchTree(['x', 'b', 'eee'])
    init.add('left')
    init.add('right')
    init.tolist()
    self.assertEqual(init.__contains__('left'),True )
    self.assertEqual(init.add('xx'), None )

class Node:
  def __init__(self, val):
    self.value = val
    self.left = None
    self.right = None
  def insert(self, item):
    if self.value == item:
        return False
    elif self.value > item:
        if self.left:
            return self.left.insert(item)
        else:
            self.right = Node(item)
            return True

  def find(self, item):
    if self.value == item:
        return True
    elif self.value > item:
        if self.left:
           return self.left.find(item)
        else:
           return False
    else:
        if self.right:
            return self.right.find(item)
        else:
            return False

  def tolist(self):
     if self:
         if self.left:
             self.left.tolist()
         if self.right:
             self.right.tolist()

 class SearchTree:
   def __init__(self, items=None):
    # if items . then should be inserted
     self.items = items
     self.root = None
     if items:
         for i in self.items:
             self.root.add(i)


  def __contains__(self, item):
     if self.root:
         return self.root.find(item)
     else:
         return False


  def add(self, item):
    if self.root:
        return self.root.insert(item)
    else:
        self.root  = Node(item)


  def tolist(self):
     self.root.tolist()




test = Testfunction()
test.test()

1 ответ

  1. При проверке элементов измените строку, чтобы использовать встроенное добавление.

    if items:
         for i in self.items:
             # Instead of self.root.add(i)
             self.add(i)