指定された二分探索ツリー内のすべてのより大きな値を各ノードに追加します

BST (Binary Search Tree) は、すべての左側のノードの値がルート ノードの値およびすべての右側のノードの値よりも小さいバイナリ ツリーの形式です。ルートノードの値より大きいです。この問題では、バイナリ ツリーを取得し、現在のノード値より大きいすべての値をそれに追加します。 「より大きな値をすべて BST の各ノードに追加する」という問題は、BST の場合、現在のノード値よりも大きなすべてのノード値をそのノード値に追加するように単純化されます。

BST 問題ステートメントの各ノードに、より大きな値をすべて追加します:

二分探索木 (BST) が与えられた場合、より大きな値をすべて各ノードに追加する必要があります。ノード。

入力

    10
    /  \
   /    \
  5     20
 / \   / \
1   7   1  5

出力

      70
    /   \
   82   45
  / \   / \
83 77  60 25

説明

このプログラムは、二分探索木を、ノード値がすべて含まれる二分木に変換します。大きな要素とノードの元の値の合計。

二分探索ツリー ソリューションの各ノードに、より大きな値をすべて追加します。

逆順トラバーサル (左のサブツリーではなく最初に右のサブツリーを再帰的に呼び出す) を使用し、これまでに通過したノードの合計を格納する変数。

次に、この合計を使用して現在のノードの値を変更します。最初にその値を合計に追加し、次にノードの値をこの合計で置き換えます。

例

#include <iostream >
using namespace std;
struct node {
   int data;
   node *left;
   node *right;
};
node *newNode(int key) {
   node *temp=new node;
   temp->left=NULL;
   temp->right=NULL;
   temp->data=key;
   return temp;
}
void Inorder(node *root) {
   if(!root)
      return;
   Inorder(root->left);
   cout<<root->data<<" ";
   Inorder(root->right);
}
node *Insert(node *root,int key) {
   if(!root)
      return newNode(key);
   if(key<root->data)
      root->left=Insert(root->left,key);
   else
      root->right=Insert(root->right,key);
   return root;
}
void RevInorderAdd(node *root,int &sum) {
   if(!root)
      return;
   RevInorderAdd(root->right,sum);
   sum+=root->data;
   root->data=sum;
   RevInorderAdd(root->left,sum);
}
void AddGreater(node *root) {
   int sum=0;
   RevInorderAdd(root,sum);
}
int main() {
   /* Let us create following BST
      10
      / \
     5   20
    / \  / \
  1  7 15 25 */
   node *root = NULL;
   root = Insert(root, 10);
   Insert(root, 20);
   Insert(root, 25);
   Insert(root, 15);
   Insert(root, 5);
   Insert(root, 7);
   Insert(root, 1);
   Inorder(root);
   cout<<endl;
   AddGreater(root);
   Inorder(root);
   cout<<endl;
   return 0;
}

以上が指定された二分探索ツリー内のすべてのより大きな値を各ノードに追加しますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。