【简介】

二叉查找树是一种数据结构，它支持多种动态集合操作。

在二叉查找树上执行的基本操作的时间与树的高度成正比。对于一棵含有n个节点的完全二叉树，这些操作的最坏情况运行时间为O(n)。

【结构体】

一棵二叉查找树按二叉树结构来组织的。

// 二叉查找树节点
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

【性质】

设x为二叉查找树上的一个节点。

如果y是x的左子树中的一个节点，则y->val 小于等于 x->val。

如果y是x的右子树中的一个节点，则y->val 大于等于 x->val。

【输出】

根据二叉查找树的性质，我们可以用中序递归遍历算法按排列顺序输出树中的所有关键字。

// 中序遍历输出二叉查找树
void InOrder(TreeNode* root){
    if(root == NULL){
        return;
    }//if
    InOrder(root->left);
    cout<<root->val<<endl;
    InOrder(root->right);
}

【插入】

// 插入
void TreeInsert(TreeNode*& root,int val){
    // 创建新节点
    TreeNode* node = new TreeNode(val);
    // 空树
    if(root == NULL){
        root = node;
        return;
    }//if
    TreeNode *pre = NULL;
    TreeNode *p = root;
    // 寻找插入位置
    while(p){
        // 父节点
        pre = p;
        // 沿左子树方向下降
        if(val < p->val){
            p = p->left;
        }//if
        // 沿右子树方向下降
        else{
            p = p->right;
        }//else
    }//while
    // 左子结点处插入
    if(val < pre->val){
        pre->left = node;
    }//if
    // 右子结点处插入
    else{
        pre->right = node;
    }//else
}

指针p跟踪了这条路径，而pre始终指向p的父节点。初始化后while循环是这两个指针沿树下降，根据val和p->val的比较结果，可以决定向左还是向右转。

直到p成为NULL为止。这个NULL所占的位置就是我们像插入的位置。

其特点是：树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的节点时再进行插入。

新插入的结点一定是一个新添加的叶子节点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。

【查找】

【递归算法】

返回指向包含关键字val的节点（如果存在的）的指针，否则返回NULL

// 查找
TreeNode* TreeSearch(TreeNode* root,int val){
    if(root == NULL || root->val == val){
        return root;
    }//if
    // 左子树查找
    if(val < root->val){
        return TreeSearch(root->left,val);
    }//if
    // 右子树查找
    else{
        return TreeSearch(root->right,val);
    }//else
}

如果root不是空树：

对碰到的每一个节点p，都要进行比较val和p->val，如果两个关键字相同，则查找结束。

如果val小于p->val，则继续查找p的左子树，如果val大于等于p->val，则继续查找p的右子树。

【非递归算法】

// 非递归查找
TreeNode* TreeSearch2(TreeNode* root,int val){
    if(root == NULL || root->val == val){
        return root;
    }//if
    TreeNode *p = root;
    while(p && val != p->val){
        // 左子树查找
        if(val < p->val){
            p = p->left;
        }//if
        // 右子树查找
        else{
            p = p->right;
        }//else
    }//while
    return p;
}

【最大元素】

要查找二叉树中具有最大关键字的元素，只要从根节点开始，沿着各节点的right指针查找下去，直到遇到NULL为止。

// 最大元素
TreeNode* TreeMaxNum(TreeNode *root){
    TreeNode *p = root;
    while(p->right){
        p = p->right;
    }//while
    return p;
}

【最小元素】

要查找二叉树中具有最小关键字的元素，只要从根节点开始，沿着各节点的left指针查找下去，直到遇到NULL为止。

// 最小元素
TreeNode* TreeMinNum(TreeNode *root){
    TreeNode *p = root;
    while(p->left){
        p = p->left;
    }//while
    return p;
}

[算法]二叉查找树