Python дек из коллекций не детерминирован c при заказе; повторные казни дают разные результаты - PullRequest
Новая
       50

Python дек из коллекций не детерминирован c при заказе; повторные казни дают разные результаты

3 голосов
/ 25 февраля 2020 
from collections import deque

class Node(object):
    def __init__(self,val):
        self.value = val
        self.right = None
        self.left = None

class Btree:
    def __init__(self):
        self.root = None

    def btree_print(self):
        if self.root:
            print("Values of btree are")
            q = deque()
            q.append(self.root)
            q.append(None)

            while q:
                parent = q.popleft()
                if parent is None:
                    print("End of  a Level")
                    if q:
                        q.append(None)
                    continue

                print("Value of btree Elm:", parent.value)

                for child in {parent.left, parent.right}:
                    if child:
                        q.append(child)

        else:
            print("Btree Empty")

    def btree_insert_helper(self, val):
        q = deque()
        q.append(self.root)

        while q:
            node = q.popleft()
            for child in {node.left, node.right}:
                if child:
                    q.append(child)
                elif node.left:
                    node.right = Node(val)
                    return
                else:
                    node.left = Node(val)
                    return

    def btree_insert(self, val):
        if self.root:
            self.btree_insert_helper(val)
        else:
            self.root = Node(val)

btree = Btree()
btree.btree_insert(1)
btree.btree_insert(2)
btree.btree_insert(3)
btree.btree_insert(4)
btree.btree_insert(5)
btree.btree_insert(6)
btree.btree_insert(7)

btree.btree_print()

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

Ожидаемый результат, Order1: 

Values of btree are
Value of btree Elm: 1
End of  a Level
Value of btree Elm: 2
Value of btree Elm: 3
End of  a Level
Value of btree Elm: 4
Value of btree Elm: 5
Value of btree Elm: 6
Value of btree Elm: 7
End of  a Level

Не ожидается, но иногда программа дает следующий результат (4, 5 переключается на 5, 4 ), Order2: 

Values of btree are
Value of btree Elm: 1
End of  a Level
Value of btree Elm: 2
Value of btree Elm: 3
End of  a Level
Value of btree Elm: 5
Value of btree Elm: 4
Value of btree Elm: 6
Value of btree Elm: 7
End of  a Level

любая помощь будет принята с благодарностью

1 Ответ

3 голосов
/ 25 февраля 2020

Само двоичное дерево является последовательным. Причина того, что ваш заказ на печать является несовместимым, исходит из строки: 

for child in {parent.left, parent.right}:

Это повторение по set из {parent.left, parent.right}. Наборы не имеют порядка, поэтому вы можете выполнять итерацию влево, вправо или вправо, затем влево.

Если изменить его на: 

for child in (parent.left, parent.right):

, вы получите последовательную печать.

...