快速广度优先搜索

本文介绍了快速广度优先搜索的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我为二进制树的BFS有点疯狂。

I'm going slightly crazy with a BFS for a binary tree.

它返回正确的元素，但似乎我将相同的Node插入队列中

It returns the correct elements, but it appears that I insert the same Node into the queue multiple times.

出了什么问题？该算法不应该那么困难，但我似乎正在努力。.

What is going wrong? The algorithm shouldn't be this difficult but I seem to be making it..

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)

推荐答案

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

You only need to remove your tempNode variable and just always use the head of the queue:

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 }

您的原始实现实际上会在第一个（根）节点上迭代两次。我也从一开始就删除了不必要的重复检查。

Your original implementation would actually iterate over the first (root) node twice. I have also removed the unnecessary double checking in the beginning.

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

Now you can also see the difference against Depth First Search:

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 }