Двоичное дерево поиска (Python) не показывает результат - PullRequest
Новая
       8

Двоичное дерево поиска (Python) не показывает результат

0 голосов
/ 10 июня 2018

Я немного новичок в Python и мне нужна помощь в решении проблемы, с которой я сталкиваюсь.Я пытаюсь сделать двоичное дерево поиска.Я написал код, и он работает, но не показывает никакого результата (печатные значения).Я не могу понять, в чем проблема.Вот весь код: 

class Node:

    def __init__(self, value):

        self.value = value

        self.left_child = None

        self.right_child = None

class binary_search_tree:

    def __init__(self):

        self.root_node = None

    def insert(self, value, curr_node):

        if self.root_node == None:

            self.root_node == node(value)

        elif self.root_node < value:

            if self.right_child == None:

                self.right.child = value

            else:

                curr_node == self.right_child

                if curr_node < value:

                    curr_node.right_child = node(value)

                elif curr_node > value:

                    curr_node.left_child = node(value)

                else:

                    print("Error! Value Already Exists!")

        elif self.root_node > value:

            if self.left_child == None:

                self.left.child = value

            else:

                curr_node == self.left_child

                if curr_node < value:

                    curr_node.right_child = node(value)

                elif curr_node > value:

                    curr_node.left_child = node(value)

                else:

                    print("Error! Value Already Exists!")

        else:

            print("Error! Value Already Exists!")

def fill_Tree(tree, num_elems = 100, max_int = 1000):

    from random import randint

    for x in range (num, elems):

        curr_elem = randint(0, max_int)

        tree.insert(curr_elem)

        return tree

Я создал класс Node для обработки узлов и функцию вставки, которая помогает вставлять значения.Это проверка для корневого узла.Если его там, он перемещается на лист на основе значений.Если нет, это добавляет значение в качестве корня.Программа продолжает проверять значения и узлы и их различия (меньше, больше, чем и т. Д.), А также то, как дерево должно функционировать.Программа выполняется, но ничего не появляется.Не уверен, что я делаю не так.

Любая помощь будет признательна!

Спасибо.

Ответы [ 2 ]

0 голосов
/ 10 июня 2018

В настоящее время ваш метод вставки присваивает значения левому или правому потомку корня root , не перемещаясь на глубину за пределы этих двух узлов, если значение меньше левого потомка или больше правогоребенок будет найден.Вместо этого создайте один класс для хранения значения, левого и правого дочернего, вместе с необходимым методом вставки.Чтобы определить, существует ли значение в дереве, лучше использовать __getitem__ с рекурсией: 

def check_val(f): 
  def wrapper(cls, _val):
    if _val in cls.__class__.seen:
       raise ValueError(f"'{_val}' already in '{cls.__class__.__name__}'")
    return f(cls, _val)
  return wrapper

class Tree:
  seen = []
  def __init__(self, value=None):
    self.left = None
    self.value = value
    self.right = None
  def __lt__(self, _node):
    return self.value < getattr(_node, 'value', _node)
  @check_val
  def insert_val(self, _val):
    if self.value is None:
      self.value = _val
      self.__class__.seen.append(_val)
    else:
      if _val < self.value:
        if self.left is None:
           self.left = Tree(_val)
           Tree.seen.append(_val)
        else:
           self.left.insert_val(_val)
      else:
        if self.right is None:
           self.right = Tree(_val)
           Tree.seen.append(_val)
        else:
           self.right.insert_val(_val)
  def __getitem__(self, val):
     if self.value == val:
        return True
     if val < self.value:
        return getattr(self.left, '__getitem__', lambda _:False)(val)
     return getattr(self.right, '__getitem__', lambda _:False)(val)
  @classmethod
  def load_tree(cls, size = 10):
    _t = cls()
    import random
    for _ in range(size):
      _t.insert_val(random.randint(1, 100))
    return _t

Для запуска: 

t = Tree.load_tree()
print(t.__class__.seen)
#[82, 94, 33, 59, 73, 72, 96, 14, 58, 67]
for i in t.__class__.seen:
   assert t[i]
print('all cases passed')

Вывод: 

'all cases passed'
0 голосов
/ 10 июня 2018

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

Вы не делаетеесть очевидная основная функция для создания объекта class binar_search_tree.Операторы печати, которые у вас есть, только в случае ошибки .Если все работает отлично, ваш код ничего не печатает. Вам нужен метод, который может отображать дерево

...