原生JS实现了二进制搜索树（Binary Search Tree）

分三步将新节点（或项目）插入树中.

第一步是创建一个Node类实例来代表新节点. 只需将要用于插入树的节点的值传递给构造函数，构造函数会自动将其左右指针值设置为null. 第二步是验证此插入操作是否是特殊情况. 这种特殊情况是我们要插入的节点是树的第一个节点. 如果是这样，则将根节点指向新节点. 第三步是将节点添加到非根节点的其他位置.

代码如下:

insert(value) {
      var newNode = new Node(value);//实例化一个新节点
      var root = this.root;
      if (root == null) {           //如果根节点不存在
        this.root = newNode;        //将这个新节点作为根节点
      } else {                      //如果根节点存在
        insertNode(root, newNode);  //将这个新节点在根节点之后找到合适位置插入
      }
    }

如果将节点添加到非根节点的其他位置，则为方便起见，我们在此处创建一个辅助函数: insertNode（node，newNode）;

/*
*函数名称：insertNode
*函数说明：将新节点newNode插入到node节点之后的合适位置
*函数参数：newNode,要插入的新节点
*        node,node节点
*/
function insertNode(node, newNode) {
//如果newNode节点值小于node节点值，进入node节点左分支
    if (newNode.value < node.value) {
      //如果node节点左孩子为空
      if (node.left == null) {
      //将newNode赋给node节点左孩子，插入完毕。
        node.left = newNode;
      } else {
      //如果node节点左孩子不为空，则继续向左孩子的左孩子递归
        insertNode(node.left, newNode);
      }
    } else {
      if (node.right == null) {
        node.right = newNode;
      } else {
        insertNode(node.right, newNode);
      }
    }
  }

使用插入节点的方法，我们可以创建一个二叉搜索树.

let bst = new BST();
bst.insert(11);
bst.insert(7);
bst.insert(15);
bst.insert(5);
bst.insert(3);
bst.insert(9);
bst.insert(8);
bst.insert(10);
bst.insert(13);
bst.insert(12);
bst.insert(14);
bst.insert(20);
bst.insert(18);
bst.insert(25);
bst.insert(6);
console.log(bst)

在控制台上打印实现二叉排序树，我们可以像这样绘制树:

遍历树是指访问树的每个节点并对它们执行某些操作的过程. 有三种方法可以访问树的所有节点: 中阶，一阶和后阶.

中间顺序遍历是一种遍历多行依次访问BST所有节点的遍历方法，即按从最小到最大的顺序访问所有节点. 中阶遍历的一种应用是对树进行排序. 中阶遍历的执行顺序是先访问该节点的左子节点，然后访问该节点本身，最后是右子节点. 遍历路径如下:

我们编写了一个midOrderTraverse方法来实现一个中阶遍历树. 此方法以回调函数为参数. 回调函数用于定义我们在遍历的每个节点上执行的操作.

// 中序遍历
midOrderTraverse(callback) {
    midOrderTraverseNode(this.root, callback);
}

同时，为了方便递归，编写辅助函数midOrderTraverseNode:

// 中序遍历辅助函数
function midOrderTraverseNode(node, callback) {
    if (node !== null) {
        midOrderTraverseNode(node.left, callback);
        callback(node);
        midOrderTraverseNode(node.right, callback);
    }
}

接下来，我们可以测试所编写代码的功能: 以中间顺序遍历上面构造的二进制搜索树，并打印出每个节点的值.

//打印节点值得函数
function printNode(node) {
    console.log(node.value);
}
bst.midOrderTraverse(printNode)  //中序遍历
//输出结果：
//3 5 6 7 8 9 10 11 12 13 14 15 18 20 25

顺序遍历以优先于后代节点的顺序访问每个节点. 预定遍历的一种应用是打印结构化文档. 一阶遍历将首先访问该节点本身实现二叉排序树，然后访问其左子节点，最后是右子节点，其遍历路径如下图所示:

像中阶遍历一样，一阶遍历仍需要一个辅助函数:

// 先序遍历
preOrderTraverse(callback){
    preOrderTraverseNode(this.root,callback)
}
// 先序遍历辅助函数
function preOrderTraverseNode(node,callback){
    if (node !== null) {
        callback(node);
        preOrderTraverseNode(node.left, callback);
        preOrderTraverseNode(node.right, callback);
    }
}

测试:

//打印节点值得函数
function printNode(node) {
    console.log(node.value);
}
bst.preOrderTraverse(printNode)  //先序遍历
//输出结果：
//11 7 5 3 6 9 8 10 15 13 12 14 20 18 25

后序遍历是先访问节点的后代节点，然后再访问节点本身. 后遍历的一种应用是计算目录及其子目录中所有文件所占用的空间大小. 顺序遍历将首先访问左子节点，然后访问右子节点，最后是父节点本身. 遍历路径如下所示:

后遍历仍然需要一个辅助功能:

// 后序遍历
lastOrderTraverse(callback){
    lastOrderTraverseNode(this.root,callback)
}
// 后序遍历辅助函数
function lastOrderTraverseNode(node,callback){
    if (node !== null) {
        lastOrderTraverseNode(node.left, callback);
        lastOrderTraverseNode(node.right, callback);
        callback(node);
    }
}

测试:

//打印节点值得函数
function printNode(node) {
    console.log(node.value);
}
bst.lastOrderTraverse(printNode)  //先序遍历
//输出结果：
//3 6 5 8 10 9 7 12 14 13 18 25 20 15 11

通过以上内容，您将发现中序遍历，一阶遍历和后序遍历的实现非常相似，唯一的区别是访问节点本身，访问左子节点以及访问的顺序. 正确的子节点.

我们可以这样记住:

参考节点本身，

我们知道在二叉搜索树中，左子节点的值始终小于右子节点的值，因此树的最小值必须是树最后一层的最左节点，以及树的最大值. 它必须是树最后一层中最右边的节点.

所以，搜索树中的最小值和最大值是搜索树最后一层中最左边和最右边的节点，代码如下:

// 查找树中节点值最小的节点
minNodeInTree(node){
    if (node) {
        while (node && node.left) {
            node = node.left;
        }
        return node.value;
    } else {
        return null;
    }
}
// 查找树中节点值最大的节点
maxNodeInTree(node){
    if (node) {
        while (node && node.right) {
            node = node.right;
        }
        return node.value;
    } else {
        return null;
    }
}

给出一个值，在树中找到与此值对应的节点. 如果该节点存在，则返回该节点；如果该节点不存在，则返回null.

这是比较方法. 将给定值与根节点值的大小进行比较，如果小于根节点值，则继续比较根节点左子节点的值；如果该值大于根节点，则继续比较该根节点的右子节点的值；递归比较. . . 已对其进行比较，直到它既不小于节点值也不大于节点值，这意味着给定的值是节点值，并最终返回节点. 代码如下:

// 查找树中特定的节点值
searchNodeInTree(value) {
    return searchNode(this.root, value);
}
// 查找特定节点辅助函数
function searchNode(node, value) {
    if (node == null) {
        return null;
    }
    if (value < node.value) {
        return searchNode(node.left, value);
    } else if (value > node.value) {
        return searchNode(node.right, value);
    } else {
        return node;
    }
}

请戳出完整的代码☞☞☞

（结束）

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-267449-1.html