Поиск в ширину в дереве двоичного поиска в Python - PullRequest
Новая
       61

Поиск в ширину в дереве двоичного поиска в Python

0 голосов
/ 19 мая 2018

Я работал над созданием различных типов данных и применяя к ним различные алгоритмы сортировки.В настоящее время я работаю над поиском в ширину в двоичном дереве поиска.Мой код почти такой же, как и везде в Интернете, но он последовательно печатает мои значения дважды, и теперь я ошеломлен.Любое руководство будет очень ценится.

# Remove (dequeue) function for Queue class
def remove(self, current=''):
    if current == '':
        current = self.tail
    # start looping/recurring to find the front of the queue
    if current.next:
        if current.next.next:
            current = current.next
            return self.remove(current)
            # side note - I'm doubting the usefulness of recursion here
        else:
            n = current.next.value
            current.next = None
            self.size -= 1
            return n
    elif current == self.tail:
        if current.value:
            n = current.value
            current = None
            self.size -= 1
            # print("Queue is now empty - returning final number")
            return n
        else:
            return "Queue is already empty."
    else:
        raise ValueError("mind boggling error...") #never raised

# Add (enqueue) function for my queue:
def add(self,value):
    n = Node(value) # create the new node we're adding
    n.next = self.tail # point the new node to link to the old tail
    self.tail = n # now have the tail point to the new node
    self.size += 1


# Breadth First Search function for the Binary Search Tree
def bfs(self):
    """
    This is currently VERY inefficient from a memory
    standpoint, as it adds a subtree for EACH node...right?
    or is it just the names/addresses of the objects being stored in
    each node, and each node is still only in the same memory location?
    """
    queue = Queue()
    queue.add(self)
    while queue.size > 0:
        current = queue.remove()
        print(current.value)

        if current.left_child:
            queue.add(current.left_child)
        if current.right_child:
            queue.add(current.right_child)

# how I typically test:
bst = BinarySearchTree(50)
for i in range(1,10):
    bst.insert_node(i*4)
bst.bfs()

Пример вывода: 25 25 4 28 4 28 8 32 8 32 12 36 12 36 16 16 20 20 24

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

Я также должен сделать заявление об отказе от ответственности, что меня не интересует использование списков Python в моемфункции очереди.Весь смысл этого упражнения в том, чтобы вручную построить мои структуры данных без помощи предварительно созданных структур, кроме ints / strings.

Полный файл доступен на моем GitHub по адресу https://github.com/GhostlyMowgli/data_structures_plus

Опять же, любая помощь здесь будет так цениться.

1 Ответ

0 голосов
/ 19 мая 2018

Ваша проблема в вашей queue.remove функциональности, ниже приведен фиксированный код с маркером на ошибочной строке (219) 

  def remove(self, current=''):
    if current == '': 
        current = self.tail
    if current.next:
        if current.next.next:
            current = current.next
            return self.remove(current) # recursive - keep going to front
        else:
            n = current.next.value
            current.next = None
            self.size -= 1
            return n
    elif current == self.tail:
        # now I'm wondering if this is even smart
        # shouldn't I be checking if current is a None type?!?!
        if current.value:
            n = current.value
            self.tail = None # HERE!!!! NOT current = None
            self.size -= 1
            # print("Queue is now empty - returning final number")
            return n
        else:
            return "Queue is already empty."
    else:
        raise ValueError("mind boggling coding error...")
...