Python 集合中的双端队列不是确定性的；重复执行给出不同的结果

Question

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 个不同的订单。不管逻辑如何，结果应该始终与其单线程程序相同。我不确定为什么要更改订单。

预期结果，订单 1：

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

任何帮助将不胜感激

Answer 1

二叉树本身是一致的。您的打印顺序不一致的原因来自以下行：

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

这是对 {parent.left, parent.right} 的 set 进行迭代。集合没有顺序，因此您可以先左后右或先右后左迭代。

将其更改为：

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

将使其打印一致。

Python 集合中的双端队列不是确定性的；重复执行给出不同的结果

Python deque from collections is not deterministic with order; repeated executions give different results

python

deque