关于数据结构:javascript数据结构之树二叉搜索树平衡二叉树红黑树

一种非程序数据结构–树。

树是一种分层数据的形象模型,一个树结构蕴含一系列存在父子关系的节点，每个节点都有一个父节点(除了顶部第一个节点)以及零个或多个子节点,位于树顶部的节点叫根节点。

二叉树和二叉搜寻树

二叉树中的节点最多只能有两个节点,一个左侧的节点，一个右侧节点。
二叉搜寻树（BST）是二叉树的一种，然而只容许在左侧贮存比父节点小的数据，在右侧贮存比父节点大的数据。

和链表一样，通过援用来示意节点之间的关系，在双向链表里，每个节点有俩援用，一个指向上一个节点，一个指向下一个节点，对于二叉搜寻树也应用同样形式，不同的中央是一个指向左侧节点，一个指向右侧节点（树中会称节点为键）。

1. insert(key) 树里插入键
2. search(key) 树里查找一个键
3. inOrderTraveres() 中序遍历所有
4. preOrderTraveres() 先序遍历所有
5. postOrderTraveres() 后序遍历所有
6. min() 获取树最小值
7. max() 获取树最大值
8. remove(key) 删除树里某个键

const Compare = {
    LESS_THAN:-1,
    BIGGER_THAN:1
}
function defultCompare(a,b){
    if(a===b){
        return 0;
    }
    return a<b?Compare.LESS_THAN:Compare.BIGGER_THAN;
}

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

class BinarySearchTree{
    constructor(compareFn = defaultCompare){
        this.compareFn = compareFn;
        this.root = null;
    }
    insert(key){
        if(!this.root){
            this.root = new Node(key);
        }else{
            this.insertNode(this.root,key);
        }
    }
    insertNode(node,key){//查找比照键大小插入,最初生成构造如上图
        if(this.compareFn(key,node.key)==Compare.LESS_THAN){
            if(!node.left){
                node.left = new Node(key);
            }else{
                this.insertNode(node.left,key);
            }
        } else {
            if(!node.right){
                node.right = new Node(key);
            }else{
                this.insertNode(node.right,key);
            }
        }
    }
    search(key){
        return this.searachNode(this.root,key);
    }
    searachNode(node,key){
        if(!node){
            return false;
        }
        if(this.compareFn(key,node.key)==Compare.LESS_THAN){
            return this.searachNode(node.left,key);
        }else if(this.compareFn(key,node.key)==Compare.BIGGER_THAN){
            return this.searachNode(node.right,key);
        }else{
            return true;//能够依据本人须要返回
        }
    }
}

做个笔记，该内容借鉴与学习javascript数据结构与算法