二叉搜索树

定义

对任何结点x，其左子树中的关键值最大不超过x.val，其右子树中的关键值最小不低于x.val。大部分二叉搜索树操作的时间复杂度与树的高度成正比

遍历

同二叉树的遍历

查找

递归

void search(typename tree, int val){
    if(tree == nullptr || val = tree->val){
        return tree;
    if(val < tree->val)
        return search(tree->left, val);
    else
        return search(tree->right, val);
 }