二叉搜索树上广度优先搜索的Python实现

Question

我正在尝试使用 Python3 为二叉搜索树编写 BFS 算法。

我首先初始化了这个类，定义了一个插入方法，并插入了一些随机数:

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

    def insert(self, data):
        if data <= self.data:
            if self.left == None:
                self.left = Node(data)
            else:
                self.left.insert(data)
        else:
            if self.right == None:
                self.right = Node(data)
            else:
                self.right.insert(data)

root = Node(1)
root.insert(0)
root.insert(2)
root.insert(1.5)
root.insert(2.4)
root.insert(1.6)
root.insert(2.3)

然后，我试着写了一个递归的 BFS 方法:

    def inLineTraversal(self, queue=[]):
        if queue == []:   # Base condition
            return
        temp = queue
        for node in temp:
            print(node.data) 
            if node.left != None:
                queue.append(node.left)
            if node.right != None:
                queue.append(node.right)
            queue.pop(0)
        self.inLineTraversal(queue)

然而，这产生了 1,2,2.4,1.5,2.3,2.3,1.6与 1,0,2,1.5,2.4,1.6,2.3 的正确结果相反.

后来我使用了一个 while 循环来执行 BFS，它正确地产生了 1,0,2,1.5,2.4,1.6,2.3 :

    def inLineTraversal(self):
        queue = [self]
        while queue != []:
            s = queue.pop(0)
            print(s.data)
            if s.left != None:
                queue.append(s.left)
            if s.right != None:
                queue.append(s.right)

递归解决方案有什么问题？

Answer 1

问题出在这一行:

temp = queue

这不会创建 queue 的新副本，正如您可能预期的那样，它只是给它一个额外的名称 temp - 但两个名字都指向同一个列表。

因此，进一步地，您在修改此列表的同时对其进行迭代，这几乎总是会导致问题。

只需创建列表的副本，例如:

temp = queue[:]

一切正常

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

    def insert(self, data):
        if data <= self.data:
            if self.left == None:
                self.left = Node(data)
            else:
                self.left.insert(data)
        else:
            if self.right == None:
                self.right = Node(data)
            else:
                self.right.insert(data)

    def inLineTraversalRecursive(self, queue=[]):
        if queue == []:   # Base condition
            return
        temp = queue[:]
        for node in temp:
            print(node.data) 
            if node.left != None:
                queue.append(node.left)
            if node.right != None:
                queue.append(node.right)
            queue.pop(0)
        self.inLineTraversal(queue)

    def inLineTraversalLoop(self):
        queue = [self]
        while queue != []:
            s = queue.pop(0)
            print(s.data)
            if s.left != None:
                queue.append(s.left)
            if s.right != None:
                queue.append(s.right)

root = Node(1)
root.insert(0)
root.insert(2)
root.insert(1.5)
root.insert(2.4)
root.insert(1.6)
root.insert(2.3)
root.inLineTraversalLoop()
print()
root.inLineTraversalRecursive([root])

输出:

1
0
2
1.5
2.4
1.6
2.3

1
0
2
1.5
2.4
1.6
2.3