將給定的二元搜尋樹中的所有較大值新增至每個節點中

在這裡我們將看到一個有趣的問題，我們將為一個給定的二元搜尋樹中的每個節點添加更大的值。因此，初始和最終的樹將如下所示-

演算法

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

以上是將給定的二元搜尋樹中的所有較大值新增至每個節點中的詳細內容。更多資訊請關注PHP中文網其他相關文章！