JavaScript 二叉查找树

🌙
手机阅读
本文目录结构

二叉查找树

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

实现树节点类:

  1. // 节点类,树的节点
  2. class Node {
  3. constructor(value) {
  4. this.value = value;
  5. this.left = null;
  6. this.right = null;
  7. }
  8. show() {
  9. console.log(this.value);
  10. }
  11. }

实现二叉查找树类:

  1. class BinarySearchTree {
  2. constructor() {
  3. this.root = null
  4. }
  5. }

实现树的节点插入方法

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

  1. insert(value) {
  2. let newNode = new Node(value);
  3. // 判断根节点是否为空,如果不为空则递归插入到树中
  4. if (this.root === null) {
  5. this.root = newNode;
  6. } else {
  7. this.insertNode(this.root, newNode);
  8. }
  9. }
  10. insertNode(node, newNode) {
  11. // 将插入节点的值与当前节点的进行比较,如果比当前节点小,则递归判断左子树,如果比当前节点大,则递归判断右子树。
  12. if (newNode.value < node.value) {
  13. if (node.left === null) {
  14. node.left = newNode;
  15. } else {
  16. this.insertNode(node.left, newNode);
  17. }
  18. } else {
  19. if (node.right === null) {
  20. node.right = newNode;
  21. } else {
  22. this.insertNode(node.right, newNode);
  23. }
  24. }
  25. }

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

  1. // 先序遍历通过递归实现
  2. // 先序遍历则先打印当前节点,再递归打印左子节点和右子节点。
  3. preOrderTraverse() {
  4. this.preOrderTraverseNode(this.root);
  5. }
  6. preOrderTraverseNode(node) {
  7. if (node !== null) {
  8. node.show();
  9. this.preOrderTraverseNode(node.left);
  10. this.preOrderTraverseNode(node.right);
  11. }
  12. }
  13. // 中序遍历通过递归实现
  14. // 中序遍历则先递归打印左子节点,再打印当前节点,最后再递归打印右子节点。
  15. inOrderTraverse() {
  16. this.inOrderTraverseNode(this.root);
  17. }
  18. inOrderTraverseNode(node) {
  19. if (node !== null) {
  20. this.inOrderTraverseNode(node.left);
  21. node.show();
  22. this.inOrderTraverseNode(node.right);
  23. }
  24. }
  25. // 后序遍历通过递归实现
  26. // 后序遍历则先递归打印左子节点和右子节点,最后再打印当前节点。
  27. postOrderTraverse() {
  28. this.postOrderTraverseNode(this.root);
  29. }
  30. postOrderTraverseNode(node) {
  31. if (node !== null) {
  32. this.postOrderTraverseNode(node.left);
  33. this.postOrderTraverseNode(node.right);
  34. node.show();
  35. }
  36. }

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

  1. // 先序遍历通过循环实现
  2. // 通过栈来实现循环先序遍历,首先将根节点入栈。然后进入循环,每次循环开始,当前节点出栈,打印当前节点,然后将
  3. // 右子节点入栈,再将左子节点入栈,然后进入下一循环,直到栈为空结束循环。
  4. preOrderTraverseByStack() {
  5. let stack = [];
  6. // 现将根节点入栈,开始遍历
  7. stack.push(this.root);
  8. while (stack.length > 0) {
  9. // 从栈中获取当前节点
  10. let node = stack.pop();
  11. // 执行节点操作
  12. node.show();
  13. // 判断节点是否还有左右子节点,如果存在则加入栈中,注意,由于中序遍历先序遍历是先访问根
  14. // 再访问左和右子节点,因此左右子节点的入栈顺序应该是反过来的
  15. if (node.right) {
  16. stack.push(node.right);
  17. }
  18. if (node.left) {
  19. stack.push(node.left);
  20. }
  21. }
  22. }
  23. // 中序遍历通过循环实现
  24. // 中序遍历先将所有的左子节点入栈,如果左子节点为 null 时,打印栈顶元素,然后判断该元素是否有右子树,如果有
  25. // 则将右子树作为起点重复上面的过程,一直循环直到栈为空并且节点为空时。
  26. inOrderTraverseByStack() {
  27. let stack = [],
  28. node = this.root;
  29. // 中序遍历是先左再根最后右
  30. // 所以首先应该先把最左边节点遍历到底依次 push 进栈
  31. // 当左边没有节点时,就打印栈顶元素,然后寻找右节点
  32. while (stack.length > 0 || node) {
  33. if (node) {
  34. stack.push(node);
  35. node = node.left;
  36. } else {
  37. node = stack.pop();
  38. node.show();
  39. node = node.right;
  40. }
  41. }
  42. }
  43. // 后序遍历通过循环来实现
  44. // 使用两个栈来是实现,先将根节点放入栈1中,然后进入循环,每次循环将栈顶元素加入栈2,再依次将左节点和右节点依次
  45. // 加入栈1中,然后进入下一次循环,直到栈1的长度为0。最后再循环打印栈2的值。
  46. postOrderTraverseByStack() {
  47. let stack1 = [],
  48. stack2 = [],
  49. node = null;
  50. // 后序遍历是先左再右最后根
  51. // 所以对于一个栈来说,应该先 push 根节点
  52. // 然后 push 右节点,最后 push 左节点
  53. stack1.push(this.root);
  54. while (stack1.length > 0) {
  55. node = stack1.pop();
  56. stack2.push(node);
  57. if (node.left) {
  58. stack1.push(node.left);
  59. }
  60. if (node.right) {
  61. stack1.push(node.right);
  62. }
  63. }
  64. while (stack2.length > 0) {
  65. node = stack2.pop();
  66. node.show();
  67. }
  68. }

实现寻找最大最小节点值

  1. // 寻找最小值,在最左边的叶子节点上
  2. findMinNode(root) {
  3. let node = root;
  4. while (node && node.left) {
  5. node = node.left;
  6. }
  7. return node;
  8. }
  9. // 寻找最大值,在最右边的叶子节点上
  10. findMaxNode(root) {
  11. let node = root;
  12. while (node && node.right) {
  13. node = node.right;
  14. }
  15. return node;
  16. }

实现寻找特定大小节点值

  1. // 寻找特定值
  2. find(value) {
  3. return this.findNode(this.root, value);
  4. }
  5. findNode(node, value) {
  6. if (node === null) {
  7. return node;
  8. }
  9. if (value < node.value) {
  10. return this.findNode(node.left, value);
  11. } else if (value > node.value) {
  12. return this.findNode(node.right, value);
  13. } else {
  14. return node;
  15. }
  16. }

实现移除节点值

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

  1. // 移除指定值节点
  2. remove(value) {
  3. this.removeNode(this.root, value);
  4. }
  5. removeNode(node, value) {
  6. if (node === null) {
  7. return node;
  8. }
  9. // 寻找指定节点
  10. if (value < node.value) {
  11. node.left = this.removeNode(node.left, value);
  12. return node;
  13. } else if (value > node.value) {
  14. node.right = this.removeNode(node.right, value);
  15. return node;
  16. } else { // 找到节点
  17. // 第一种情况——没有叶节点
  18. if (node.left === null && node.right === null) {
  19. node = null;
  20. return node;
  21. }
  22. // 第二种情况——一个只有一个子节点的节点,将节点替换为节点的子节点
  23. if (node.left === null) {
  24. node = node.right;
  25. return node;
  26. } else if (node.right === null) {
  27. node = node.left;
  28. }
  29. // 第三种情况——一个有两个子节点的节点,去右子树中找到最小的节点,用它的值来替换当前节点
  30. // 的值,保持树的特性,然后将替换的节点去掉
  31. let aux = this.findMinNode(node.right);
  32. node.value = aux.value;
  33. node.right = this.removeNode(node.right, aux);
  34. return node;
  35. }
  36. }

更多面试题

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

面试题
HTML CSS JavaScript
jQuery Vue.js React
算法 HTTP Babel
BootStrap Electron Gulp
Node.js 前端经验相关 前端综合
Webpack 微信小程序 -

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

AXIHE / 精选资源

浏览全部教程

面试题

学习网站

前端培训
自己甄别

前端书籍

关于朱安邦

我叫 朱安邦,阿西河的站长,在杭州。

以前是一名平面设计师,后来开始接接触前端开发,主要研究前端技术中的JS方向。

业余时间我喜欢分享和交流自己的技术,欢迎大家关注我的 Bilibili

关注我: Github / 知乎

于2021年离开前端领域,目前重心放在研究区块链上面了

我叫朱安邦,阿西河的站长

目前在杭州从事区块链周边的开发工作,机械专业,以前从事平面设计工作。

2014年底脱产在老家自学6个月的前端技术,自学期间几乎从未出过家门,最终找到了满意的前端工作。更多>

于2021年离开前端领域,目前从事区块链方面工作了