深度优先搜索效率

Question

我实现了一个DFS方法，该方法以搜索值和二进制搜索树为参数。然后，该方法在树中搜索给定的值，找到后返回。

当我调用该方法时，似乎存在重复的节点访问，这可能会影响效率。这次访问实际上是重复还是仅仅反映了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），我建议使用binary search。