Обход двоичного дерева поиска через цикл вместо рекурсии

Question

Кто-нибудь знает, как пересечь двоичное дерево поиска, используя циклы вместо рекурсии?

У меня есть Рекурсивный метод

public static int countMatches(BinaryNodeInterface<Integer> tree, Integer key) 
{ 
    int matches = 0; 
    if (tree != null) 
    { 
     if (tree.getData().equals(key)) 
      matches++; 
     matches += countMatches(tree.getLeftChild(), key); 
     matches += countMatches(tree.getRightChild(), key); 
    } 
    return matches; 
} 

Answer 1

Вы можете использовать сделать обход заказа уровня с использованием очередью

public static int countMatches(BinaryNodeInterface<Integer> tree, Integer key) 
{ 
    int matches = 0; 
    if (tree == null) return 0; 
    Queue<BinaryTreeNodeInterface<Integer>> queue = new LinkedList<BinaryTreeNodeInterface<Integer>>(); 
    queue.add(tree); 
    while (!queue.isEmpty()) { 
     BinaryTreeNodeInterface<Integer> current = queue.remove(); 
     if (current.getData().equals(key)) 
      matches++; 
     if (current.getLeftChild() != null) 
      queue.add(current.getLeftChild()); 
     if (current.getRightChild() != null) 
      queue.add(current.getRightChild()); 
    } 

    return matches; 
} 

Answer 2

Простого подхода будет использовать список, который проходит через него либо DEPT из широта первый.

public static int countMatches(BinaryNodeInterface<Integer> tree, Integer key) 
{ 
    ArrayList<Node> open = new ArrayList<Node>(); 
    open.add(tree.getRoot()); 
    int matches = 0; 
    while(!open.isEmpty()) 
    { 
     if(open.get(0).hasLeft()) 
      open.add(open.get(0).getLeftChild()); 
     if(open.get(0).hasRight()) 
      open.add(open.get(0).getRightChild()); 
     if(open.get(0).equals(key)) 
      ++matches; 

     open.remove(0); 
    } 
    return matches; 
} 

Это, вероятно, не самый эффективный способ сделать это, но он должен работать на то, что вы просите. Этот первый работает с глубиной, но вам не должно быть слишком сложно, если вам нужно, сначала изменить его на ширину.