जावास्क्रिप्ट में BinarySearchTree क्लास

यहां BinarySearchTree क्लास का पूरा कार्यान्वयन है:

उदाहरण

class BinarySearchTree {
    constructor() {
        // रूट एलिमेंट को नल से इनिशियलाइज़ करें।
        this.root = null;
    }
    insertIter(data) {
        let node = new this.Node(data);
        // जांचें कि ट्री खाली है या नहीं
        if (this.root === null) {
            // पहले एलिमेंट के रूप में इंसर्ट करें
            this.root = node;
            return;
        }
        let currNode = this.root;
        while (true) {
            if (data < currNode.data) {
                // यहां वैल्यू सेट करें क्योंकि हम लीफ नोड पर पहुंच गए हैं
                if (currNode.left === null) {
                    currNode.left = node;
                    break;
                } else {
                    currNode = currNode.left;
                }
            } else {
                // यहां वैल्यू सेट करें क्योंकि हम लीफ नोड पर पहुंच गए हैं
                if (currNode.right === null) {
                    currNode.right = node;
                    break;
                } else {
                    currNode = currNode.right;
                }
            }
        }
    }
    insertRec(data) {
        let node = new this.Node(data);
        // जांचें कि ट्री खाली है या नहीं
        if (this.root === null) {
            // पहले एलिमेंट के रूप में इंसर्ट करें
            this.root = node;
        } else {
            insertRecHelper(this.root, node);
        }
    }
    searchIter(data) {
        let currNode = this.root;
        while (currNode !== null) {
            if (currNode.data === data) {
                // एलिमेंट मिल गया!
                return true;
            } else if (data < currNode.data) {
                // बाएं जाएं क्योंकि डेटा पैरेंट से छोटा है
                currNode = currNode.left;
            } else {
                // दाएं जाएं क्योंकि डेटा पैरेंट से बड़ा है
                currNode = currNode.right;
            }
        }
        return false;
    }
    searchRec(data) {
        return searchRecHelper(data, this.root);
    }
    getMinVal() {
        if (this.root === null) {
            throw "खाली ट्री!";
        }
        let currNode = this.root;
        while (currNode.left !== null) {
            currNode = currNode.left;
        }
        return currNode.data;
    }
    getMaxVal() {
        if (this.root === null) {
            throw "खाली ट्री!";
        }
        let currNode = this.root;
        while (currNode.right !== null) {
            currNode = currNode.right;
        }
        return currNode.data;
    }
    deleteNode(key) {
        return !(deleteNodeHelper(this.root, key) === false);
    }
    inOrder() {
        inOrderHelper(this.root);
    }
    preOrder() {
        preOrderHelper(this.root);
    }
    postOrder() {
        postOrderHelper(this.root);
    }
}
BinarySearchTree.prototype.Node = class {
    constructor(data, left = null, right = null) {
        this.data = data;
        this.left = left;
        this.right = right;
    }
};
// हेल्पर मेथड्स
function preOrderHelper(root) {
    if (root !== null) {
        console.log(root.data);
        preOrderHelper(root.left);
        preOrderHelper(root.right);
    }
}
function inOrderHelper(root) {
    if (root !== null) {
        inOrderHelper(root.left);
        console.log(root.data);
        inOrderHelper(root.right);
    }
}
function postOrderHelper(root) {
    if (root !== null) {
        postOrderHelper(root.left);
        postOrderHelper(root.right);
        console.log(root.data);
    }
}
function insertRecHelper(root, node) {
    if (node.data < root.data) {
        // यहां वैल्यू सेट करें क्योंकि हम लीफ नोड पर पहुंच गए हैं
        if (root.left === null) {
            root.left = node;
        } else {
            insertRecHelper(root.left, node);
        }
    } else {
        // यहां वैल्यू सेट करें क्योंकि हम लीफ नोड पर पहुंच गए हैं
        if (root.right === null) {
            root.right = node;
        } else {
            insertRecHelper(root.right, node);
        }
    }
}
function searchRecHelper(data, root) {
    if (root === null) {
        // लीफ पर पहुंच गए लेकिन नहीं मिला।
        return false;
    }
    if (data < root.data) {
        return searchRecHelper(data, root.left);
    } else if (data > root.data) {
        return searchRecHelper(data, root.right);
    }
    // इसका मतलब एलिमेंट मिल गया
    return true;
}
/**
 * रूट और की लेता है और की के लिए रिकर्सिवली खोजता है।
 * अगर यह की ढूंढ लेता है, तो 3 केस हो सकते हैं:
 *
 * 1. यह नोड एक लीफ नोड है।
 *
 * उदाहरण: F हटाना
 * A
 * / \
 * B C
 * / / \
 * D E F
 *
 * इसे हटाने के लिए, हम बस इसके पैरेंट के कनेक्शन को इससे हटा सकते हैं।
 *
 * A
 * / \
 * B C
 * / /
 * D E
 *
 * 2. यह नोड ट्री में कहीं बीच में है जिसमें एक चाइल्ड है।
 *
 * उदाहरण: B हटाना
 * A
 * / \
 * B C
 * / / \
 * D E F
 *
 * इसे हटाने के लिए, हम बस चाइल्ड नोड को ऊपर के कनेक्शन में पैरेंट नोड से बदल सकते हैं
 * A
 * / \
 * D C
 * / \
 * E F
 *
 * 3. इस नोड के दोनों चाइल्ड हैं। यह एक मुश्किल केस है।
 *
 * उदाहरण: C हटाना
 *
 * A
 * / \
 * B C
 * / / \
 * D E F
 * / / \
 * G H I
 *
 * इस मामले में, हमें नोड के सक्सेसर या प्रीडिसेसर को ढूंढना होगा और इस नोड को उससे बदलना होगा। उदाहरण के लिए, अगर हम सक्सेसर के साथ जाते हैं, तो उसका सक्सेसर उससे थोड़ा बड़ा एलिमेंट होगा, यानी राइट सबट्री में मिन एलिमेंट। तो डिलीशन के बाद, ट्री इस तरह दिखेगा:
 *
 * A
 * / \
 * B H
 * / / \
 * D E F
 * / \
 * G I
 *
 * इस एलिमेंट को हटाने के लिए, हमें सक्सेसर के पैरेंट को ढूंढना होगा, उनका लिंक तोड़ना होगा, सक्सेसर के लेफ्ट और राइट को करंट नोड के लेफ्ट और राइट पर इंगित करना होगा। आसान तरीका यह है कि डिलीट किए जाने वाले नोड के डेटा को सक्सेसर से बदल दें और सक्सेसर को डिलीट कर दें।
 */
function deleteNodeHelper(root, key) {
    if (root === null) {
        // खाली ट्री
        return false;
    }
    if (key < root.data) {
        root.left = deleteNodeHelper(root.left, key);
        return root;
    } else if (key > root.data) {
        root.right = deleteNodeHelper(root.right, key);
        return root;
    } else {
        // कोई चाइल्ड नहीं
        // केस 1 - एक लीफ नोड
        if (root.left === null && root.right === null) {
            root = null;
            return root;
        }
        // सिंगल चाइल्ड केस
        if (root.left === null) return root.right;
        if (root.right === null) return root.left;
        // दोनों चाइल्ड, इसलिए सक्सेसर ढूंढने की जरूरत है
        let currNode = root.right;
        while (currNode.left !== null) {
            currNode = currNode.left;
        }
        root.data = currNode.data;
        // राइट सबट्री से वैल्यू डिलीट करें।
        root.right = deleteNodeHelper(root.right, currNode.data);
        return root;
    }
}