在二进制搜索树中查找数据点的深度

我需要找到二进制搜索树中给定数据点的深度。我已经实现了一个方法和一个辅助方法countNodes()，递归计算节点。

如果我们正在搜索的数据不存在于树中，我需要返回-1。我没有看到我的递归有多可能。

@Override 
public int depth(T data) { 
    if (data == null) { 
     throw new IllegalArgumentException("Data is null"); 
    } 
    //FIXME don't use the contains() method 
    return countNodes(root, data); 
} 

/** 
* Helper method counts teh nodes 
* @param node the node we're going to start counting at 
* @param data that we're looking for 
* @return the sum of the number of children nodes 
*/ 
private int countNodes(BSTNode<T> node, T data) { 
    if (node == null) { 
     return 0; 
    } 
    if (compare(data, node.getData()) == 0) { 
     return 1; 
    } else if (compare(data, node.getData()) < 0) { 
     return 1 + countNodes(node.getLeft(), data); 
    } else if (compare(data, node.getData()) > 0) { 
     return 1 + countNodes(node.getRight(), data); 
    } else { 
     return -1; 
    } 
}

来源

2015-02-09 Nxt3

您必须检查递归函数是否返回-1，如果是，则返回-1。 – lared 2015-02-09 22:48:54

@lared我是否需要将该检查放入递归方法中？或在标准方法？ – Nxt3 2015-02-09 23:19:33

在递归中，否则你会覆盖它（IIRC，你刚刚在那里加了'1'）。 – lared 2015-02-09 23:20:34

在这种情况下的总体思路是把“未找到”的地位，在这种情况下-1，备份递归树。您可以通过检查递归调用是否返回-1来做到这一点 - 如果是，则返回-1直到调用堆栈的顶部，如果没有，则按正常进行。

来源

2015-02-10 00:04:11 lared

在二进制搜索树中查找数据点的深度

回答

相关问题