주어진 이진 검색 트리에서 더 큰 값을 모두 각 노드에 추가합니다.

여기서 흥미로운 문제를 볼 수 있습니다. 주어진 이진 검색 트리의 각 노드에 더 큰 값을 추가합니다. 따라서 초기 및 최종 트리는 다음과 같습니다. -

알고리즘

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

Example

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

output

350 330 300 260 210 150 80

위 내용은 주어진 이진 검색 트리에서 더 큰 값을 모두 각 노드에 추가합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!