经典算法系列之（六）：七大查找——树表查找

活动地址：CSDN21天学习挑战赛

学习的最大理由是想摆脱平庸，早一天就多一份人生的精彩；迟一天就多一天平庸的困扰

 一.什么是二叉排序树        

二叉排序树或是空树，或是满足以下性质的二叉树：

1.若其左子树非空，则左子树上所有结点的值均小于根结点的值
2.若右子树非空，则右子树上所有结点的值均大于等于根结点的值
3.其左右子树本身又各是一颗二叉排序树

其中左子树上所有结点的值都小于根结点的值，右子树上所有结点的值都大于等于根结点的值。
每个子节点也都遵循整个定义

 

对二叉排序树进行中序遍历可以得到一个按关键字从小到大的有序表

​二.查找思路

        1.若二叉排序树为空，则查找失败，返回空指针。
        2.若非空，将给定值key与根结点的关键字进行比较，类似于二分查找法。

三.插入      

1.若二叉树排序树为空，则插入结点作为根结点插入到空树中
2.若不为空，继续在其左、右子树上查找。
         若树中已有，就不再插入.
         若树中没有，查找直到某个叶子结点的左子树或右子树为空为止，则插入结点应为叶子结点的左孩子或右孩子

通过插入算法可以生成一个二叉排序树。一个无序序列可通过构造二叉排序树变成一个有序序列。，构造树的过程就是对无序序列进行排序的过程。插入的结点均为叶子结点，无需移动其他结点，相当于在有序序列上插入记录二无需移动其他记录。

TreeNode* bstInsert(TreeNode** T,int data)
{
    if(*T==NULL)//如果是空树则直接为根节点
    {
        *T=(TreeNode*)malloc(sizeof(TreeNode));//开辟空间
        (*T)->data=data;//赋值
        (*T)->lchild=NULL;//初始化
        (*T)->rchild=NULL;//初始化
    }
    else if(data<(*T)->data)//如果比根节点小则继续递归和左孩子比较
    {
        bstInsert(&((*T)->lchild),data);
    }
    else if(data==(*T)->data)//如果相等则不进行操作，因为不能有相同的数存在
        return ;
    else 
        bstInsert(&((*T)->rchild),data);//如果比根节点大则继续递归和右孩子比较
}

四.查找

 

TreeNode* bstInsert(TreeNode** T,int data)
{
    if(*T==NULL)//如果是空树则直接为根节点
    {
        *T=(TreeNode*)malloc(sizeof(TreeNode));//开辟空间
        (*T)->data=data;//赋值
        (*T)->lchild=NULL;//初始化
        (*T)->rchild=NULL;//初始化
    }
    else if(data<(*T)->data)//如果比根节点小则继续递归和左孩子比较
    {
        bstInsert(&((*T)->lchild),data);
    }
    else if(data==(*T)->data)//如果相等则不进行操作，因为不能有相同的数存在
        return ;
    else 
        bstInsert(&((*T)->rchild),data);//如果比根节点大则继续递归和右孩子比较
}

 五.删除        

删除只能和删除结点，不能删除以结点为根的子树，且还要保证删除后所得二叉树仍满足二叉排序树的性质不变。

1.被删除的结点是叶子结点：直接删去该结点。
2.被删除的结点只有右子树或者只有左子树，用其右子树或者左子树替换 
3.被删除的结点既有左子树又有右子树，找到删除结点的左子树中的最大值，将其替换删除结点（或者找右子树上最小的结点）