JS實(shí)現(xiàn)二叉排序樹

sherlock221 發(fā)布于2019-08-21 17:35 / 930人閱讀

摘要：實(shí)現(xiàn)二叉排序樹實(shí)現(xiàn)二叉排序樹初始化二叉樹只接受一個(gè)數(shù)組作為參數(shù)根節(jié)點(diǎn)接受傳入的參數(shù)數(shù)組初始化每個(gè)樹節(jié)點(diǎn)當(dāng)前節(jié)點(diǎn)的值左子樹右子樹構(gòu)建二叉樹請(qǐng)選擇一個(gè)數(shù)組參數(shù)插入節(jié)點(diǎn)當(dāng)前需要插入的節(jié)點(diǎn)根節(jié)點(diǎn)不存在值時(shí)插入節(jié)點(diǎn)到根節(jié)點(diǎn)當(dāng)前節(jié)點(diǎn)的小于父節(jié)點(diǎn)時(shí)當(dāng)

JS實(shí)現(xiàn)二叉排序樹

1. 初始化二叉樹

        function BinaryTree (arr) {
            if (Object.prototype.toString.call(arr).slice(8, -1) !== "Array") {
                throw new TypeError("只接受一個(gè)數(shù)組作為參數(shù)")
            }
            this.root = null; //根節(jié)點(diǎn)
            this.arr = arr || []; //接受傳入的參數(shù)-數(shù)組
            
            
            //初始化每個(gè)樹節(jié)點(diǎn)
            var TreeNode = function (key) {
                this.key = key; //當(dāng)前節(jié)點(diǎn)的值
                this.left = null; //左子樹
                this.right = null; //右子樹
            }
            
            //構(gòu)建二叉樹
            this.init = function () {
                if (!this.arr) {
                    console.warn("請(qǐng)選擇一個(gè)數(shù)組參數(shù)");
                }
                for (var i = 0, len = this.arr.length; i < len; i++) {
                    this.insert(this.arr[i])
                }
            }
        
            //插入節(jié)點(diǎn)
            this.insert = function (key) {
                var newNode = new TreeNode(key) //當(dāng)前需要插入的節(jié)點(diǎn)
                if (this.root === null) { //根節(jié)點(diǎn)不存在值時(shí), 插入節(jié)點(diǎn)到根節(jié)點(diǎn)
                    this.root = newNode;
                }else{
                    this.insertNode(this.root, newNode)
                }
            }
            this.insertNode = function (rootNode, newNode) {
                if (rootNode.key > newNode.key) { // 當(dāng)前節(jié)點(diǎn)的key小于父節(jié)點(diǎn)時(shí), 當(dāng)前節(jié)點(diǎn)應(yīng)該插入左子樹
                    if (rootNode.left === null) { //如果左子樹不存在節(jié)點(diǎn)時(shí), 把當(dāng)前節(jié)點(diǎn)放進(jìn)去
                        rootNode.left = newNode;
                        return;
                    }
                    this.insertNode(rootNode.left, newNode) //左子樹存在節(jié)點(diǎn), 再次遞歸與該左節(jié)點(diǎn)進(jìn)行比較
        
                }else{ // 當(dāng)前節(jié)點(diǎn)的key大于或等于父節(jié)點(diǎn)時(shí), 當(dāng)前節(jié)點(diǎn)應(yīng)該插入右子樹
                    if (rootNode.right === null) { //如果右子樹不存在節(jié)點(diǎn)時(shí), 把當(dāng)前節(jié)點(diǎn)放進(jìn)去
                        rootNode.right = newNode;
                        return;
                    }
                    this.insertNode(rootNode.right, newNode) //右子樹存在節(jié)點(diǎn), 再次遞歸與該右節(jié)點(diǎn)進(jìn)行比較
                }
            }
        }

        var arr = [8, 13,3,7,19,21,15];
        var tree = new BinaryTree(arr);
        tree.init();
        console.log(tree)

結(jié)構(gòu)圖如下

2. 二叉樹的遍歷

    /* 
        前序遍歷：根節(jié)點(diǎn)->左子樹->右子樹
        中序遍歷：左子樹->根節(jié)點(diǎn)->右子樹
        后序遍歷：左子樹->右子樹->根節(jié)點(diǎn)
    */

前序遍歷

    //前序遍歷
    this.preorderTraversal = function (callback) {
        if (this.root === null) {   //傳入根節(jié)點(diǎn)
            console.warn("請(qǐng)先初始化二叉排序樹");
            return;
        }
        var fn = function (node, callback) {
            if (node !== null) {  //當(dāng)前節(jié)點(diǎn)不等于空的時(shí)候,先遍歷自身節(jié)點(diǎn), 再遍歷左子樹節(jié)點(diǎn), 最后遍歷右子樹節(jié)點(diǎn)
               callback(node); //自身
               fn(node.left, callback); //左子樹
               fn(node.right, callback) //右子樹
            }
        }
        fn(this.root, callback)
    }

中序遍歷

    //中序遍歷
    this.orderTraversal = function (callback) { //從小到大
        callback = callback || function () {};
        if (this.root === null) {  //傳入根節(jié)點(diǎn)
            console.warn("請(qǐng)先初始化二叉排序樹");
            return;
        }
        var fn = function (node, callback) {
            if (node !== null) { //當(dāng)前節(jié)點(diǎn)不等于空的時(shí)候,先遍歷左子樹節(jié)點(diǎn), 再遍歷自身節(jié)點(diǎn), 最后遍歷右子樹節(jié)點(diǎn)
               fn(node.left, callback);  //左子樹
               callback(node); //自身
               fn(node.right, callback);  //右子樹 
            }
        }
        fn(this.root, callback)
    }

后序遍歷

    //后序遍歷
    this.postorderTraversal = function (callback) {
        if (this.root === null) {  //傳入根節(jié)點(diǎn)
            console.warn("Please initialize first");
            return;
        }
        var fn = function (node, callback) {
            if (node !== null) {  //當(dāng)前節(jié)點(diǎn)不等于空的時(shí)候,先遍歷左子樹節(jié)點(diǎn), 再遍歷右子樹節(jié)點(diǎn), 最后遍歷自身節(jié)點(diǎn)
               fn(node.left, callback); //左子樹
               fn(node.right, callback);  //右子樹
               callback(node);  //自身
            }
        }
        fn(this.root, callback)
    }

4.查找最小值

   this.min = function () {  //查找最小值就一直往左邊查找就行了,直到左邊沒有節(jié)點(diǎn)為止,那就證明已經(jīng)到最小值了
       var fn = function (node) {
           if (node == null) {  //傳入根節(jié)點(diǎn)
               console.warn("請(qǐng)先初始化二叉排序樹");
               return null;
           }
           if (node.left) { //查找當(dāng)前左子樹有沒有節(jié)點(diǎn), 有點(diǎn)話繼續(xù)遞歸查找該左節(jié)點(diǎn)存不存在左節(jié)點(diǎn)
               return fn(node.left);
           }else{ //直到當(dāng)前節(jié)點(diǎn)不在存在左節(jié)點(diǎn),證明取到最小值了
               return node;
           }
       }
       return fn(this.root)   
   }

5.查找最大值

   //查找最大值
   this.max = function () {  //跟查找最小值一樣,  查找最大值就一直往右邊查找就行了
       var fn = function (node) {
           if (node == null) {  //傳入根節(jié)點(diǎn)
               console.warn("請(qǐng)先初始化二叉排序樹");
               return null;
           }
           if (node.right) { 
               return fn(node.right);
           }else{
               return node;
           }
       }
       return fn(this.root) 
   }

6.刪除節(jié)點(diǎn)

    //刪除節(jié)點(diǎn)
    this.remove = function (key) {
        var fn = function (node, key) {
            if (node === null) {  //傳入初始節(jié)點(diǎn)
                console.warn("請(qǐng)先初始化二叉排序樹");
                return null;
            }
            if (node.key > key) { //初始節(jié)點(diǎn)的值大于我要?jiǎng)h除節(jié)點(diǎn)的值, 說明我要?jiǎng)h除的節(jié)點(diǎn)在初始節(jié)點(diǎn)的左邊
                node.left = fn(node.left, key) //遞歸一直尋找左邊的子節(jié)點(diǎn),直到找到null 為止
                return node;
            }else if (node.key < key) {//初始節(jié)點(diǎn)的值小于我要?jiǎng)h除節(jié)點(diǎn)的值, 說明我要?jiǎng)h除的節(jié)點(diǎn)在初始節(jié)點(diǎn)的右邊
                node.right = fn(node.right, key);
                return node;
            }else { //當(dāng)前節(jié)點(diǎn)的值等于我要?jiǎng)h除節(jié)點(diǎn)的值,說明找到要?jiǎng)h除的節(jié)點(diǎn)了

                //當(dāng)前節(jié)點(diǎn)的左右兩邊分支都為空時(shí),直接把當(dāng)前節(jié)點(diǎn)置為null,返回出去
                if (node.left === null && node.right === null) { 
                    node = null;
                    return node;
                }

                //當(dāng)前節(jié)點(diǎn)只有左邊為空時(shí), 直接引入右邊的分支替換成當(dāng)前分支
                if (node.left === null) { 
                    node = node.right;
                    return node;
                }

                //當(dāng)前節(jié)點(diǎn)只有右邊為空時(shí), 直接引入左邊的分支替換成當(dāng)前分支
                if (node.right == null) {  
                    node = node.left;
                    return node;
                }

                //當(dāng)左右兩邊節(jié)點(diǎn)都不為空時(shí), 就需要找一個(gè)值來替換當(dāng)前的值, 為了結(jié)構(gòu)的完整性,最好是大于左邊的值,
                //而且小于右邊的, 這個(gè)值的最佳選擇就是當(dāng)前節(jié)點(diǎn)右邊的最小值, 這樣就能比左邊的大,  比右邊的小

                //去右邊尋找最小值, 而且最小值應(yīng)該在左子樹上
                var minNode = rightMinNode(node.right);

                // 那我們就要?jiǎng)h除右邊最小值的那個(gè)分支, 然后把值賦值到當(dāng)前節(jié)點(diǎn)上

                fn(node, minNode.key) //執(zhí)行右邊最小值刪除操作

                node.key = minNode.key
                return node;
            }
        }

        var rightMinNode = function (node) {
            if (node.left === null) { //如果第一個(gè)右子樹的左子樹上為空的話, 那他就是最小值, 如果存在那就往左子樹上在進(jìn)行查詢,知道左子樹為null時(shí), 那就是最小值
                return node;
            }
            return rightMinNode(node.left)
        }
        fn(this.root, key)
    }