xgqfrms™, xgqfrms® : xgqfrms's offical website of GitHub!

binary search tree

BST

二叉搜索树/二叉查找树

"use strict";

/**
 *
 * @author xgqfrms
 * @license MIT
 * @copyright xgqfrms
 * @created 2020-06-21
 * @modified
 *
 * @description
 * @augments
 * @example
 * @link
 *
 */

const log = console.log;

function BinarySearchTree () {
  var root = null;
  // 节点，构造函数
  function Node (key) {
    this.key = key;
    this.left = null;
    this.right = null;
  }
  // 闭包，私有方法
  function insertNode(root, node) {
    if(root.key > node.key) {
      // 左子树
      if (root.left === null) {
        root.left = node;
      } else {
        insertNode(root.left, node);
      }
    } else {
      // root.key <= node.key
      // 右子树
      if (root.right === null) {
        root.right = node;
      } else {
        insertNode(root.right, node);
      }
    }
  }
  this.insert = function(key) {
    var node = new Node(key);
    if(!root && root === null) {
      root = node;
    } else {
      insertNode(root, node);
    }
  }
}


// export default BinarySearchTree;

// export {
//   BinarySearchTree,
// };

---

js algorithm

tree

概念

节点: 根节点, 子节点, 外部节点(叶子节点), 内部节点();
层次: 根节点 0 层, (1 ~ n) 层;
深度: 叶子节点的祖先节点的数量, 即(节点层次 - 1; 或者祖先节点与叶子节点的边数);
高度: 最大的叶子节点的深度, 即(最大的节点层次 - 1; 或者根节点与叶子节点的最大边数);
边: 两个节点之间的连线

树: 一系列存在父子关系的节点, 除根节点外, 每个节点都有 1 个父节点, 和大于等于 0 个的子节点;
子树: 把一个内部节点作为根节点的树, 即（内部节点和其后代子节点)

二叉树: 每个节点上的子节点数量小于等于 2 个(左节点, 右节点)
平衡二叉树: 左右子树的节点的层次差值为 1
完全二叉树: 每个内部节点的子节点都是2个
满二叉树:

二叉搜索树: 每个父节点的左子节点值都小于父节点的值, 右子节点值都大于等于父节点的值, 即(左节点值 < 父节点的值 <= 右子节点值)

1. BST BinarySearchTree

JavaScript 算法可视化

https://visualgo.net/zh

Binary tree

BST

{{uploading-image-606213.png(uploading...)}}

---

---

©xgqfrms 2012-2020

www.cnblogs.com 发布文章使用：只允许注册用户才可以访问！

---