如何创建一个返回无序二叉树最小值的函数

Question

这似乎应该很容易,但我已经有很长一段时间没遇到这个问题了.正如标题所说,我只是试图找到具有最小值的二叉树(不是BST!)中的节点并返回它.我可以很容易地写一个递归的void函数,至少可以在函数中分配最小的值,但是当我到达NULL指针时,我会陷入如何回溯到先前节点的问题.

我有一个节点类,它有一个指向左右子节点的指针,每个子节点都有自己的值.到目前为止,这是我的(失败)尝试:

int preOrder(Node *node, int value, int count, int sizeOfTree)
{
  count++; //keeps track of whether or not we have traversed the whole tree

  if(value < node->getValue())
    value = node->getValue(); 

  if(count == sizeOfTree);
    return value;

  if(node == NULL)
    //Want to return to the previous function call
    //How do I do this for a non void function? 
    //for a void function, you could jsut type "return;" and the function
    //back tracks to your previous place in the tree
    //but since I'm returning a value, How would I go about doing this?

  //these 2 calls are incorrect but the idea is that I first traverse the left subtree
  //followed by a traversal of the right subtree.
  preOrder(node->getLeft(), value);

  preOrder(node->getRight(), value);

}

如果可能的话,我想尝试在不跟踪"计数"的情况下执行此操作以使代码更清晰.如果需要澄清,请告诉我.

Answer 1

我真的不明白为什么在您的原始代码中,您需要跟踪遍历的元素数量.这是我的解决方案:

int find_min(Node* node)
{
  int value = node->getValue()

  Node* left_node = node->getLeft();
  if (left_node != NULL)
  {
    int left_value = find_min(left_node);
    if (left_value < value)
      value = left_value;
  }

  Node* right_node = node->getRight();
  if (right_node != NULL)
  {
    int right_value = find_min(right_node);
    if (right_value < value)
      value = right_value;
  }

  return value;
}