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

BST或二元搜尋樹是一種二元樹形式，其中所有左節點的值小於根節點的值，且所有右節點的值都大於根節點的值。對於這個問題，我們將取一個二元樹並將所有大於當前節點值的值加到它中。問題「在BST的每個節點上加入所有較大的值」被簡化為對於BST，將所有大於目前節點值的節點值加到該節點值。

在BST中的每個節點上加入所有較大的值問題陳述：

給定一個二元搜尋樹（BST），我們需要為每個節點添加所有較大值節點的總和。

輸入

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

輸出

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

解釋

這個程式將把一個二元搜尋樹轉換為一個二元樹，其中節點的值為所有較大元素的和加上節點的原始值。

將所有較大的值新增至二元搜尋樹解決方案中的每個節點：

我們使用逆向中序遍歷（先遞歸呼叫右子樹而不是左子樹），並維護一個變數來儲存到目前為止已經遍歷過的節點的和。

然後，我們使用這個和來修改目前節點的值，首先將其值加到和上，然後用這個和替換節點的值。

範例

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

#

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