BFS - 树遍历

Question

我尝试使用 BFS 方法遍历以下员工数组。

array = [
  ["alice", "bob", "joseph"],
  ["bob", "tom", "richard"],
  ["richard", "michelle", "amy"],
  ["joseph", "elaine", "albert"],
  ["albert", "colin", "liam"]
]

此数组未排序，但它表示公司中的经理树。对于数组中的每个项目，索引 0 是经理，而索引 1 和 2 是经理的下属。基本上，它是一棵看起来像这样的树：

              alice
            /       \
         bob         joseph
        /   \         /    \
     tom  richard  elaine  albert
          /   \            /  \
   michelle   amy      colin  liam

我们的输出应该完全匹配：

需要准确的输出：

alice
bob joseph
tom richard elaine albert
michelle amy colin liam

我试过了，但它只显示了节点。

array = [
    ["alice", "bob", "joseph"],
    ["bob", "tom", "richard"],
    ["richard", "michelle", "amy"],
    ["joseph", "elaine", "albert"],
    ["albert", "colin", "liam"]
]

new_array = Array.new

def treverse(array,new_array)
    final_array = Array.new
    arr = array.shift
    i = true
    arr.each do |b|
        unless new_array.include?(b)
            
            new_array.push(b)
        end
        array.each do |c|
            if c.include?(b)
                treverse(array, new_array)
            end
        end
    end
    return 
end

treverse(array,new_array)

new_array.each do |p|
    puts p
end

Answer 1

我不确定你是否可以只在给定的数组上完成它。

我将从将数组转换为实际的树结构开始。例如，您可以使用 Node class 和 name（例如 "alice"）以及 left 和 right 属性，指的是 child 个节点：

Node = Struct.new(:name, :left, :right)

要填充节点，我们可以使用辅助哈希：

nodes = Hash.new { |h, k| h[k] = Node.new(k) }
array.each do |name, left, right|
  nodes[name].left = nodes[left]
  nodes[name].right = nodes[right]
end

root = nodes['alice']
#=> #<struct Node name="alice", left=#<struct Node name="bob" ...>, right=... >

现在，要以 breadth-first 方式遍历（并打印）这棵树，我们可以使用这样的东西：

def traverse(node)
  row = [node]
  until row.empty?
    puts row.map(&:name).join(' ')
    row = row.flat_map { |n| [n.left, n.right] }.compact
  end
end

traverse(root)

我们的想法是构建最上面的“行”，它只是我们的根节点：[node]。然后我们打印行的名称并从当前行的 left 和 right child-nodes 创建 follow-up 行。我们重复直到运行个节点，即 row 变为空。

输出：

alice
bob joseph
tom richard elaine albert
michelle amy colin liam

BFS - 树遍历

BFS - TreeTraversal

ruby

data-structures

tree

traversal

tree-traversal