数据结构:JavaScript实现二叉查找树

蔚落 2022-08-20 09:23 202阅读 0赞

二叉树是一种特殊的树，它的子节点个数不超过两个。

二叉查找树是一种是一种特殊的二叉树，相对较小的值保存在左节点中，较大的保存在右节点中，这一特性使得查找效率大大提高。

首先我们需要的对象就是Node,它包含了左子节点，右子节点以及存储的数据，另外还有一个方法来读取数据

function Node(data, left, right){
      this.data = data;
      this.left = left;
      this.right = right;
      this.show = show;
    }
    function show(){
      return this.data;
    }

现在可以创建一个类，用来表示二叉查找树(BST)

function BST(){
      this.root = null;
      this.insert = insert;
      //中序遍历
      this.inOrder = inOrder;
      //先序遍历
      this.preOrder = preOrder;
      //后续遍历
      this.postOrder = postOrder;
      //查找最小值
      this.getMin = getMin;
      //查找最大值
      this.getMax = getMax;
      //查找特定值
      this.find = find;
      //删除节点
      this.remove = remove;
    }

接下来是插入节点的函数insert

遍历二叉查找树

有三种遍历BST的方式：中序，先序和后序

先序遍历：首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树，如果二叉树为空则返回。

中序遍历：中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，再访问根结点，最后遍历右子树。

后序遍历：后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点。

代码如下：

接下来是获取最大值和最小值

在二叉树中查找最小值时，只需一直向下寻找左子树直到跳出循环，查找最大值时也是如此

最后是二叉查找树的节点的删除

首先回顾一下二叉查找树的三个重要的性质

**1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值**

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

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

**考虑到如下几种情况：**

**1）要删除的节点没有子节点**

**2）要删除的节点只有左子节点**

3**）要删除的节点只有右子节点**

**4）要删除的节点既有左子节点又有右子节点**

**第一种情况，也是最为简单易懂的一种情况，直接将待删除节点值设置为null即可**

**第二、三种情况，只需将需删除节点的父节点直接指向待删除节点的子节点即可**

**第四种情况，可以这样处理，首先找到以待删除节点的右子节点为根的子树中的最小值节点，将这个节点的data赋值给带删除节点，然后把找到的最小值节点从树种删除**

**代码如下**

//找到待删除节点的父节点
    function find(data){
      var currunt = nums.root;
      var parent = null;
      if(currunt.data === data){
        return null;
      }
      while (currunt !== null) {
        if(currunt.data === data){
          return parent;
        }else if(data < currunt.data){
          parent = currunt;
          currunt = currunt.left;
        }else{
          parent = currunt;
          currunt = currunt.right;
        }
      }
      //return null;
    }
    function remove(data){
      var parent = nums.find(data);
      //判断是否是根节点
      if(parent === null){
        nums.root = null;
        return 0;
      }
      //判断是否是左子树
      var flag = true;
      if(parent.right.data === data){
        flag = false;
        currunt = parent.right;
      }else{
        currunt = parent.left;
      }
      //没有子节点
      if((currunt.left === null) && (currunt.right === null)){
        if(flag === false){
          parent.right = null;
        }else{
          parent.left = null;
        }
      }else if((currunt.left === null) && (currunt.right !== null)){
        //只有右子节点
        if(flag === false){
          parent.right = currunt.right;
        }else{
          parent.left = currunt.right;
        }
      }else if((currunt.right === null) &&(currunt.left !== null)){
        //只有左子节点
        if(flag === false){
          parent.right = currunt.left;
          }else{
          parent.left = currunt.right;
        }
      }else{
        //既有左子节点又有右子节点
        var newNode = currunt;
        currunt = currunt.right;
        while (currunt.left !== null) {
          parent = currunt;
          currunt = currunt.left;
        }
        console.log(currunt);
        newNode.data = currunt.data;
        parent.left = null;
      }
    }

以下为测试代码

var nums = new BST();
    nums.insert(10);
    nums.insert(2);
    nums.insert(58);
    nums.insert(1);
    nums.insert(34);
    nums.insert(7);
    nums.insert(4);
    console.log("中序遍历：");
    inOrder(nums.root);
    console.log("先序遍历：");
    preOrder(nums.root);
    console.log("后序遍历：");
    postOrder(nums.root);
    console.log("查找最小值：");
    console.log(nums.getMin(nums.root));
    console.log("查找最大值：");
    console.log(nums.getMax(nums.root));
    nums.remove(7);
    console.log("删除节点后：");
    preOrder(nums.root);

运行结果如下

➜  winterexcise  node bst
    中序遍历：
    1
    2
    4
    7
    10
    34
    58
    先序遍历：
    10
    2
    1
    7
    4
    58
    34
    后序遍历：
    1
    4
    7
    2
    34
    58
    10
    查找最小值：
    1
    查找最大值：
    58
    删除节点后：
    10
    2
    1
    4
    58
    34
    ➜  winterexcise