4张GIF图帮助你理解二叉查找树算法_查找算法gif

二叉查找树（Binary Search Tree），也称二叉搜索树，是指一棵空树或者具有下列性质的二叉树：

• 任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
• 任意节点的左、右子树也分别为二叉查找树；
• 没有键值相等的节点。

二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为O(log n)。二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如集合、multiset、关联数组等。（摘自维基百科）

下面 4 张 GIF 动图，是 penjee 官博制作分享。，分享给大家。

图1：查找 BST 中的某个元素

在二叉搜索树b中查找x的过程为：

1. 若b是空树，则搜索失败，否则：
2. 若x等于b的根节点的数据域之值，则查找成功；否则：
3. 若x小于b的根节点的数据域之值，则搜索左子树；否则：
4. 查找右子树。

图2 ↓ ：从有序数组构造一个二叉查找树

图3 ↓：往 BST 中插入元素

向一个二叉搜索树b中插入一个节点s的算法，过程为：

1. 若b是空树，则将s所指结点作为根节点插入，否则：
2. 若s->data等于b的根节点的数据域之值，则返回，否则：
3. 若s->data小于b的根节点的数据域之值，则把s所指节点插入到左子树中，否则：
4. 把s所指节点插入到右子树中。（新插入节点总是叶子节点）

图4 ↓：BST 转成有序数组

#include <iostream>  
using namespace std;  
 
//二叉树二叉链表结点结构定义  
typedef struct BiTNode   
{  
    int data;  
    struct BiTNode *lchild ,*rchild;  
}BiTNode,*BiTree;  
 
/************************************************************************/  
/* 递归查找二叉排序树T中是否存在key                                     */  
/* 指针f指向T的双亲，其初始调用值为NULL                                 */  
/* 若查找成功，则指针p指向该数据元素结点，并返回TRUE                    */  
/* 否则指针p指向查找路径上访问的最后一个结点并返回FALSE                 */             
/************************************************************************/  
bool searchBST(BiTree &T,int key,BiTree f,BiTree &p)  
{  
    if (!T)  //查找不成功 指针p指向查找路径上访问的最后一个结点并返回FALSE
    {  
        p = f;  
        return false;  
    }  
    else if (key == T->data)//查找成功   
    {  
        p = T;//若查找成功，则指针p指向该数据元素结点  
        return true;  
    }  
    else if (key < T->data)  
    {  
        return searchBST(T->lchild,key,T,p);  
    }  
    else  
    {  
        return searchBST(T->rchild,key,T,p);  
    }  
}  
 
/************************************************************************/  
/* 当二叉排序树T中不存在关键字等于key的数据元素时，                     */  
/*  插入key并返回TRUE，否则返回FALSE                                    */  
/************************************************************************/  
bool insertBST(BiTree &T,int key)  
{  
    BiTree p=NULL,s;  
    if (!searchBST(T,key,NULL,p))//查找不成功  
    {  
        s = (BiTree)malloc(sizeof(BiTNode));  
        s->data = key;  
        s->lchild = s->rchild = NULL;  
        if (!p)  //插入的一个元素
        {  
            T = s;  
        }  
        else if (key<p->data)  
        {  
            p->lchild = s;  
        }  
        else  
        {  
            p->rchild = s;  
        }  
        return true;  
    }  
    else  
    {  
        return false;//数中已有关键字相同的结点 不再插入  
    }  
}  
//创建二叉排序树BST  
bool createBST(BiTree &T,int*a, int n)  
{  
    T = NULL;  
    bool s=NULL ;  
    for (int i = 0;i<n;i++)  
    {  
        s = insertBST(T,a[i]);  
        if (!s)
        {
            cout<<"insert err"<<endl;
            break;
        }
    }  
    return s;  
}  
 
// 中序遍历      
void inOrderBST(BiTree T)      
{      
    if(T)      
    {      
        inOrderBST(T->lchild);      
        cout << T->data << " ";      
        inOrderBST(T->rchild);      
    }      
}   
//后续遍历销毁二叉树      
void freeTree(BiTNode* root)      
{      
    if (root!=NULL)      
    {      
 
        if (root->lchild)      
        {      
            freeTree(root->lchild);      
            root->lchild = NULL;      
        }      
        if (root->rchild)      
        {      
            freeTree(root->rchild);      
            root->rchild = NULL;      
        }      
        if (root!=NULL)      
        {      
            free(root);      
            root=NULL;      
        }      
    }      
}      
int main()  
{  
    int a[14] = {19, 32, 28, 14, 37, 18, 5, 21, 23, 25,12,30,11,15};      
    int n = 14;      
    BiTree T,f=NULL,p=NULL;     
    bool result=false;  
 
    // 并非所有的a[]都能构造出BITree,所以，最好对createBITree的返回值进行判断      
    result = createBST(T, a, n);  
 
    if (!result)  
    {  
        cout<<"createBST error"<<endl;  
        system("pause");
        return -1;  
    }  
 
    inOrderBST(T);      
    cout << endl;      
 
    searchBST(T,3,f,p);
 
    cout<<p->data<<endl;
    freeTree(T);    
 
    system("pause");  
    return 0;  
}