資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝學
法學在 C++ 中將所有大於節點的值新增到給定 BST 的每個節點？
BST 或二叉搜尋樹是一種二叉樹，其所有左子節點都小於根值，所有右子節點都大於根值。對於這個問題，我們將採用二叉樹並將所有大於當前節點的值新增到其中。“將所有大於節點的值新增到 BST 的每個節點中”這個問題簡化為：對於 BST，將所有大於當前節點值的值新增到該節點值中。
將所有大於節點的值新增到 BST 中的每個節點中 問題陳述 -
給定一個二叉搜尋樹 (BST)，我們需要為每個節點新增所有大於該節點的值的總和。
說明
此程式將把 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;
}
更新於： 2019年10月24日
82 次檢視
廣告