【小基础】数据结构与算法——JS二叉搜索树

1,823 阅读8分钟

前言

大学的东西都忘的差不多了吧?下面我们一起用js简单复习一下大学里《数据结构与算法》中的树。 本文仅使用js实现二叉树,实际工作中可能并用不到(瞎说什么大实话),但是面试挺喜欢问的,毕竟这是计算机相关专业的基础嘛。同时,代码里用了很多递归,这对后期对代码量优化还是很有帮助的。 虚拟dom,使用的就是树结构。 如果你对二叉树很熟悉,那么此文对你可能毫无价值。

参考资料:学习JavaScript数据结构与算法

树数据结构简介

生活中常见树结构有企业的组织架构图、家谱图等。 一个树结构包含一系列存在父子关系的节点。每个节点都有一个父节点(除了顶部的第一个节点,称为根结点)以及零个或多个子节点:

二叉树和二叉搜索树

二叉树中的节点最多只能有两个子节点:一个是左侧子节点,另一个是右侧子节点。

二叉搜索树(BST)是二叉树的一种,但是它只允许你在左侧节点存储(比父节点)小的值, 在右侧节点存储(比父节点)大(或者等于)的值。

二叉搜索树将是本文所复习的主要内容。

二叉搜索树的实现

实现二叉搜索树

二话不说,直接上代码,实现一个二叉搜索树的类,复制代码,放到浏览器即可。可以直接看代码,后面再细谈。

function BinarySearchTree() {
  // 初始化根结点root为null
  let root = null;

  // 用于初始化节点,key为值,left right分别为左右子节点
  function Node(key) {
    this.key = key;
    this.left = null;
    this.right = null;
  };

  // 获取树并打出
  this.getRoot = function () {
    return root
  }

  // 向树中插入新数据
  this.insert = function (key) {
    let newNode = new Node(key);
    if (root === null) {
      root = newNode;
    } else {
      insertNode(root, newNode);
    }
  };

  // 插值处理递归函数
  function insertNode(node, newNode) {
    if (newNode.key < node.key) {
      if (node.left === null) {
        node.left = newNode;
      } else {
        insertNode(node.left, newNode);
      }
    } else {
      if (node.right === null) {
        node.right = newNode;
      } else {
        insertNode(node.right, newNode);
      }
    }
  };

  // 中序遍历
  this.inorderTraversal = function (callback) {
    inorderTraversalNode(root, callback);
  };

  // 中序遍历处理递归函数
  function inorderTraversalNode(node, callback) {
    if (node !== null) {
      inorderTraversalNode(node.left, callback);
      callback(node.key);
      inorderTraversalNode(node.right, callback);
    }
  };

  // 先序遍历
  this.preorderTraversal = function (callback) {
    preorderTraversalNode(root, callback);
  };

  // 先序遍历递归函数
  function preorderTraversalNode(node, callback) {
    if (node !== null) {
      callback(node.key);
      preorderTraversalNode(node.left, callback);
      preorderTraversalNode(node.right, callback);
    }
  };

  // 后序遍历
  this.postorderTraversal = function (callback) {
    postorderTraversalNode(root, callback);
  };

  // 后序遍历递归函数
  function postorderTraversalNode(node, callback) {
    if (node !== null) {
      postorderTraversalNode(node.left, callback);
      postorderTraversalNode(node.right, callback);
      callback(node.key);
    }
  };

  // 查询节点,若存在则返回true 反之 false
  this.search = function (key) {
    return searchNode(root, key);
  };

  // 查询节点递归函数
  function searchNode(node, key) {
    if (node === null) {
      return false;
    }
    if (key < node.key) {
      return searchNode(node.left, key);
    } else if (key > node.key) {
      return searchNode(node.right, key);
    } else {
      return true;
    }
  };

  // 查询最小值
  this.min = function () {
    return minNode(root);
  };

  function minNode(node) {
    if (node) {
      while (node && node.left !== null) {
        node = node.left;
        return node.key;
      }
      return null;
    };
  }

  // 查询最大值
  this.max = function () {
    return maxNode(root);
  };

  function maxNode(node) {
    if (node) {
      while (node && node.right !== null) {
        node = node.right;
      }
      return node.key;
    }
    return null;
  };

  // 移除一个节点
  this.remove = function (key) {
    root = removeNode(root, key);
  }
  function removeNode(node, key) {
    if (node === null) {
      return null;
    }
    if (key < node.key) {
      node.left = removeNode(node.left, key);
      return node;
    } else if (key > node.key) {
      node.right = removeNode(node.right, key);
      return node;
    } else { //键等于node.key
      //第一种情况——一个叶节点
      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;
        return node;
      }
      //第三种情况——一个有两个子节点的节点
      var aux = findMinNode(node.right);
      node.key = aux.key;
      node.right = removeNode(node.right, aux.key);
      return node;
    }
  };

  function findMinNode(node) {
    while (node && node.left !== null) {
      node = node.left;
    }
    return node;
  };
}

// 上面代码已经实现二叉搜索树,下面开始用起来!

// 先new一个树
let tree = new BinarySearchTree();
console.log('原始树为', tree.getRoot())
// 依次向树中插入数据
tree.insert(10);
tree.insert(2);
tree.insert(5);
tree.insert(3);
tree.insert(9);
tree.insert(8);
tree.insert(13);
tree.insert(12);
tree.insert(14);

// 获取当前树
console.log('插值后的树为:', tree.getRoot())

// 用于遍历的回调函数
function printNode(value) {
  console.log(value);
}
// 先序遍历
console.log('下方为先序遍历结果')
tree.preorderTraversal(printNode);
// 中序遍历
console.log('下方为中序遍历结果')
tree.inorderTraversal(printNode);
// 后序遍历
console.log('下方为后序遍历结果')
tree.postorderTraversal(printNode);
// 查询
console.log('查询10的结果', tree.search(10))
// 最大值最小值
console.log('最大值为:', tree.max())
console.log('最小值为:', tree.min())
// 移除节点
console.log('移除节点 10 之前', tree.getRoot())
tree.remove(10)
console.log('移除节点 10 之后', tree.getRoot())

声明一个Node类表示节点

二叉树需要记录当前节点的值,以及其2个子节点,此处以left right 分别代表左子节点和右子节点。 当创建新当节点时,new 一个Node类即可。

function Node(key) {
  this.key = key;
  this.left = null;
  this.right = null;
};

实现插值函数

插入一个新的值,就是插入一个新节点。这个时候就需要new一个Node类了。如果根结点不存在,即root为null,则表示当前值为第一个节点。否则,则需要一个插值函数用来循环插值。 在二叉树中,基本都是递归,所以这块需要详细思考一下代码的具体运行方式。 代码解释见注释:

// 向树中插入新数据
this.insert = function (key) {
  let newNode = new Node(key);
  if (root === null) {
    root = newNode;
  } else { // 如果根结点不为空,则就需要调用插值函数来计算往哪插值了
    insertNode(root, newNode);
  }
};

// 插值处理递归函数
function insertNode(node, newNode) {
  // 如果要插入的值小于当前所在节点的值
  if (newNode.key < node.key) {
    // 如果新值小于当前节点的值且左侧子节点为空,则当前节点的左子节点就为新插入的值  (1)
    if (node.left === null) {
      node.left = newNode;
    } else {
      // 如果当前节点左侧子节点不为空,则把当前节点的左子节点传入insertNode中,开始递归,直到满足上面的 (1)才能顺利插入值    
      insertNode(node.left, newNode);
    }
  } else {  // 如果要插入的值大于当前所在节点的值,则说明要插的值需要在右侧子节点,递归逻辑同上
    if (node.right === null) {
      node.right = newNode;
    } else {
      insertNode(node.right, newNode);
    }
  }
};

实现先序、中序、后续遍历

这3种遍历没有本质区别,只不过是回调函数的位置不同而已。对比代码一看即懂。

// 中序遍历
this.inorderTraversal = function (callback) {
  // 传root,完整的树,作为初始值
  inorderTraversalNode(root, callback);
};

// 下面才是遍历的真正方法
function inorderTraversalNode(node, callback) {
  // 最开始root为完整的树,当node不为空,就一直递归。为空时,则说明遍历完毕
  if (node !== null) {
    // node不为空时,继续调用,查看左子节点是否为空。如果左子节点不为空,则还会再次进入方法,直到左子节点为null
    inorderTraversalNode(node.left, callback);
    // 这个回调函数的调用有点类似koa的洋葱圈模型。当inorderTraversalNode递归到左子节点为空时,才不会继续调用。
    // 所以最先最先执行 callback(node.key) 中的节点值是最小的,然后依次越来越大。
    callback(node.key);
    inorderTraversalNode(node.right, callback);
  }
};

节点查询

节点查询就比较简单了,就是循环所有节点,看看是否有相同的值,如果有就返回true,否则false

// 查询节点
this.search = function (key) {
  return searchNode(root, key);
};

// 查询节点递归函数
function searchNode(node, key) {
  // 此处每次递归时,都会走到。如果所有节点都走完了,也没走到(1) ,那就放弃吧,确实没有
  if (node === null) {
    return false;
  }
  if (key < node.key) {
    return searchNode(node.left, key);
  } else if (key > node.key) {
    return searchNode(node.right, key);
  } else {
    return true;  // 相等(1)
  }
};

查询最大、最小值

这个也比较简单,在二叉树中,最小值肯定在左侧,最大值肯定在右侧。所以查询最小值,只要循环树左侧的节点,直到节点没了。下图的箭头分别代表寻找最大最小值的访问路径。 这里有个特殊情况需要处理,那就是树本身就为null,直接返回null。最大值同理。

// 查询最小值
this.min = function () {
  return minNode(root);
};

function minNode(node) {
  if (node) {
    // 如果节点存在且左子节点不为空,则一直循环,把node设为node.left
    while (node && node.left !== null) {
      node = node.left;
      return node.key;
    }
    return null;
  };
}

// 查询最大值
this.max = function () {
  return maxNode(root);
};

function maxNode(node) {
  if (node) {
    while (node && node.right !== null) {
      node = node.right;
    }
    return node.key;
  }
  return null;
};

删除节点

删除节点稍微比较复杂。见注释。 移除含有2个子节点的节点比较复杂,如果所示,需要在他的子树中(注意,是第一层子树),右子树寻找最小的节点,用这个最小的节点替换需要删除的节点。

// 移除一个节点
this.remove = function (key) {
  // 删除key后,新的树为removeNode的返回值
  root = removeNode(root, key);
}
function removeNode(node, key) {
  if (node === null) {
    return null;
  }
  if (key < node.key) {
    // 如果要删除的值小于当前节点的值,则说明还没找到那个要删除的节点。
    // 递归removeNode时,只有找到了那个节点,即执行了 (1),才会有返回值。并把当前节点的左子节点设为返回值。然后返回node。
    // 注意,给node.left赋值时,是递归赋值,node在不同的循环指向不同的节点
    node.left = removeNode(node.left, key);
    return node;
  } else if (key > node.key) {
    node.right = removeNode(node.right, key);
    return node;
  } else { //键等于node.key (1)
  /*
   * 如果逻辑走到了这边的代码,则说明已经找到了需要删除的节点。
   *  但是,该节点有3种情况。
   * 1. 该节点没有子节点:则说明该节点为直接设为null即可,也就是说,他的父节点的left设为null, node.left = null;
   * 2. 该节点有一个左或者右子节点:若左子节点为null,右子节点直接上移,替换该节点即可node = node.right;,其他类似
   * 3. 该节点有2个子节点。这个时候,需要在他的子树中(注意,是第一层子树),右子树寻找最小的节点,用这个最小的节点替换需要删除的节点。
   */
    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;
      return node;
    }
    //第三种情况——一个有两个子节点的节点
    var aux = findMinNode(node.right);
    node.key = aux.key;
    node.right = removeNode(node.right, aux.key);
    return node;
  }
};
// 这个方法用来寻找子树中的最小节点
function findMinNode(node) {
  while (node && node.left !== null) {
    node = node.left;
  }
  return node;
};

平衡树 红黑树 堆积树

此类后续再详细讲。