通過循環遍歷二叉搜索樹而不是遞歸

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

一個簡單的方法是使用通過它的任何部門運行列表寬度第一。

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; 
} 

這可能不是最有效的方法，但它應該適用於您的要求。 這是一個深入的工作，但如果你需要的話，先把它變成寬度不應該太難。