二叉查找树的查找和插入

常用的查找算法

倒排索引

• 次关键码
• 记录号表

二叉排序树，又称为二叉查找数，它或者是一棵空树，或者是具有下列性质的二叉树。

• 若它的左子树不空，则左子树上所有节点的值均小于它的根结构的值
• 若它的右子树为空，则右子树上所有节点的值均大于它的根节点的值

二叉查找树的插入

• 定义

typedef struct BiTNode{

int data;
struct BiTNode*lchild,*rchild;
}BiTNode,*BiTree;  

• 插入使用递归的方式找到最合适的地方

typedef bool Status; // 1.T为二叉链表 2.key为要查找的关键字 3.f指向T的双亲。当T为根节点的时候，f的初值是NULL 4.p 为查找成功后可以查找节点的位置 Status searchBST(BiTree T, int key,BiTree f,BiTree*p){

if (!T) {   //如果查找不成功
    *p = f;
    return false;
}else if (key == T->data){
    *p = T;
    return true;
}else if (key< T->data){
    return  searchBST(T->lchild, key, T, p);
}else if (key> T->data){
    return  searchBST(T->rchild, key, T, p);
}
return  true;}

• 二叉查找树 基于查找的基础上 进行插入

//二叉树的插入操作 1. 先去查找有没有 2.没有的话，则先创建一个节点，分别为节点赋值。然后判断插入节点和当前节点的关系。 Status insertBST(BiTree *T,int key){

// f为T的双亲节点。p为当前节点
BiTree s ,p ;
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 if (key>p->data){
        p->rchild = s;
        
    }
    return  true;
}
return  false;}