JavaScript -- 二叉查找树的JavaScript的描述

谁借莪１个温暖的怀抱￠ 2022-04-17 01:50 134阅读 0赞

我首先看一下什么是树。

树是计算机科学中经常用到的一种数据结构。树是一种非线性的数据结构，以分层的方式存储数据。树被用来存储具有层级关系的数据，比如文件系统中的文件；

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d1c3RfY3ls_size_16_color_FFFFFF_t_70][]

这是一颗普通的树。

二叉树是一种特殊的树，它的子节点个数不超过两个。二叉树有许多优秀的性质。

二叉排序树（Binary Sort Tree），又称**[二叉查找树][Link 1]**（Binary Search Tree），亦称[二叉搜索树][Link 2]。

二叉排序树或者是一棵空树，或者是具有下列性质的[二叉树][Link 3]：

（1）若左子树不空，则左子树上所有结点的值均小于它的[根结][Link 4]点的值；

（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

（4）没有键值相等的节点。

二叉查找树，查找数据非常快，log(n)的时间复杂度，哈哈哈。

对于前端工程师，你可以写写，学一学，在前端处理一下数据，然后可以跟后台说，不用你啦，我已经用很高效的算法处理了，哈哈。

我们可以定义个数据结构用来表示每一个节点。

let Node = function (element) {
        this.element = element;//数据域
        this.left = null;//左节点
        this.right = null;//右节点
    }

增节点操作：

根据二叉查找树的性质：假设插入数据为data,当前节点为cur

if (data < cur.val)  那么应该插到cur的左子树上面，

if (data > cur.val) 那么应该查到cur的右子树上面。

this.insert = function (data) {//插入数据
            let newNode = new Node(data);//新生成节点
            let cur = this.rootNode;
            while (true) {
                if (data > cur.element) {//挂在右子树上
                    if (cur.right != null) {//如果右节点不能挂，那么继续找
                        cur = cur.right;
                    } else {
                        cur.right = newNode;//挂上节点
                        break;
                    }
                } else {
                    if (cur.left != null) {//挂在左子树
                        cur = cur.left;//如果左节点不能挂，那么继续找
                    } else {
                        cur.left = newNode;//挂上节点
                        break;
                    }
                }
            };
        };

我们遍历树有四种方法

1：前序遍历 （首先访问根，再先序遍历左子树，最后先序遍历右子树）DLR

2：中序遍历   (首先遍历左子树，再访问根，最后中序遍历右子树)  LDR

3:   后序遍历   (首先遍历左子树，再后序遍历右子树，最后访问根)  LRD

4:   层次遍历   (按照树的层次，按层遍历，每一层从左到右输出）不介绍

this.preOrder = function (node) { //先序遍历，
            if (node == null) return ;
            console.log(node.element);//因为当前节点就是根节点，所以输出
            this.preOrder(node.left);//然后遍历左子树
            this.preOrder(node.right);//接着就是右子树
        };
        this.inOrder = function (node) {//中序遍历
            if (node == null) return ;
            this.inOrder(node.left);//先遍历左子树
            console.log(node.element);//输出根节点
            this.inOrder(node.right);//然后遍历又子树
        };
        this.postOrder = function (node) {//后序遍历
            if (node == null) return ;
            this.postOrder(node.left);//先遍历左子树
            this.postOrder(node.right);//然后遍历左子树
            console.log(node.element);//输出根节点
        };

我们来验证一下，刚刚代码吧。

let app = new BST(50);
    app.insert(10);
    app.insert(70);
    app.insert(80);
    app.insert(60);
    app.insert(15);
    app.insert(5);

我们建立了如下的二叉查找树（虚线表示先序遍历）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d1c3RfY3ls_size_16_color_FFFFFF_t_70 1][]

![20181111171033974.png][]先序遍历

![20181111171111643.png][]中序遍历

![20181111171154105.png][]后序遍历

我们看一下二叉查找树的用途，以找最大值和最小值为例

1：找最大值 根据二叉查找树的性质，最大值肯定是右子树的最右节点。

2：找最小值 根据二叉查找树的性质，最小值肯定是左子树的最左节点。

this.getMax = function () {
            let cur = this.rootNode;
            while ( cur.right != null) { //右子树的最右节点
                cur = cur.right;
            }
            return cur.element;
        };
        this.getMin = function () {
            let cur = this.rootNode;
            while ( cur.left != null ) { //左子树的最左节点
                cur = cur.left;
            }
            return cur.element;
        };

找普通值也是如此，(log(n))的时间复杂度，代码根据上面琢磨一下，就可以写出来了。

this.find = function (data) {
            let cur = this.rootNode;
            while (cur != null) {//该节点不空
                if (data == cur.element) return true;//找到了
                else {
                    if (data > cur.element )  cur = cur.right;//在右子树
                    else  cur = cur.left;//在左子树
                }
            }
            return false;
        }

现在有一个重要的任务就是删除操作，这是一个很麻烦的操作。

删除操作分四种情况讨论。（总的来说，就是要维护二叉树的特性）

1：删除节点没有子节点

2：删除节点只有左节点

3：删除节点只有右节点

4：删除节点有左右节点

删除节点没有子节点：这个很简单，找到该节点，和其父亲节点相连的那一条边置为null。

删除节点只有左节点，删除节点只有右节点：这个也不麻烦，只需要将其父节点指向它的子节点。

删除节点有左右节点：这个最麻烦，有俩种方案。1：找到删除节点左子树的最大值，然后替换删除的节点。2：找到删除节点右子树的最小值，然后替换删除的节点。

我们使用方法一

话不多说，看代码

this.remove = function (data) {//调用removeNode函数
            this.rootNode = this.removeNode (this.rootNode,data);
        };
        this.removeNode = function (node,data) {
            if ( node == null ) return null;//当前节点为null, 返回null
            if ( node.element == data ) {//找到需要删除节点了
                if ( node.left == null && node.right == null ) return null;//第一种情况，那么简单的返回null即可与父节点断开
                else if ( node.left == null ) return node.right;//和下面相同，将子树与父节点相连
                else if ( node.right == null ) return node.left;
                else {//第四种情况
                    let cur = node.left;//左子树根节点
                    let next = node.left.right;//左子树根节点的右儿子
                    if (next === null ) {//当右儿子不存在，即它（左子树根节点）为最大值， 
                        node.element = cur.element;//替换
                        node.left = cur.right;//如果左子树根节点存在右子树，与node连起来
                        return node;
                    }
                    while ( next.right != null ) {//有右儿子，那么一直寻找到最下面（最大值）
                        cur = next;//需要记录父节点，因为我们需要把替换的节点（最大值）删掉，即断开与父节点的联系
                        next = next.right;
                    }
                    cur.right = null;//父节点与替换节点（最大值节点）断开联系
                    node.element = next.element;//使用最大值替换需要删除的值
                    return node;
                }
    
            } else if ( data > node.element) {//那么肯定在右子树上
                node.right = this.removeNode (node.right,data);
                return node;
            } else {//那么肯定在左子树上
                node.left = this.removeNode (node.left,data);
                return node;
            }
        };

代码很详细了，你可以在草稿纸上面画一画，删除节点的四种情形，然后模拟一下，就明白我在说什么了。

验证代码：

let app = new BST(50);
    app.insert(10);
    app.insert(70);
    app.insert(80);
    app.insert(60);
    app.insert(15);
    app.insert(5);
     
    
    app.remove(70);
    
    app.inOrder(app.rootNode);

![20181111203336378.png][]70被删除了。

好了，给出完整代码，可以玩玩嘛

可以自己试一试哈！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d1c3RfY3ls_size_16_color_FFFFFF_t_70]: /images/20220417/588cae9abc1142e4af0581c4a7d3e20d.png
[Link 1]: https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%9F%A5%E6%89%BE%E6%A0%91/7077965
[Link 2]: https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/7077855
[Link 3]: https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%A0%91
[Link 4]: https://baike.baidu.com/item/%E6%A0%B9%E7%BB%93
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d1c3RfY3ls_size_16_color_FFFFFF_t_70 1]: /images/20220417/ddc13f6c66e6420e94ca937f3eb6ede9.png
[20181111171033974.png]: /images/20220417/2ec3bf7e195a4d53aa3a7e59692b9355.png
[20181111171111643.png]: /images/20220417/f52c6f3b73dc46cd9c635b35d19db186.png
[20181111171154105.png]: /images/20220417/8bf998358ad94874bf5d80db943afa17.png
[20181111203336378.png]: /images/20220417/de9ed7f7abd94edd99a9c76e0477597e.png