这似乎应该很容易,但我已经有很长一段时间了。正如标题所说,我只是想在二叉树(不是 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);
}
如果可能的话,我想尝试在不跟踪“计数”的情况下执行此操作,以使代码更清晰。让我知道是否需要进一步澄清。