js实现二叉查找树的建立、插入、删除、遍历操作

青旅半醒 2023-05-29 11:48 107阅读 0赞

# 概念 #

二叉排序树（二叉查找树），它或者是一颗空树，或者是具有以下性质的二叉树：

*  任意一个结点左子树上的所有结点值均小于该结点值
 *  任意一个结点右子树上的所有结点值均大于该结点值

例如下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70]

# 插入和建立二叉排序树 #

结点的数据结构

function newNode(value){
        
        this.value = value;
        this.left = null;
        this.right = null;
    }

## 插入操作 ##

插入操作很简单，即用递归依次比较插入值与结点值的大小，找到插入的位置

## 建立操作 ##

二叉排序树的建立就是多次执行插入操作

function create(array){
        
        var tree = new newNode(null);  //建立根节点
        for (let i=0; i < array.length; i++){
        
            InsertNode(tree, array[i]);
        }
        return tree;
    }

# 遍历 #

二叉排序树中序遍历的输出结果就是结点值从小到大排序的结果

function InOrderTraverse(root){
        
        if (!root) return;
        InOrderTraverse(root.left);
        console.log(root.value);
        InOrderTraverse(root.right);
    }

# 查找 #

二叉树的查找课简单地细分成：

*  查找二叉树的最大最小值；
 *  给定值在二叉树中进行查找。

## 查找最大最小值 ##

## 查找给定值 ##

*  节点值和给定值相当 => 返回该节点；
 *  给定值 < 节点值 => 查找当前节点的左节点，用左节点的值和给定值比较；
 *  给定值 > 节点值 => 查找当前节点的右节点，用右节点的值和给定值比较；

# 删除操作 #

删除操作稍微复杂一些。思路在于首先找到删除值的结点，若该结点是叶子结点，则直接将其置为null，若其具有左子树或右子树，则将左孩子结点或右孩子结点赋值给当前结点。若当前结点既有左子树，又有右子树，则在其左子树中，寻找一个和当前结点值最接近的孩子结点（即中序遍历结果中当前结点的前驱），将当前结点的值替换为该孩子结点的值，替换后，树中此时就有两个重复的值，因此，再利用递归删除重复的孩子结点，依次类推。。。

*  从待删除节点的左子树找节点值最大的节点A，替换待删除节点，并删除节点A；
 *  从待删除节点的右子树找节点值最小的节点A，替换待删除节点，并删除节点A。

为什么要找右子树最小值（或者左子树的最大值）呢？因为右子树最小值比左子树的所有值都大，却比右子树的所有值小，这正是根节点的特性，用它来替代根节点再适合不过了。

参考：[js实现二叉查找树的建立、插入、删除、遍历操作][js]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191105233657712.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5,size_16,color_FFFFFF,t_70
[js]: https://blog.csdn.net/zjw_python/article/details/82320128