阿西河

所有教程

公众号
🌙
阿西河前端的公众号

我的收藏

    最近访问  (文章)

      教程列表

      抓包专区
      测试专区

      JavaScript 二叉查找树

      二叉查找树

      二叉查找树是一种特殊的二叉树,相对较小的值保存在左节点中,较大的值保存在右节点中,这一特性使得查找的效率很高, 对于数值型和非数值型数据,比如字母和字符串,都是如此。

      实现树节点类:

      // 节点类,树的节点
      class Node {
        constructor(value) {
          this.value = value;
          this.left = null;
          this.right = null;
        }
      
        show() {
          console.log(this.value);
        }
      }
      

      实现二叉查找树类:

      class BinarySearchTree {
      
        constructor() {
          this.root = null
        }
      
      }
      

      实现树的节点插入方法

      节点插入的基本思想是将插入节点和当前节点做比较,如果比当前节点值小,并且没有左子树,那么将节点作为左叶子节点, 否则继续和左子树进行比较。如果比当前节点值大,并且没有右子树,则将节点作为右叶子节点,否则继续和右子树进行比较。 循环这个过程直到找到合适的插入位置。

      
        insert(value) {
      
          let newNode = new Node(value);
      
          // 判断根节点是否为空,如果不为空则递归插入到树中
          if (this.root === null) {
            this.root = newNode;
          } else {
            this.insertNode(this.root, newNode);
          }
        }
      
        insertNode(node, newNode) {
      
          // 将插入节点的值与当前节点的进行比较,如果比当前节点小,则递归判断左子树,如果比当前节点大,则递归判断右子树。
          if (newNode.value < node.value) {
            if (node.left === null) {
              node.left = newNode;
            } else {
              this.insertNode(node.left, newNode);
            }
          } else {
            if (node.right === null) {
              node.right = newNode;
            } else {
              this.insertNode(node.right, newNode);
            }
          }
      
        }
      

      通过递归实现树的先序、中序、后序遍历

       // 先序遍历通过递归实现
       // 先序遍历则先打印当前节点,再递归打印左子节点和右子节点。
        preOrderTraverse() {
          this.preOrderTraverseNode(this.root);
        }
      
        preOrderTraverseNode(node) {
          if (node !== null) {
            node.show();
            this.preOrderTraverseNode(node.left);
            this.preOrderTraverseNode(node.right);
          }
        }
      
        // 中序遍历通过递归实现
        // 中序遍历则先递归打印左子节点,再打印当前节点,最后再递归打印右子节点。
        inOrderTraverse() {
          this.inOrderTraverseNode(this.root);
        }
      
        inOrderTraverseNode(node) {
          if (node !== null) {
            this.inOrderTraverseNode(node.left);
            node.show();
            this.inOrderTraverseNode(node.right);
          }
        }
      
        // 后序遍历通过递归实现
        // 后序遍历则先递归打印左子节点和右子节点,最后再打印当前节点。
        postOrderTraverse() {
          this.postOrderTraverseNode(this.root);
        }
      
        postOrderTraverseNode(node) {
          if (node !== null) {
            this.postOrderTraverseNode(node.left);
            this.postOrderTraverseNode(node.right);
            node.show();
          }
        }
      

      通过循环实现树的先序、中序、后序遍历

        // 先序遍历通过循环实现
        // 通过栈来实现循环先序遍历,首先将根节点入栈。然后进入循环,每次循环开始,当前节点出栈,打印当前节点,然后将
        // 右子节点入栈,再将左子节点入栈,然后进入下一循环,直到栈为空结束循环。
        preOrderTraverseByStack() {
          let stack = [];
      
          // 现将根节点入栈,开始遍历
          stack.push(this.root);
      
          while (stack.length > 0) {
      
            // 从栈中获取当前节点
            let node = stack.pop();
      
            // 执行节点操作
            node.show();
      
            // 判断节点是否还有左右子节点,如果存在则加入栈中,注意,由于中序遍历先序遍历是先访问根
            // 再访问左和右子节点,因此左右子节点的入栈顺序应该是反过来的
            if (node.right) {
              stack.push(node.right);
            }
      
            if (node.left) {
              stack.push(node.left);
            }
          }
        }
      
        // 中序遍历通过循环实现
        // 中序遍历先将所有的左子节点入栈,如果左子节点为 null 时,打印栈顶元素,然后判断该元素是否有右子树,如果有
        // 则将右子树作为起点重复上面的过程,一直循环直到栈为空并且节点为空时。
        inOrderTraverseByStack() {
          let stack = [],
            node = this.root;
      
          // 中序遍历是先左再根最后右
          // 所以首先应该先把最左边节点遍历到底依次 push 进栈
          // 当左边没有节点时,就打印栈顶元素,然后寻找右节点
          while (stack.length > 0 || node) {
            if (node) {
              stack.push(node);
              node = node.left;
            } else {
              node = stack.pop();
              node.show();
              node = node.right;
            }
          }
        }
      
        // 后序遍历通过循环来实现
        // 使用两个栈来是实现,先将根节点放入栈1中,然后进入循环,每次循环将栈顶元素加入栈2,再依次将左节点和右节点依次
        // 加入栈1中,然后进入下一次循环,直到栈1的长度为0。最后再循环打印栈2的值。
        postOrderTraverseByStack() {
          let stack1 = [],
            stack2 = [],
            node = null;
      
          // 后序遍历是先左再右最后根
          // 所以对于一个栈来说,应该先 push 根节点
          // 然后 push 右节点,最后 push 左节点
      
          stack1.push(this.root);
      
          while (stack1.length > 0) {
            node = stack1.pop();
      
            stack2.push(node);  
            
            if (node.left) {
              stack1.push(node.left);
            }
            
            if (node.right) {
              stack1.push(node.right);
            }
      
          }
      
          while (stack2.length > 0) {
            node = stack2.pop();
            node.show();
          }
        }
      

      实现寻找最大最小节点值

       // 寻找最小值,在最左边的叶子节点上
        findMinNode(root) {
          let node = root;
      
          while (node && node.left) {
            node = node.left;
          }
      
          return node;
        }
      
        // 寻找最大值,在最右边的叶子节点上
      
        findMaxNode(root) {
          let node = root;
      
          while (node && node.right) {
            node = node.right;
          }
      
          return node;
        }
      

      实现寻找特定大小节点值

        // 寻找特定值
        find(value) {
          return this.findNode(this.root, value);
        }
      
        findNode(node, value) {
      
          if (node === null) {
            return node;
          }
          if (value < node.value) {
            return this.findNode(node.left, value);
          } else if (value > node.value) {
            return this.findNode(node.right, value);
          } else {
            return node;
          }
        }
      

      实现移除节点值

      移除节点的基本思想是,首先找到需要移除的节点的位置,然后判断该节点是否有叶节点。如果没有叶节点,则直接删除,如 果有一个叶子节点,则用这个叶子节点替换当前的位置。如果有两个叶子节点,则去右子树中找到最小的节点来替换当前节点。

      
        // 移除指定值节点
        remove(value) {
          this.removeNode(this.root, value);
        }
        removeNode(node, value) {
      
          if (node === null) {
            return node;
          }
      
          // 寻找指定节点
          if (value < node.value) {
            node.left = this.removeNode(node.left, value);
            return node;
          } else if (value > node.value) {
            node.right = this.removeNode(node.right, value);
            return node;
          } else { // 找到节点
      
            // 第一种情况——没有叶节点
            if (node.left === null && node.right === null) {
              node = null;
              return node;
            }
      
            // 第二种情况——一个只有一个子节点的节点,将节点替换为节点的子节点
            if (node.left === null) {
              node = node.right;
              return node;
            } else if (node.right === null) {
              node = node.left;
            }
      
            // 第三种情况——一个有两个子节点的节点,去右子树中找到最小的节点,用它的值来替换当前节点
            // 的值,保持树的特性,然后将替换的节点去掉
            let aux = this.findMinNode(node.right);
            node.value = aux.value;
            node.right = this.removeNode(node.right, aux);
            return node;
          }
        }
      

      更多面试题

      如果你想了解更多的前端面试题,可以查看本站的WEB前端面试题 ,这里基本包涵了市场上的所有前端方面的面试题,也有一些大公司的面试图,可以让你面试更加顺利。

      面试题
      HTMLCSSJavaScript
      jQueryVue.jsReact
      算法HTTPBabel
      BootStrapElectronGulp
      Node.js前端经验相关前端综合
      Webpack微信小程序-

      这些题库还在更新中,如果你有不错的面试题库欢迎分享给我,我整理后放上来;人人为我,我为人人,互帮互助,共同提高,祝大家都拿到心仪的Offer!

      目录
      目录