二叉搜索树,又称二叉查找树
定义:
一棵二叉树,可以为空,若不为空,则满足以下性质
- 非空左子树的所有键值小于其根结点的键值
- 非空右子树的所有键值大于其根结点的键值
- 左、右子树都是二叉搜索树
操作:
1.查找指定值x:
- 从根节点开始,如果树为空,返回NULL
- 若搜索树非空,则将根结点和被查找数x进行比较
①若x小于根结点键值,则递归搜索左子树
②若x大于根结点键值,则递归搜索右子树
③若两者相等,则返回指向该结点的指针
Position Find (ElemenType x,BinTree BST)
{
if (!BST) return NULL; //树为空,返回NULL
if(x < BST->Data ) //若x小于根结点键值,则递归搜索左子树
return Find(x,BST->Left)
else if( x> BST->Data ) //若x大于根结点键值,则递归搜索右子树
return Find(x,BST->Right)
else //若两者相等,则返回指向该结点的指针
return BST;
}
由于非递归函数的执行效率高,因此将“尾递归”改为迭代函数
Position Find (ElemenType x,BinTree BST)
{
while(BST){
if(x < BST->Data ) //若x小于根结点键值,向左子树移动
BST = BST->Left;
else if( x> BST->Data ) //若x大于根结点键值,向右子树移动
BST = BST->Right;
else
return BST;
}
return NULL;
}
由此可见查找效率取决于树的高度
2.查找最大值最小值:
最大值:在树的最右分枝的端结点上
最小值:在树的最左分枝的端结点上
Position FindMin( BinTree BST)
{
if( !BST ) return NULL;
else if(!BST->Left)
return BST;
else
return FindMin(BST->left);
}
Position FindMax( BinTree BST)
{
if( BST )
while( BST->Right )
BST = BST->Right;
return BST;
}
3.插入:
首先要找到插入的位置
①如果x < BST->data,沿着左子树继续搜索
②如果x > BST->data,沿着右子树继续搜索
③如果x = BST->data,则说明重复
④创建一个新结点存储元素e,修改指针使得元素e和二叉搜索树链接
BinTree Insert( BinTree BST, ElementType X ) {
if( !BST ){ // 若原树为空,生成并返回一个结点的二叉搜索树,即将插入时用到
BST = (BinTree)malloc(sizeof(struct TNode));
BST->Data = X;
BST->Left = BST->Right = NULL;
}
else { // 开始找要插入元素的位置
if( X < BST->Data )
BST->Left = Insert( BST->Left, X ); //左孩子为空时插入
else if( X > BST->Data )
BST->Right = Insert( BST->Right, X ); //右孩子为空时插入
/* else X已经存在,什么都不做 */
}
return BST;
}
4.删除:
①如果要删除的是叶结点:直接删除,并再修改其父结点指针为NULL
②要删除的结点有一个孩子结点:将其父结点的指针指向要删除结点的孩子结点
③要删除的结点有两个孩子结点,用右子树的最小元素或者左子树的最大元素替代被删除结点
BinTree Delete( BinTree BST, ElementType X ) {
Position Tmp;
if( !BST )
printf("要删除的元素未找到");
else {
if( X < BST->Data )
BST->Left = Delete( BST->Left, X ); // 从左子树递归删除
else if( X > BST->Data )
BST->Right = Delete( BST->Right, X ); /* 从右子树递归删除
else { //BST就是要删除的结点
/* 如果被删除结点有左右两个子结点 */
if( BST->Left && BST->Right ) { //从右子树中找最小的元素填充删除结点
Tmp = FindMin( BST->Right );
BST->Data = Tmp->Data; //从右子树中删除最小元素
BST->Right = Delete( BST->Right, BST->Data );
}
else {
/* 被删除结点有一个或无子结点 */
Tmp = BST;
if( !BST->Left ) /* 只有右孩子或无子结点 */
BST = BST->Right;
else /* 只有左孩子 */
BST = BST->Left;
free( Tmp );
}
}
}
return BST;
}
整理自浙江大学数据结构慕课