我对JS树的简单学习

摘要：二叉搜索树这一数据结构综合了以上两种数据结构的优点。上图就展示了一个二叉搜索树。实现二叉树的算法大部分都有递归。

一种非顺序数据结构-树，它对于存储需要快速查找的数据非常有用

相关概念：

根节点：位于树顶部的节点，没有父节点

内部节点：至少有一个子节点的节点（7，5，9，15，13，20）

外部节点（叶节点）：没有子元素的节点（第3层）

子树：由节点和它的后代构成（节点13，12，14构成了一个子树）

深度：节点的深度取决于它的祖先节点的数量

高度：取决于所有节点深度的最大值

无序链表在插入时候具有较高的灵敏性，而有序数组在查找的时候具有较高的效率。

二叉搜索树（BST）这一数据结构综合了以上两种数据结构的优点。但是它只允许你在左侧节点存储（比父节点）小的值，右侧节点存储（比父节点）大的值。

上图就展示了一个二叉搜索树。实现二叉树的算法大部分都有递归。

创建一个BinarySearchTree类

function BinarySearchTree () {
  var Node = function () {
    this.key = key; // 键
    this.left = null; // 指针指向左侧子节点
    this.right = null; // 指针指向右侧子节点
  };
  var root = null;
}

var tree = new BinarySearchTree();

实现insert(key)方法，插入一个键

this.insert = function (key) {
  var newNode = new Node(kye); // 创建用来表示新节点的Node类实例，
  if (root === null) { // 如果插入的节点是树第一个节点
    root = newNode;
  } else {
    insertNode(root, newNode); // 私有的辅助函数
  }
}

tree.insert();

私有的辅助函数

var 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);
    }
  }
}

前序遍历：根节点->左子树->右子树
中序遍历：左子树->根节点->右子树
后序遍历：左子树->右子树->根节点

对下面的树进行遍历

前序遍历：abdefgc

中序遍历：debgfac

后序遍历：edgfbca

中序遍历：一种应用是对树进行排序操作

this.inOrderTraverse = function {callback} {
  inOrderTraverse(root, callback); // 回调函数用来处理遍历到的每个节点
};

var inOrderTraverseNode = function (node, callback) {
  if (node !== null) {
    inOrderTraverseNode(node.left, callback);
    callback(node.key);
    inOrderTraverseNode(node.right, callback);
  }
}

先序遍历：一种应用是打印一个结构化的文档

this.preOrderTraverse = function (callback) {
  preOrderTraverseNode(root, callback);
}

var preOrderTraverseNode = function (node, callback) {
  if (node !== null) {
    callback(node.key);
    preOrderTraverseNode(node.left, callback);
    preOrderTraverseNode(node.right, callback);
  }
}

后序遍历：一种应用是计算一个目录和它的子目录中所有文件所占的空间大小。

this.postOrderTraverse = function (callback) {
  postOrderTraverse(root, callback);
}

var postOrderTraverse = function (callback) {
  if (node !== null) {
    postOrderTraverse(node.left, callback);
    postOrderTraverse(node.right, callback);
    callback(node.key);
  }
}

对于寻找最小值，总是沿着树的左边；对于寻找最大值，总是沿着树的右边

寻找树中的最小键

this.min = function () {
  return minNode(root);
}

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

寻找一个特定的值

this.search = function (key) {
  return searchNode(root, key);
}

var searchNode = function (node, kye) {
  if (node === null) { // node有效性检查
    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.remove = function (key) {
  root = removeNode (root, key);
}

var removeNode = function (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 {
    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;
  }
}