Maison > développement back-end > C++ > le corps du texte

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

WBOY
Libérer: 2023-09-07 12:17:04
avant
1298 Les gens l'ont consulté

Ajoutez toutes les valeurs plus grandes dans larbre 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
Copier après la connexion

Output

      70
    /   \
   82   45
  / \   / \
83 77  60 25
Copier après la connexion

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;
}
Copier après la connexion

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!

Étiquettes associées:
source:tutorialspoint.com
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal