Fügen Sie jedem Knoten alle größeren Werte im angegebenen binären Suchbaum hinzu

BST oder Binary Search Tree ist eine Form eines Binärbaums, in dem alle linken Knoten Werte haben, die kleiner als der Wert des Wurzelknotens sind, und alle rechten Knoten Werte haben, die größer als der Wert des Wurzelknotens sind. Für dieses Problem nehmen wir einen Binärbaum und fügen ihm alle Werte hinzu, die größer als der aktuelle Knotenwert sind. Das Problem „Füge alle größeren Werte zu jedem Knoten eines BST hinzu“ wird vereinfacht, indem für einen BST alle Knotenwerte, die größer als der aktuelle Knotenwert sind, zu diesem Knotenwert addiert werden.

Fügen Sie alle Knoten mit größerem Wert zu jedem Knoten in der BST-Problemstellung hinzu:

Bei einem binären Suchbaum (BST) müssen wir für jeden Knoten die Summe aller Knoten mit größerem Wert addieren.

Eingabe

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

Ausgabe

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

Erläuterung

Dieses Programm wandelt einen binären Suchbaum in einen binären Baum um, in dem der Wert eines Knotens die Summe aller größeren Elemente plus dem ursprünglichen Wert des Knotens ist.

Fügen Sie alle größeren Werte zu jedem Knoten in der binären Suchbaumlösung hinzu:

Wir verwenden die umgekehrte Inorder-Traversierung (rufen rekursiv zuerst den rechten Teilbaum anstelle des linken Teilbaums auf) und verwalten eine Variable zum Speichern der Summe der Knoten wurden bisher durchquert.

Wir verwenden diese Summe dann, um den Wert des aktuellen Knotens zu ändern, indem wir zunächst seinen Wert zur Summe addieren und dann den Wert des Knotens durch diese Summe ersetzen.

Beispiel

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

Das obige ist der detaillierte Inhalt vonFügen Sie jedem Knoten alle größeren Werte im angegebenen binären Suchbaum hinzu. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!