Ajoutez toutes les valeurs plus grandes dans l'arbre de recherche binaire donné à chaque nœud

BST ou Binary Search Tree est une forme d'arbre binaire dans lequel tous les nœuds de gauche ont des valeurs inférieures à la valeur du nœud racine et tous les nœuds de droite ont des valeurs supérieures à la valeur du nœud racine. Pour ce problème, nous prendrons un arbre binaire et y ajouterons toutes les valeurs supérieures à la valeur actuelle du nœud. Le problème "ajouter toutes les valeurs plus grandes à chaque nœud d'un BST" est simplifié pour, pour un BST, ajouter toutes les valeurs de nœud supérieures à la valeur de nœud actuelle à cette valeur de nœud.

Ajoutez tous les nœuds de valeur plus grande à chaque nœud dans l'énoncé du problème BST :

Étant donné un arbre de recherche binaire (BST), nous devons ajouter pour chaque nœud la somme de tous les nœuds de valeur plus grande.

Input

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

Output

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

Explication

Ce programme convertira un arbre de recherche binaire en un arbre binaire où la valeur d'un nœud est la somme de tous les éléments plus grands plus la valeur d'origine du nœud.

Ajoutez toutes les valeurs plus grandes à chaque nœud dans la solution de l'arbre de recherche binaire :

Nous utilisons le parcours inverse dans l'ordre (appelant récursivement le sous-arbre droit en premier au lieu du sous-arbre gauche) et maintenons une variable pour stocker la somme des nœuds qui ont été parcourues jusqu'à présent.

Nous utilisons ensuite cette somme pour modifier la valeur du nœud actuel, en ajoutant d'abord sa valeur à la somme, puis en remplaçant la valeur du nœud par cette somme.

Exemple

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!