关于数据结构: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数据结构与算法