SMALLESTデータを持つノード以外のBSTのすべてのノードに再帰的に1を加算します。

Question

最小の番号を持つノードを除くすべてのノードのデータに+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; 

} 

Answer 1

ツリーを下りて、最も左のノードであるかどうかを追跡できます。ノードに到達するために右折した場合、そのノードは一番左に置くことはできません。一番左のノードで、左の子がない場合、はです。一番左のノードです。他にはすべて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); 
} 

Answer 2

ここでは、最小の値を除いてすべてをインクリメントするだけでなく、最小の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; 
}