قم بتحويل BST إلى Binary Tree بحيث يتم إضافة مجموع كل المفاتيح الأكبر إلى كل مفتاح


مستوى الصعوبة متوسط
كثيرا ما يطلب في Facebook
شجرة البحث الثنائية شجرة ثنائية شجرة

بالنظر إلى شجرة بحث ثنائية ، اكتب خوارزمية لتحويل BST إلى ثنائي شجرة بحيث يتم إضافة مجموع كل المفاتيح الأكبر إلى كل مفتاح.

مثال

إدخال

قم بتحويل BST إلى Binary Tree بحيث يتم إضافة مجموع كل المفاتيح الأكبر إلى كل مفتاح

الناتج

قم بتحويل BST إلى Binary Tree بحيث يتم إضافة مجموع كل المفاتيح الأكبر إلى كل مفتاح

طلب مسبق: 81 87 88 54 69 34

نهج ساذج

الفكرة بسيطة جدا ، طريق مختصر جميع العقد واحدة تلو الأخرى ، ولكل عقدة مرة أخرى اجتياز الشجرة بأكملها وإيجاد مجموع العقد أكبر منها. قم بتخزين المجموع في مصفوفة وبعد الحساب ، قم بزيادة العقد بمجموعها المقابلة. هذا الأسلوب قابل للتطبيق على أي شجرة ثنائية عامة وليس بشكل خاص لـ BST.

  1. اجتياز BST المحدد في شكل بالترتيب.
  2. لكل عقدة ، اجتياز الشجرة مرة أخرى في شكل بالترتيب وابحث عن مجموع جميع العقد الأكبر من العقدة الحالية.
  3. تخزين المجموع في مصفوفة أو قائمة.
  4. بعد اجتياز جميع العقد ، اجتياز الشجرة مرة أخرى في شكل مرتب وزاد كل عقدة بمجموعها المقابل في المصفوفة أو القائمة.

تعقيد الوقت = على2)
تعقيد الفضاء = أوه)
حيث n هو عدد العقد في الشجرة.

كود جافا لتحويل BST إلى شجرة ثنائية

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class ConvertABSTToABinaryTreeSuchThatSumOfAllGreaterKeysIsAddedToEveryKey {
    // class representing the node of a binary tree
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
        }
    }

    // function to print the pre-order traversal of a binary tree
    private static void preOrder(Node root) {
        if (root != null) {
            System.out.print(root.data + " ");
            preOrder(root.left);
            preOrder(root.right);
        }
    }

    private static int findSum(Node root, int value) {
        // if root is null, sum is 0
        if (root == null) {
            return 0;
        }

        // initialize sum as 0
        int sum = 0;

        // traverse the tree and find the sum of all the values greater than value
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            Node curr = queue.poll();
            if (curr.data > value) {
                sum += curr.data;
            }

            if (curr.left != null)
                queue.add(curr.left);
            if (curr.right != null)
                queue.add(curr.right);
        }

        // return sum
        return sum;
    }

    private static void formSumList(Node root, Node curr, ArrayList<Integer> sumList) {
        // traverse the tree in in-order form and for each node
        // calculate the sum of elements greater than it
        if (curr != null) {
            formSumList(root, curr.left, sumList);

            // Check for all the nodes to find the sum
            int sum = findSum(root, curr.data);
            sumList.add(sum);

            formSumList(root, curr.right, sumList);
        }
    }

    private static void  convertToGreaterSumTree(Node root, ArrayList<Integer> sumList) {
        // traverse the tree in in-order form and for each node
        // increment its value by sum
        if (root != null) {
            convertToGreaterSumTree(root.left, sumList);

            // increment this value
            root.data += sumList.get(0);
            sumList.remove(0);

            convertToGreaterSumTree(root.right, sumList);
        }
    }

    public static void main(String[] args) {
        // Example Tree
        Node root = new Node(12);
        root.left = new Node(6);
        root.right = new Node(20);
        root.left.left = new Node(1);
        root.right.left = new Node(15);
        root.right.right =  new Node(34);

        ArrayList<Integer> sumList = new ArrayList<>();
        formSumList(root, root, sumList);

        convertToGreaterSumTree(root, sumList);

        preOrder(root);
        System.out.println();
    }
}
81 87 88 54 69 34

كود C ++ لتحويل BST إلى شجرة ثنائية

#include <iostream> 
#include<vector> 
#include<queue> 
using namespace std; 

// class representing node of a binary tree 
class Node { 
    public: 
    int data; 
    Node *left; 
    Node *right; 
    
    Node(int d) { 
        data = d; 
        left = right = NULL; 
    } 
}; 

// function to print the preorder traversal of a binary tree 
void preOrder(Node *root) { 
    if (root != NULL) { 
        cout<<root->data<<" "; 
        preOrder(root->left); 
        preOrder(root->right); 
    } 
} 

int findSum(Node *root, int value) { 
    // if root is null, sum is 0 
    if (root == NULL) { 
        return 0; 
    } 
    
    // initialize sum as 0 
    int sum = 0; 
    
    // traverse the tree and find the sum of all the values greater than value 
    queue<Node*> q; 
    q.push(root); 
    while (!q.empty()) { 
        Node *curr = q.front(); 
        q.pop(); 
        if (curr->data > value) { 
            sum += curr->data; 
        } 
        if (curr->left != NULL) { 
            q.push(curr->left); 
        } 
        if (curr->right != NULL) { 
            q.push(curr->right); 
        } 
    } 
    
    // return sum 
    return sum; 
} 

void formSumList(Node *root, Node *curr, vector<int> &sumList) { 
    // traverse the tree in in-order form and for each node 
    // calculate the sum of elements greater than it 
    if (curr != NULL) { 
        formSumList(root, curr->left, sumList); 
        
        // Check for all the nodes to find the sum 
        int sum = findSum(root, curr->data); 
        sumList.push_back(sum); 
        formSumList(root, curr->right, sumList); 
    } 
} 

void convertToGreaterSumTree(Node *root, vector<int> &sumList) { 
    // traverse the tree in in-order form and for each node 
    // replace its value with the corresponding sum 
    if (root != NULL) { 
        convertToGreaterSumTree(root->left, sumList); 
        // change this value 
        root->data += sumList[0]; 
        sumList.erase(sumList.begin()); 
        convertToGreaterSumTree(root->right, sumList); 
    } 
} 

int main() { 
    // Example Tree 
    Node *root = new Node(12); 
    root->left = new Node(6); 
    root->right = new Node(20); 
    root->left->left = new Node(1); 
    root->right->left = new Node(15); 
    root->right->right = new Node(34); 
    
    vector<int> sumList; 
    formSumList(root, root, sumList); 
    
    convertToGreaterSumTree(root, sumList); 
    preOrder(root); 
    cout<<endl; 
    
    return 0; 
}
81 87 88 54 69 34

النهج الأمثل

يمكن تحسين الأسلوب أعلاه من أجل BST ، حيث يقوم BST بتخزين البيانات بطريقة محددة للغاية.
اجتياز BST بالترتيب العكسي ، أي اليمين> الجذر> النموذج الأيسر. بهذه الطريقة سوف نجتاز العقد بترتيب تنازلي وقبل زيارة أي عقدة سنزور العقد الأكبر منها ، وبالتالي يمكننا العثور على مجموع جميع العقد الأكبر من العقدة في اجتياز واحد فقط ، وبالتالي خلال هذه الزيادة الاجتيازية لكل عقدة بمجموع العقد أكبر منه.

  1. قم بتهيئة مجموع متغير كـ 0 ، يتم تمريره من خلال المرجع أو تحديده بشكل عام.
  2. اجتياز BST في شكل ترتيب عكسي ، وبهذه الطريقة سنحصل على البيانات بترتيب تنازلي.
  3. لكل عقدة نجتازها ، نزيد قيمتها بالمجموع ، ونزيد المجموع بالقيمة الأصلية للعقدة (قبل التحديث).

تعقيد الوقت = O (ن)
تعقيد الفضاء = أوه)
حيث n هو العدد الإجمالي للعقد في BST المعطى.

كود جافا لتحويل BST إلى شجرة ثنائية

public class ConvertABSTToABinaryTreeSuchThatSumOfAllGreaterKeysIsAddedToEveryKey {
    // class representing node of a binary tree
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
        }
    }

    // function to print the pre-order traversal of a binary tree
    private static void preOrder(Node root) {
        if (root != null) {
            System.out.print(root.data + " ");
            preOrder(root.left);
            preOrder(root.right);
        }
    }

    // sum defined globally and initialized as 0
    private static int sum = 0;

    private static void convertToGreaterSumTree(Node root) {
        // traverse the tree in reverse in-order form
        if (root != null) {
            convertToGreaterSumTree(root.right);

            // update the sum and increment the node's value
            int prevValue = root.data;
            root.data += sum;
            sum += prevValue;

            convertToGreaterSumTree(root.left);
        }
    }

    public static void main(String[] args) {
        // Example Tree
        Node root = new Node(12);
        root.left = new Node(6);
        root.right = new Node(20);
        root.left.left = new Node(1);
        root.right.left = new Node(15);
        root.right.right =  new Node(34);

        convertToGreaterSumTree(root);

        preOrder(root);
        System.out.println();
    }
}
81 87 88 54 69 34

كود C ++ لتحويل BST إلى شجرة ثنائية

#include <iostream>
#include<vector>
#include<queue>
using namespace std;

// sum defined globally and initialized as 0
int sum = 0;

// class representing node of a binary tree
class Node {
    public:
    int data;
    Node *left;
    Node *right;
    
    Node(int d) {
        data = d;
        left = right = NULL;
    }
};

// function to print the preorder traversal of a binary tree
void preOrder(Node *root) {
    if (root != NULL) {
        cout<<root->data<<" ";
        preOrder(root->left);
        preOrder(root->right);
    }
}

void convertToGreaterSumTree(Node *root) {
    // traverse the tree in reverse in-order form
    if (root != NULL) {
        convertToGreaterSumTree(root->right);
        
        // update the sum and the node's value
        int prevValue = root->data;
        root->data += sum;
        sum += prevValue;
        
        convertToGreaterSumTree(root->left);
    }
}

int main() {
    // Example Tree
    Node *root = new Node(12);
    root->left = new Node(6);
    root->right = new Node(20);
    root->left->left = new Node(1);
    root->right->left = new Node(15);
    root->right->right =  new Node(34);

    convertToGreaterSumTree(root);

    preOrder(root);
    cout<<endl;
    
    return 0;
}
81 87 88 54 69 34

Reference1     مرجع 2