Heim >Backend-Entwicklung >C++ >Fügen Sie jedem Knoten alle größeren Werte im angegebenen binären Suchbaum hinzu
Hier sehen wir ein interessantes Problem: Wir werden jedem Knoten in einem bestimmten binären Suchbaum einen größeren Wert hinzufügen. Der anfängliche und endgültige Baum sieht also so aus:
bstUpdate(root, sum) -
Begin if root is null, then stop bstUpdate(right of room, sum) sum := sum + value of root update root value using sum bstUpdate(left of room, sum) End
#include<iostream> using namespace std; class Node { public: int data; Node *left, *right; }; Node *getNode(int item) { Node *newNode = new Node(); newNode->data = item; newNode->left = newNode->right = NULL; return newNode; } void updateBST(Node *root, int *sum) { if (root == NULL) return; updateBST(root->right, sum); //update right sub tree *sum = *sum + root->data; root->data = *sum; //update root data updateBST(root->left, sum); //update left sub tree } void BSTUpdate(Node *root) { int sum = 0; updateBST(root, &sum); } void inorder(Node *root) { if (root != NULL) { inorder(root->left); cout<<root->data<<" "; inorder(root->right); } } Node* insert(Node* node, int data) { if (node == NULL) return getNode(data); if (data <= node->data) //go to left node->left = insert(node->left, data); else //go to right node->right = insert(node->right, data); return node; } int main() { int data[] = {50, 30, 20, 40, 70, 60, 80}; int n = sizeof(data)/sizeof(data[0]); Node *root = NULL; for(int i = 0; i < n; i++) { root = insert(root, data[i]); } BSTUpdate(root); inorder(root); }
350 330 300 260 210 150 80
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!