資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在給定的BST中，將所有更大的值新增到每個節點？
BST 或二叉搜尋樹是一種二叉樹的形式，其中所有左節點都小於根值，所有右節點都大於根值。對於這個問題，我們將取一個二叉樹，並將所有大於當前節點的值新增到它。問題“將所有大於每個節點的值新增到BST中”簡化為對於BST，將所有大於當前節點值節點的值新增到該節點值。
在BST中將所有更大的值新增到每個節點問題陳述
給定一個二叉搜尋樹 (BST)，我們需要將所有大於當前節點的值之和新增到每個節點中。
輸入
10 / \ / \ 5 20 / \ / \ 1 7 1 5
輸出
70 / \ 82 45 / \ / \ 83 77 60 25
解釋
此程式將把BST轉換為二叉樹，節點的值為所有大於元素的總和加上節點的原始值。
在二叉搜尋樹中將所有更大的值新增到每個節點的解決方案
我們使用逆序遍歷（遞迴首先呼叫右子樹而不是左子樹）並維護一個變數來儲存到目前為止已遍歷的節點的總和。
然後，我們使用此總和修改當前節點的值，首先將它的值新增到總和中，然後用此總和替換節點的值。
示例
#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;
}
更新於: 2020年7月1日
200 次瀏覽
廣告