在这里我们将看到一个有趣的问题,我们将为一个给定的二叉搜索树中的每个节点添加更大的值。因此,初始和最终的树将如下所示 -
算法
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
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);
coutdataright);
}
}
Node* insert(Node* node, int data) {
if (node == NULL)
return getNode(data);
if (data 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 登录后复制
输出
350 330 300 260 210 150 80
登录后复制
以上就是将给定的二叉搜索树中的所有较大值添加到每个节点中的详细内容,更多请关注每日运维网(www.mryunwei.com)其它相关文章!