时间戳

首页 > 解决方案 > Swift 广度优先搜索

swift - Swift 广度优先搜索

问题描述

我对二叉树的 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)

标签： swiftalgorithm

解决方案

您只需要删除您的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
}

推荐阅读