向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數據的節點以外

回答

相關問題