# 树

链表可以认为是特殊化的树

# 常见术语

根节点：位于树顶部的节点叫作根节点。
叶节点：没有子元素的节点称为叶子节点或外部节点
子树：子树由节点和它的后代构成
深度：节点的深度取决于它的祖先节点的数量
树的高度：取决于所有节点深度的最大值。一

# 二叉树

二叉树中的节点最多只能有两个子节点：

一个是左侧子节点，
一个是右侧子节点

这个定义有助于我们写出更高效地在树中插入、查找和删除节点的算法。二叉树在计算机科学中的应用

二叉搜索树（BST）

二叉搜索树（BST）是二叉树的一种，但是只允许你在左侧节点存储（比父节点）小的值，在右侧节点存储（比父节点）大的值。

仔细思考，这样的一棵树，再做查询时效率会大大的提高

# 三、创建二叉树搜索树类

我们要实现一些基本的方法：

insert(key)：向树中插入一个新的键。
search(key)：在树中查找一个键。如果节点存在，则返回 true；如果不存在，则返回false。
inOrderTraverse()：通过中序遍历方式遍历所有节点。
preOrderTraverse()：通过先序遍历方式遍历所有节点。
postOrderTraverse()：通过后序遍历方式遍历所有节点。
min()：返回树中最小的值/键。
max()：返回树中最大的值/键。
remove(key)：从树中移除某个键。

# 3.1 二叉搜索树类

在实现具体的方法前，我们要有基础，即一个Tree和Node，之后实现上面的方法～

class BinarySearchTree {
    constructor() {
        this.root = null; // Node 类型的根节点
        this.insert = insert; // 插入节点
        this.search = search; // 搜索节点
        this.inOrderTraverse = inOrderTraverse; // 中序遍历
        this.preOrderTraverse = preOrderTraverse; // 前序遍历
        this.postOrderTraverse = postOrderTraverse; // 后序遍历
        this.min = min; // 最小值
        this.max = max; // 最大值
        this.remove = remove; // 移除指定节点 
    }
}

class Node {
    constructor(key) {
        this.key = key; // 节点值
        this.left = null; // 左侧子节点引用
        this.right = null; // 右侧子节点引用
    }
}

# 3.2 insert - 插入一个节点

利用左子节点小于父节点，右子节点大于父节点的特性，通过递归完成节点的插入

function insert(key) {
    // 要插入的节点
    const node = new Node(key); 
    if (!this.root) {
        this.root = node; // 根节点为空
    } else {
        insertNode(this.root, node); // 推荐子节点
    }
}

function insertNode(root, node) {
    if (root.key > node.key) {
        if (!root.left) {
            root.left = node; // 小的放左边
        } else {
            insertNode(root.left, node); // 继续传递
        }
    } else {
        if (!root.right) {
            root.right = node; // 大的放右边
        } else {
            insertNode(root.right, node); // 继续传递
        }
    }
}

# 3.3 search - 搜索一个节点

搜索当前节点，当前节点为空证明未找到
当前节点不满足要求，则像下一层寻找

function search(key) {
    if (!this.root) {

        return false; // 空树
    }

    return this.searchNode(node, key)
}

function searchNode(node, key) {
    if (!node) {
        return false; // 空节点
    }
    if (node.key > key) {
        return searchNode(node.left, key);
    } else if (node.key < key) {
        return searchNode(node.right, key);
    } else {
        return true;
    }
}

# 3.4 inOrderTraverse - 中序遍历

中序遍历是一种以上行顺序访问BST所有节点的遍历方式，也就是以从最小到最大的顺序
首先遍历左子树，然后访问根结点，最后遍历右子树。
callback用于遍历时的操作

function inOrderTraverse(callback) {
    inOrderTraverseNode(this.root, callback)
}

function inOrderTraverseNode(node, callback) {
    if (node) {
        // 还有左节点
        inOrderTraverseNode(node.left, callback);
        callback(node.key);
        inOrderTraverseNode(node.right, callback);
    }
}

# 3.5 preOrderTraverse - 前序遍历

前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。

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

function preOrderTraverseNode(node, callback) {
    if (node) {
        callback(node.key);
        preOrderTraverseNode(node.left, callback);
        preOrderTraverseNode(node.right, callback);
    }
}

# 3.6 postOrderTraverse - 后序遍历

在二叉树中，先左后右再根，即首先遍历左子树，然后遍历右子树，最后访问根结点。

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

function postOrderTraverseNode(node, callback) {
    if (node) {
        preOrderTraverseNode(node.left, callback);
        preOrderTraverseNode(node.right, callback);
        callback(node.key);
    }
}

# 3.7 min

根据特性，搜索二叉树的最小值一定在树的最左侧

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

function minNode(node) {
    let cur = node;
    while (cur && cur.left) {
        cur = cur.left;
    }
    return cur;
}

# 3.8 max

根据特性，搜索二叉树的最大值一定在树的最右侧

function max() {
    return maxNode(this.root);
}

function maxNode(node){
    let cur = node;
    while (cur && cur.right) {
        cur = cur.right;
    }
    return cur;
}

# 3.9 remove

function remove(key) {
    this.root = removeNode(this.root, key, this)
}

function removeNode(node, key, bst) {
    if (node == null) { // {2} 
        return null;
    }
    if(node.key > key){
        node.left = removeNode(node.left, key); // 删除的值在左侧
    }else if(node.key < key){
        node.right = removeNode(node.right, key); // 删除的值在左侧
    }else{
        // 无子节点
        if(!node.left && !node.right){
            node = null;
            return node;
        }
        if(!node.left){
            // 只有右子节点，上移
            node = node.right;
            return node;
        }else if(!node.right){
            // 只有左子节点，上移
            node = node.left;
            return node;
        }
        // 存在左右子节点
        // 左节点，要接在右节点的最左侧
        const min = minNode(node.right); // 找到最小的值
        node.key = min.key;
        node.right = removeNode(node.right, min.key);
        return node;
    }
}

# 3.10 层序遍历

从根节点向下逐层遍历，同一层按照从左到右顺序访问。

function levelOrder(node){
  if(node == null) return;
  let queue = [];
  queue.push(node);
  while(queue.length>0){
    let cur = queue.shift();
    visit(cur);
    if(cur.left!=null){
        queue.push(cur.left)
    }
    if(cur.right != null){
        queue.push(cur.right)
    }
  } 
}

# 四、自平衡二叉树（进阶）

todo

队列集合