JavaScript实现二叉树算法

什么是二叉树

   在计算机科学中，二叉树（英语：Binary tree）是每个节点最多只有两个分支(不存在分支度大于2的节点)的树结构。通常分支被称作“左子树”和“右子树”。二叉树的分支具有左右次序，不能颠倒。

以上是维基百科对二叉树的简单介绍，我们可以用图片形象表示：

二叉树结构

JS来实现二叉树

下面我们通过JavaScript来模拟二叉树的数据结构

/**
 * JavaScript实现二叉树算法
 */
function BinaryTree() {
  // 二叉树根节点
  this.root = null;

  // 生成二叉树节点
  const Node = function(key) {
    this.key = key;
    this.left = null;
    this.right = null;
  }

  // 插入节点
  const insertNode = function(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.insert = function(key) {
    let newNode = new Node(key);
    if (this.root === null) {
      this.root = newNode;
    } else {
      insertNode(this.root, newNode);
    }
  }

}

// 模拟数据
const data = [8, 3, 10, 1, 6, 14, 4, 7, 13];

// 实例化二叉树的数据结构
const binaryTree = new BinaryTree();

// 遍历数据并插入
data.forEach(item => binaryTree.insert(item));

// 打印结果
console.log(binaryTree.root);

结果

binaryTree.root

也即对应图像：

二叉树结构

以上就是用JavaScript对二叉树的简单描述。