二叉搜索（排序或查找）树

文章目录

一、二叉搜索树概念

二、二叉排序树的查找

三、 二叉排序树的最值

四、二叉排序树的插入

五、二叉排序树的删除

六、二叉排序树的打印

一、二叉搜索树概念

二叉搜索树：也叫二叉排序树或二叉查找树，是一种对排序和查找都很有用的特殊二叉树

• 它是一颗特殊的二叉树，可以为空树，若不空，则
  ①非空左子树的所有结点的值小于其根节点的值
  ②非空右子树的所有结点的值小于其根节点的值
  ③左、右子树都是二叉树
• 二叉搜索树支持对数时间的搜索，支持对数时间级别的插入和删除。
• 一个无序序列可以通过构建一棵二叉排序树，从而变成一个有序序列。

二、二叉排序树的查找

• 如果相等，查找成功；
• 如果比较结果为根结点的值较大，则说明该值可能存在其左子树中；
• 如果比较结果为根结点的值较小，则说明该值可能存在其右子树中；

//递归 
BSTree SearchBST(BSTree T,ElemType e)
{
   
//如果递归过程中 T 为空，则查找结果，返回NULL；或者查找成功，返回指向该关键字的指针
	if(!T||e==T->data)
	return T;
	else if(e < T->data)
	return SearchBST( T->lchild, e);
	else if(e > T->data)
	return SearchBST( T->rchild, e);
}

//非递归 
BSTree SearchBST(BSTree T,ElemType e)
{
   
	while(T)
	{
   
		if(e < T->data)
		{
   
			T=T->lchild;
		}
		else if (e>T-data)
		{
   
			T=T->rchild;
		}
		else
		break;
	}
	return T;
}

三、二叉排序树的最值

//非递归
Position FindMin( BinTree BST )
{
   
	if (BST)
	{
   
		while (BST->Left)
		{
   
			BST= BST->Left;//狂左
		}
	}
	return BST;

}
Position FindMax( BinTree BST )
{
   
	if (BST)
	{
   
		while (BST->Right)//狂右
		{
   
			BST= BST->Right;
		}
	}
	return BST;
}
Position FindMin( BinTree BST )
{
   //如果递归过程中 BST 为空，则查找结果，返回NULL；或者查找成功，返回指向该关键字的指针
	if(!BST||!BST->Left) //空树或找到
	return BST;
	else return FindMin (BST->Left);
}
Position FindMax( BinTree BST )
{
   
	if(!BST||!BST->Right) 
	return BST;
	else return FindMin( BST->Right);
}
}

四、二叉排序树的插入

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;
}

五、二叉排序树的删除

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;
}

六、二叉排序树的打印

//二叉排序树的打印
//中序打印
void printTree(BinTree T)
{
   
	if (T)
	{
   
		printTree(T->lchild);
		printf("%d",T->data);
		printTree(T->rchild);
	}
}