我正在尝试将 +1 添加到每个节点的数据中,除了具有最小数字的节点。到目前为止,我的实现没有正确进行,我在递归调用中迷失了方向。我的代码在某些情况下添加不正确,并且在必要时不添加。我明白要找到最小的数据,在这种情况下,我们会一直走到左边 (8) 连接的节点,我是否缺少某些测试条件?
Given a data set: 8, 14, 24, 29, 31, 35, 46, 58, 62,85, 95
Expected results: 8, 15, 25, 30, 32, 36, 47, 59, 63, 86, 96
Actual results: 9, 14, 25, 29, 32, 36, 46, 59, 63, 85, 96
struct node
{
node * left;
node * right;
int data;
};
int add1(node * root)
{
if(!root) return 0;
add1(root->left); //go left
if(!root->left) { //if left is NULL
if(root->right) //check if there is a right child
add1(root->right); //go to that node
else
return 0;
}
root->data += 1; //add 1 to node
add1(root->right); //go right
return 1;
}
int main()
{
node * root = NULL;
build(root); //inserts data set into our tree
display(root);
add1(root);
display(root);
return 0;
}
最佳答案
您可以沿着树向下移动,跟踪您是否可能是最左边的节点。如果您右转到达一个节点,则该节点不能在最左边。如果您可能是最左边的节点,并且您没有左 child ,那么您是最左边的节点。其他所有内容都添加了 1。
void add1(root* node, bool mightbeLeftmost=true)
{
if(!root) return;
if(!mightbeLeftmost || root->left != nullptr) ++(root->data);
add1(root->left, mightbeLeftmost);
add1(root->right, false);
}
int main()
{
//define list
...
add1(root, true);
}
关于c++ - 递归地将 1 添加到 BST 中的所有节点,除了具有 SMALLEST 数据的节点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42862870/