乐趣区

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

jiezi

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

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

二叉树和二叉搜寻树

二叉树中的节点最多只能有两个节点, 一个左侧的节点，一个右侧节点。
二叉搜寻树（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 数据结构与算法

退出移动版