(七)数据结构之搜索二叉树的简单实现

蔚落 2022-06-08 06:14 98阅读 0赞

## 1、搜索二叉树的简单定义 ##

二叉搜索树(BST, Binary Search Tree), 也称二叉排序树或者二叉查找树。  
定义：  
a、是一颗二叉树，可以为空，也可以不为空。  
b、非空左子树的所有键值小于其根结点的键值  
c、非空右子树的所有键值大于其根结点的键值。  
d、左、右子树都是二叉搜索树。

## 2、具体实现 ##

搜索二叉树是特殊的二叉树，所以这里只实现搜索二叉树特殊的操作，基本操作可以参考二叉树的基本操作，可以参考这篇文章： [http://blog.csdn.net/tech\_pro/article/details/78012270][http_blog.csdn.net_tech_pro_article_details_78012270]。

### 2.1 基本数据结构 ###

/* 二叉树的基本数据结构的定义 */
    typedef int ElementType;
    typedef struct TreeNode *BinTree;
    typedef BinTree Position;
    struct TreeNode{
    	ElementType Data;
    	BinTree Left;
    	BinTree Right;
    };

### 2.2 插入操作 ###

/* 二叉搜索树的插入算法 */
    BinTree Insert( ElementType X, BinTree BST )
    {
    	if( !BST )
    	{
    		/*若原树为空，生成并返回一个结点的二叉搜索树*/
    		BST = (BinTree)malloc(sizeof(struct TreeNode));
    		BST->Data = X;
    		BST->Left = BST->Right = NULL;
    	}
    	else
    	{
    		/*开始找要插入元素的位置*/
    		if( X < BST->Data )
    			BST->Left = Insert( X, BST->Left);		/*递归插入左子树*/
    		else if( X > BST->Data )
    			BST->Right = Insert( X, BST->Right);	/*递归插入右子树*/
    	}
    	return BST;
    }

### 2.3 删除操作 ###

/* 二叉树的删除操作，如果该结点有左右两个子结点，则使用右子树的最小元素替代该点 */
    BinTree Delete( ElementType X, BinTree BST )
    { 
    	Position Tmp = NULL;
    	if( !BST ) printf("The BST is empty!\n");
    	else if( X < BST->Data )
    		BST->Left = Delete( X, BST->Left); 		/* 左子树递归删除 */
    	else if( X > BST->Data )
    		BST->Right = Delete( X, BST->Right); 	/* 右子树递归删除 */
    	else 	/*找到要删除的结点 */
    	{
    		if( BST->Left && BST->Right )
    		{ 
    			/*被删除结点有左右两个子结点 */
    			Tmp = FindMin( BST->Right );
    			/*在右子树中找最小的元素填充删除结点*/
    			BST->Data = Tmp->Data;
    			BST->Right = Delete( BST->Data, BST->Right);	/*在删除结点的右子树中删除最小元素*/
    		} 
    		else 
    		{
    			/*被删除结点有一个或无子结点*/
    			Tmp = BST;
    			if( !BST->Left ) 		/* 有右孩子或无子结点*/
    				BST = BST->Right;
    			else if( !BST->Right ) 	/*有左孩子或无子结点*/
    				BST = BST->Left;
    			free( Tmp );
    		}
    	}
    	return BST;
    }

### 2.4 查找指定元素 ###

有两种方式：递归和非递归方式。

#### 2.4.1 递归方式 ####

/* 查找指定元素的位置 */
    Position Find( ElementType X, BinTree BST )
    {
    	if( !BST ) return NULL; 	/*查找失败*/
    	if( X > BST->Data )
    		return Find( X, BST->Right ); /*在右子树中继续查找*/
    	else if( X < BST->Data )
    		return Find( X, BST->Left ); /*在左子树中继续查找*/
    	else 
    		return BST; 				 /*查找成功，返回结点的找到结点的地址*/
    }

#### 2.4.2 非递归方式 ####

/* 查找指定元素的位置 */
    Position IterFind( ElementType X, BinTree BST )
    {
    	while(BST)
    	{
    		if( X > BST->Data )
    			BST = BST->Right;
    		else if (X < BST->Data)
    			BST = BST->Left;
    		else 
    			return BST;
    	}
    	return NULL;
    }

### 2.5 查找最小值 ###

也分为两种方式：递归和非递归。

#### 2.5.1 递归方式 ####

/* 找到这个二叉树中的最小值的位置 */
    Position FindMin( BinTree BST )
    {
    	if( !BST ) return NULL; /*空的二叉搜索树，返回NULL*/
    	else if( !BST->Left )
    		return BST; 		/*找到最左叶结点并返回*/
    	else
    		return FindMin( BST->Left ); /*沿左分支继续查找*/
    }

#### 2.5.2 非递归方式 ####

/* 查找最小元素所在的位置 */
    Position IterFindMin( BinTree BST )
    {
    	if(BST )
    	{
    		/*沿左分支继续查找，直到最左叶结点*/
    		while( BST->Left) BST = BST->Left;
    	}
    	return BST;
    }

### 2.6 查找最大值 ###

也分为两种：递归和非递归。

#### 2.6.1 递归方式 ####

/* 找到这个二叉树中的最大值的位置 */
    Position FindMax( BinTree BST )
    {
    	if( !BST ) return NULL; /*空的二叉搜索树，返回NULL*/
    	else if (!BST->Right)
    		return BST;
    	else
    		return FindMax( BST->Right); /*沿右分支继续查找*/
    }

#### 2.6.2 非递归方式 ####

/* 查找最大元素所在的位置 */
    Position IterFindMax( BinTree BST )
    {
    	if(BST )
    	{
    		/*沿右分支继续查找，直到最右叶结点*/
    		while( BST->Right ) BST = BST->Right;
    	}
    	return BST;
    }

### 2.7 完整示例代码实现 ###

/* 二叉搜索树的基本实现 */
    #include <stdio.h>
    #include <stdlib.h>
    
    /* 二叉树的基本数据结构的定义 */
    typedef int ElementType;
    typedef struct TreeNode *BinTree;
    typedef BinTree Position;
    struct TreeNode{
    	ElementType Data;
    	BinTree Left;
    	BinTree Right;
    };
    
    /* 创建一颗二叉树, 先创建根节点，然后创建左子树，最后创建右子树*/
    BinTree CreatBinTree()  
    {  
        ElementType data;  
        BinTree T;  
        scanf("%d", &data);   // 通过控制台获得一个结点数据  
        if(0 == data)       // 如果为空树结点  
        {  
            T = NULL;  
        }  
        else    // 如果为非空树结点  
        {  
            T = (BinTree)malloc(sizeof(struct TreeNode));  // 分配一块内存给根结点  
            if(NULL == T) return NULL;  
            T->Data= data;    
            T->Left = CreatBinTree();      // 递归创建左子树  
            T->Right = CreatBinTree();     // 递归创建右子树  
        }  
        return T;   // 返回树根结点  
    }  
    
    /* 销毁一颗二叉树 */
    void DestroyBinTree(BinTree BT)
    {
    	if (BT)
    	{
    		DestroyBinTree(BT->Left);
    		DestroyBinTree(BT->Right);
    		free(BT);
    		BT = NULL;
    	}
    }
    
    /********************************* 递归操作 ******************************************/
    
    /* 查找指定元素的位置 */
    Position Find( ElementType X, BinTree BST )
    {
    	if( !BST ) return NULL; 	/*查找失败*/
    	if( X > BST->Data )
    		return Find( X, BST->Right ); /*在右子树中继续查找*/
    	else if( X < BST->Data )
    		return Find( X, BST->Left ); /*在左子树中继续查找*/
    	else 
    		return BST; 				 /*查找成功，返回结点的找到结点的地址*/
    }
    
    /* 找到这个二叉树中的最小值的位置 */
    Position FindMin( BinTree BST )
    {
    	if( !BST ) return NULL; /*空的二叉搜索树，返回NULL*/
    	else if( !BST->Left )
    		return BST; 		/*找到最左叶结点并返回*/
    	else
    		return FindMin( BST->Left ); /*沿左分支继续查找*/
    }
    
    /* 找到这个二叉树中的最大值的位置 */
    Position FindMax( BinTree BST )
    {
    	if( !BST ) return NULL; /*空的二叉搜索树，返回NULL*/
    	else if (!BST->Right)
    		return BST;
    	else
    		return FindMax( BST->Right); /*沿右分支继续查找*/
    }
    
    /* 二叉搜索树的插入算法 */
    BinTree Insert( ElementType X, BinTree BST )
    {
    	if( !BST )
    	{
    		/*若原树为空，生成并返回一个结点的二叉搜索树*/
    		BST = (BinTree)malloc(sizeof(struct TreeNode));
    		BST->Data = X;
    		BST->Left = BST->Right = NULL;
    	}
    	else
    	{
    		/*开始找要插入元素的位置*/
    		if( X < BST->Data )
    			BST->Left = Insert( X, BST->Left);		/*递归插入左子树*/
    		else if( X > BST->Data )
    			BST->Right = Insert( X, BST->Right);	/*递归插入右子树*/
    	}
    	return BST;
    }
    
    /* 二叉树的删除操作，如果该结点有左右两个子结点，则使用右子树的最小元素替代该点 */
    BinTree Delete( ElementType X, BinTree BST )
    { 
    	Position Tmp = NULL;
    	if( !BST ) printf("The BST is empty!\n");
    	else if( X < BST->Data )
    		BST->Left = Delete( X, BST->Left); 		/* 左子树递归删除 */
    	else if( X > BST->Data )
    		BST->Right = Delete( X, BST->Right); 	/* 右子树递归删除 */
    	else 	/*找到要删除的结点 */
    	{
    		if( BST->Left && BST->Right )
    		{ 
    			/*被删除结点有左右两个子结点 */
    			Tmp = FindMin( BST->Right );
    			/*在右子树中找最小的元素填充删除结点*/
    			BST->Data = Tmp->Data;
    			BST->Right = Delete( BST->Data, BST->Right);	/*在删除结点的右子树中删除最小元素*/
    		} 
    		else 
    		{
    			/*被删除结点有一个或无子结点*/
    			Tmp = BST;
    			if( !BST->Left ) 		/* 有右孩子或无子结点*/
    				BST = BST->Right;
    			else if( !BST->Right ) 	/*有左孩子或无子结点*/
    				BST = BST->Left;
    			free( Tmp );
    		}
    	}
    	return BST;
    }
    
    
    /* 先序递归遍历 */
    void PreOrderTraversal( BinTree BST )
    {
    	if( BST ) 
    	{
    		printf("%d ", BST->Data);
    		PreOrderTraversal( BST->Left );
    		PreOrderTraversal( BST->Right );
    	}
    }
    
    /* 中序递归遍历 */
    void InOrderTraversal( BinTree BST )
    {
    	if( BST ) 
    	{
    		InOrderTraversal( BST->Left );
    		printf("%d ", BST->Data);
    		InOrderTraversal( BST->Right );
    	}
    }
    
    /* 后序递归遍历 */
    void PostOrderTraversal( BinTree BST )
    {
    	if( BST )
    	{
    		PostOrderTraversal( BST->Left );
    		PostOrderTraversal( BST->Right);
    		printf("%d ", BST->Data);
    	}
    }
    
    
    /********************************* 非递归操作 ****************************************/
    
    /* 查找指定元素的位置 */
    Position IterFind( ElementType X, BinTree BST )
    {
    	while(BST)
    	{
    		if( X > BST->Data )
    			BST = BST->Right;
    		else if (X < BST->Data)
    			BST = BST->Left;
    		else 
    			return BST;
    	}
    	return NULL;
    }
    
    /* 查找最小元素所在的位置 */
    Position IterFindMin( BinTree BST )
    {
    	if(BST )
    	{
    		/*沿左分支继续查找，直到最左叶结点*/
    		while( BST->Left) BST = BST->Left;
    	}
    	return BST;
    }
    
    
    /* 查找最大元素所在的位置 */
    Position IterFindMax( BinTree BST )
    {
    	if(BST )
    	{
    		/*沿右分支继续查找，直到最右叶结点*/
    		while( BST->Right ) BST = BST->Right;
    	}
    	return BST;
    }
    
    
    /* 程序入口 */
    int main()
    {
    	ElementType input;
    	BinTree node = NULL;
    	BinTree tree = NULL;
    
    	/* 创建一颗二叉树 */
    	tree = CreatBinTree();
    
    	/* 遍历 */
    	printf("************************Traversal***************************\n");
    	printf("Pre : "); PreOrderTraversal(tree); printf("\n");
    	printf("In : "); InOrderTraversal(tree); printf("\n");
    	printf("Post : "); PostOrderTraversal(tree); printf("\n");
    
    	/* 递归查找 */
    	printf("************************Search******************************\n");
    	printf("Input a number to search : ");
    	scanf("%d", &input);
    	node = Find(input, tree);
    	printf("The search value is : %d\n", node->Data);
    	node = FindMin(tree);
    	printf("Min value is : %d\n", node->Data);
    	node = FindMax(tree);
    	printf("Max value is : %d\n", node->Data);
    
    	/* 非递归查找 */
    	printf("************************IterSearch******************************\n");
    	printf("Input a number to search : ");
    	scanf("%d", &input);
    	node = IterFind(input, tree);
    	printf("The search value is : %d\n", node->Data);
    	node = IterFindMin(tree);
    	printf("Min value is : %d\n", node->Data);
    	node = IterFindMax(tree);
    	printf("Max value is : %d\n", node->Data);
    
    	/* 插入一个元素 */
    	printf("************************Insert******************************\n");
    	printf("Input a number to insert : ");
    	scanf("%d", &input);
    	tree = Insert(input, tree);
    	printf("Pre : "); PreOrderTraversal(tree); printf("\n");
    
    	/*  删除一个元素*/
    	printf("************************Delete******************************\n");
    	printf("Input a number to delete : ");
    	scanf("%d", &input);
    	tree = Delete(input, tree);
    	printf("Pre : "); PreOrderTraversal(tree); printf("\n");
    
    	DestroyBinTree(tree);		/* 销毁一颗二叉树 */
    	
    	return 0;
    }

[http_blog.csdn.net_tech_pro_article_details_78012270]: http://blog.csdn.net/tech_pro/article/details/78012270