使用 Ruby 打印广度优先搜索

Question

通过 Web 探索各种示例，我似乎无法使用广度优先示例实现打印我的二叉树。我在 #printf(children=nil) 中得到了 children=nil 的提示，但无法进行任何操作。我提供了创建队列 array 或两个的想法，但我的特定功能不执行搜索或传递任何参数。我只是想从顶部节点向下打印我的树。

二叉树的输出

=> #<BinarySearchTree:0x007fbe40b044c8 @root=#<Node:0x007fbe40b044f0 @title="The Matrix", @rating=87, @parent=nil, @left=#<Node:0x007fbe40b04478 @title="Pacific Rim", @rating=72, @parent=#<Node:0x007fbe40b044f0 ...>, @left=nil, @right=#<Node:0x007fbe40b04428 @title="Braveheart", @rating=78, @parent=#<Node:0x007fbe40b04478 ...>, @left=nil, @right=nil>>, @right=#<Node:0x007fbe40b042e8 @title="District 9", @rating=90, @parent=#<Node:0x007fbe40b044f0 ...>, @left=nil, @right=#<Node:0x007fbe40b04298 @title="The Shawshank Redemption", @rating=91, @parent=#<Node:0x007fbe40b042e8 ...>, @left=nil, @right=nil>>>>

函数的输出应该如下所示：

The Matrix: 87
Pacific Rim: 72
District 9: 90
Braveheart: 78
Shawshank: 91
...

我的打印功能

def printf(children=nil)
  current = @root
  queue = [current]

  if current.left && current.right
    queue << current.left << current.right
    puts queue.methods.sort
  elsif current.right
    queue << current.right
  end

  queue.each do |i|
    #print out my created array
  end
end

对于如何在给出这个特定示例的二叉树对象中移动以及我现在所拥有的东西不起作用感到困惑，尤其是当树扩展时。想法或建议？

Answer 1

Tree中层序遍历的灵感来自于Graph的BFS，层序中我们使用queue来遍历树，不断推左右节点，直到队列为空或找到节点（如果我们寻找一个）。这是相同的典型示例：

def bfs(node)
  return nil if node.nil? || root.nil? # nothing to do if there is no node or root to begin the search
  queue = Queue.new
  queue.enq(root)
  result = nil
  while !queue.empty?
    value = queue.deq
    if value.title == node.title && value.rating == node.rating
      result = value
      break
    end

    # keep moving the levels in tree by pushing left and right nodes of tree in queue
    queue.enq(value.left) if value.left
    queue.enq(value.right) if value.right
  end

  result # returns node found in BST else default value nil
end

假设 root 是 BST class 中的一个 getter 方法。 Class Queue 在 Ruby 中可用线程。您可能必须在代码中执行 require 'thread' 才能在代码中使用它。

时间复杂度：O(n)

Space 复杂度：队列的 O(n)。

Answer 2

从上面修改

  def printf(node)
    return nil if node.nil?
    queue = Queue.new
    queue.enq(node)
    result = nil
    while !queue.empty?
      value = queue.deq
      puts value.title if !value.title.nil?
      # keep moving the levels in tree by pushing left and right nodes of tree in queue
      queue.enq(value.left) if value.left
      queue.enq(value.right) if value.right
    end
  end

使用 Ruby 打印广度优先搜索

Printing out Breadth First Search using Ruby

ruby

tree

binary-tree

ruby-on-rails

breadth-first-search