向BST中的所有节点递归地添加1，除了具有SMALLEST数据的节点以外

我试图给每个节点的数据添加+1，除了具有最小数字的节点之外。到目前为止，我的实现不正确，我在递归调用中迷路了。我的代码在某些情况下添加不正确，在必要时不添加。我明白要找到最小的一块数据，我们继续向左连接的节点（8），在这种情况下，我是否缺少某些测试条件？向BST中的所有节点递归地添加1，除了具有SMALLEST数据的节点以外

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; 

}

来源

2017-03-17 some dude

对不起，你的意思是添加我的节点的结构？ –

yep节点声明和初始化 – em2er

您可以下降树，跟踪您是否可能是最左边的节点。如果您曾经右转到达节点，那么该节点不能位于最左侧。如果你可能是最左边的节点，并且你没有离开的孩子，那么你的是最左边的节点。其他一切都已添加。

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); 
}

来源

2017-03-17 16:50:40 Smeeheey

这是一个二叉搜索树。你不需要遍历整个树来发现最低值。最低值始终是树中最左边的值。 –

哦，是的，我错过了那部分。将调整 – Smeeheey

下面是一个有额外好处的函数的解决方案：除了递增除最小值之外的所有值，它还返回最小BST值。如果最小值不是唯一的，它也可以工作。

#include <limits.h> 

... 

int add1(struct node* root) 
{ 
     static int min; 

     if (root == NULL) 
      return INT_MAX; 

     int lval = add1(root->left); 

     // Check if it's the leftmost node to set min 
     if (lval == INT_MAX) 
      min = root->data; 

     add1(root->right); 

     if (root->data != min) 
      root->data++; 

     return min; 
}

来源

2017-03-17 18:50:47 DigiGen

向BST中的所有节点递归地添加1，除了具有SMALLEST数据的节点以外

回答

相关问题