【数据结构】二叉搜索树的特点及实现

二叉搜索树，又称二叉查找树

定义：
一棵二叉树，可以为空，若不为空，则满足以下性质

• 非空左子树的所有键值小于其根结点的键值
• 非空右子树的所有键值大于其根结点的键值
• 左、右子树都是二叉搜索树

操作：
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; 
}
    

整理自浙江大学数据结构慕课