二叉排序树学习内容

二叉排序树的基本概念和查找

定义

二叉排序树的定义是一个递归定义的过程。

确保所有小于Root node value的节点都位于Left subtree上 ， 而大于Root node value的节点均位于Right subtree上

查找步骤：

①当输入值与根节点的键相等时, 确保找到目标记录；
②如果输入值小于根节点的键, 则转向左子树继续搜索；否则
③如果输入值大于根节点的键, 则转向右子树继续搜索。

在二叉排序树上进行查找，类似折半查找。

查找算法

    //递归实现
    BSTree SearchBST(BSTree bst, KeyType key){
    	if(!bst) return NULL;
    	else if(bst->key==key) return bst;
    	else if(key<bst->key)
    		return SearchBST(bst->lchild,key);
    	else
    		return SearchBST(bst->rchild,key);
    }

二叉排序树的插入与删除

插入操作仅在搜索未找到目标数据时触发；当二叉排序树为空时，新插入的节点将自动成为根节点。

插入操作仅在搜索未找到目标数据时触发；