ruby - 深度优先搜索效率

Question

我已经实现了一个 DFS 方法，它接受一个搜索值和一个二叉搜索树作为参数。然后该方法在树中搜索给定值，找到后返回。

调用方法时，出现重复节点访问，可能影响效率。这次访问实际上是重复还是仅反射(reflect)了 DFS 的性质？

例如，如果我的二叉树如下所示，并且我正在寻找值 3，则搜索将从堆栈中弹出节点 5，然后是 2，然后是 1，然后 检索在找到 3 之前，再次从堆栈中取出 2 节点。这是对 2 重复的堆栈检索吗？它是适当的 DFS 吗？

     5
    / \
   /   \
  2     7
 / \   / \
1   3 6   8
     \     \
      4     9

二叉树

class Node
  attr_accessor :value, :left, :right

  def initialize(value)
    @value = value
  end
end

def build_tree(array, *indices)
  array.sort.uniq!
  mid = (array.length-1)/2
  first_element = indices[0]
  last_element = indices[1]

  if !first_element.nil? && first_element >last_element
    return nil 
  end

  root = Node.new(array[mid])
  root.left = build_tree(array[0..mid-1], 0, mid-1)
  root.right = build_tree(array[mid+1..-1], mid+1, array.length-1)

  return root
end

深度优先搜索法

def depth_first_search(search_value, tree)
  stack = [tree]
  visited = [tree]

  while !stack.empty?
    current = stack.last
    visited << current
    puts current
    p current

    if current.value == search_value
      puts current
      exit
    elsif !current.left.nil? && !visited.include?(current.left)
      if current.left.value == search_value
        puts current.left
        exit
      else
        visited << current.left
        stack << current.left
      end
    elsif !current.right.nil? && !visited.include?(current.right)
      if current.right.value == search_value
        puts current.right
        exit
      else
        visited << current.right
        stack << current.right
      end
    else
      stack.pop
    end
  end
  puts "nil"
end

方法调用

binary_tree = build_tree([1,2,3,4,5,6,7,8,9])
depth_first_search(3, binary_tree)

Answer 1

现在，因为它是 DFS，所以它是这样工作的。二叉树中的 DFS 与树的 pre-order traversal 完全一样。因此，对于图中的示例树，DFS 将像这样访问:

5-2-1-(2)-3-4-(3)-(2)-(5)-7-6-(7)-8-9

此处，括号中的值是您调用的“第二次访问”，但实际上并没有访问那些节点。所以，没关系。

此外，如果输入树是 BST(而非 DFS)，我建议使用二分搜索。