二进制搜索树中具有最小值的节点

Question

我想找到最有效的方法来检查二进制搜索树中具有最小值的节点.我现在不打算用某种编程语言来做这件事,我只想想最有效的算法.

你怎么看待这件事:

procedure minBST(t)
if (t = NULL) then return; 
if (t -> left = NULL) then return  t -> inf;  
 *// if the left node is null, then in a BST the smallest value will be the root*
if (t -> left != NULL) then .... 
 *// I need to dig more in the left side until I get the last left node*

我的问题是,在得到最后一个左节点之前,我应该如何深入挖掘.我也尝试解释这些步骤.你认为这是最好的方法吗？

Answer 1

如果你有一个合适的BST,你可以继续沿着左边的孩子走下去:

     10
   /    \
  5      12
 / \    /  \
1   6  11  14

如果节点没有左子节点(Null),则表示您当前所在的节点具有最小值.最简单的方法是通过递归:

int minBST(TreeNode node)
{
  if (node->left == Null)
    return node->value;
  else
    return minBST(node->left);
}

要开始搜索,只需使用root作为节点参数调用上面的函数.上面的树将具有如下代码路径:

• minBST(值为10的节点) - >已离开子 - > minBST(值为5的节点)
• minBST(值为5的节点) - >已离开子 - > minBST(值为1的节点)
• minBST(值为1的节点) - >没有左子节点 - >返回1

如果您的树包含n个节点并且是平衡的(在任何地方都是相同的深度),则这将采用O(log_2 n)操作,并且是没有额外簿记的最快方法.树是平衡的这一事实对于获得最佳性能非常重要,如果你想保持你的树平衡,可以看看红黑树.