快速广度优先搜索

Question

我对于二叉树的BFS有点疯狂。

它返回正确的元素，但似乎我多次将相同的节点插入队列。

出什么问题了？算法不应该这么难，但我似乎是在制造它。

func breadthFirstSearch(_ data: Int) -> Node? {
    var queue = [Node]()
    if (self.data == data) { return self }
    queue.append(self)
    var tempNode = queue[0]

    while queue.count > 0 {
        if (tempNode.data == data) { return tempNode }

        if let lft = tempNode.left {
            queue.append(lft)
        }
        if let rht = tempNode.right {
            queue.append(rht)
        }
        tempNode = queue[0]
        queue.remove(at: 0)

    }
    return nil
}

树在哪里

class Node: CustomStringConvertible {
    var data : Int
    var left: Node?
    var right: Node?

    init(_ data : Int) {
        self.data = data
    }
    var description: String {
        return String(data) + ((left != nil) ? left!.description : "") + ((right != nil) ? right!.description : "")
    }

    func insert(_ data: Int) {
        if (self.data > data) {
            if let lft = self.left {
                lft.insert(data)
            } else {
                let left = Node(data)
                self.left = left
            }
        }
        else {
            if let rgt = self.right {
                rgt.insert(data)
            } else {
                let right = Node(data)
                self.right = right
            }
        }
    }
 }

和插入

var binaryTree = Node(10)
binaryTree.insert(5)
binaryTree.insert(20)
binaryTree.insert(3)
binaryTree.insert(15)
binaryTree.breadthFirstSearch(4)

Answer 1

您只需要删除tempNode变量，只需始终使用队列的头：

func breadthFirstSearch(_ data: Int) -> Node? {
    var queue = [self]

    while let head = queue.first {
        queue.remove(at: 0)

        if (head.data == data) {
          return head
        }

        if let lft = head.left {
            queue.append(lft)
        }

        if let rht = head.right {
            queue.append(rht)
        }
    }
    return nil
}

您的原始实现实际上将在第一个(根)节点上迭代两次。在开始时，我也删除了不必要的复核。

现在，您还可以看到深度优先搜索的区别：

func depthFirstSearch(_ data: Int) -> Node? {
    var stack = [self]

    while let head = stack.popLast() {
        if (head.data == data) {
            return head
        }

        if let lft = head.left {
            stack.append(lft)
        }

        if let rht = head.right {
            stack.append(rht)
        }
    }
    return nil
}