二叉排序树的查找长度_c 二叉排序树_二叉排序树删除节点

二叉排序树又称二叉查找树，它是一种对排序和查找都很有用的特殊二叉树。

（1）若它的左子树不为空，则左子树上的所有结点的值均小于它的根结点的值；

（2）若它的右子树不为空，则右子树上所有结点的值均小于它的根结点上的值；

（3）它的左右子树本身也分别为二叉排序树。

通过中序排列我们发现中序遍历的结果是结点的值是由低到高的。

typedef struct{
  keyType key；
  InfoType other info；
}ElemType；
typedef struct BSTNode
{
 ElemType data；
 struct BSTNode *lchild，*rchild；

}BSTNode，*BSTreet；

二叉排序树的 查找依然沿用前面介绍的顺序查找和折半查找。

（1）若二叉排序树为空，则查找失败，则返回空指针。

（2）若二叉排序树非空，将给定值key与根结点的关键字T->data.Key进行比较：

若key等于T->data.key,则查找成功，返回根结点地址；

若key小于T->data.key，则进一步查找左子树；

若key大于T->data.key，则进一步查找右子树。

     BSTree SearchBST(BSTree T,KeyType key)
     {
            //在根指针T所指二叉排序树种递归地查找某个关键字等于key的数据元素
            //若查找成功，则返回指向该数据元素结点的指针，否则返回空指针

            if((!T)||key==T->data.key) return T;    //查找结束
            else if(keydata.key) return SearchBST(T->child,key);//在左子树上继续查找
        else return SearchBST(T->child,key);//在右子树上继续查找
    }

（1）若二叉排序树为空，则待插入结点*S作为根结点插入到空树中。

（2）若二叉排序树非空，则将key与根结点的关键字T->data.Key进行比较：

若key等于T->data.key，则停止插入；

若key小于T->data.key,则将*S插入左子树；

若key大于T->data.key,，则将*S插入右子树。

/*  当二叉排序树T中不存在关键字等于key的数据元素时， */
/*  插入key并返回TRUE，否则返回FALSE */
Status InsertBST(BiTree *T, int key) 
{  
    BiTree p,s;
if (!SearchBST(*T, key, NULL, &p)) /* 查找不成功 */
{
    s = (BiTree)malloc(sizeof(BiTNode));
    s->data = key;  
    s->lchild = s->rchild = NULL;  
        if (!p) 
        *T = s;            /*  插入s为新的根结点 */
    else if (keydata) 
        p->lchild = s;    /*  插入s为左孩子 */
    else 
    p->rchild = s;  /*  插入s为右孩子 */
return TRUE;
} 
else 
return FALSE;  /*  树中已有关键字相同的结点，不再插入 */
}

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-27935-1.html