C语言数据结构之二叉排序树

矫情吗；* 2022-12-02 01:11 198阅读 0赞

## C语言数据结构之二叉排序树 ##

tips：前些天学习了线索二叉树，今天来总结一下二叉排序树的相关操作。

--------------------

**二叉排序树(BST)：**

*  若左子树非空，则左子树上所有结点的值均小于根结点的值；
 *  若右子树非空，则右子树上所有结点的值均大于根结点的值；
 *  二叉排序树的左右子树也是一棵二叉排序树；

总之，二叉排序树的中序序列是一个递增的序列。

二叉排序树的存储结构与普通二叉树相同：

typedef struct node
    {
        
    	int key;//关键字
    	struct node *left;
    	struct node *right;
    }Node,*pNode;

--------------------

**1、二叉排序树的构造及插入**

思路：

*  若二叉排序树为空，则直接插入结点作为根结点；
 *  若二叉排序树非空，当值小于根结点时，插入左子树；
 *  若二叉排序树非空，当值等于根结点时，不予插入；
 *  若二叉排序树非空，当值大于根结点时，插入右子树；

**注意，这里我们要在子函数修改在主函数声明的bt的值，所以这里我们在子函数中传入bt的地址！**

具体实现：

//二叉排序树的插入
    int BSTInsert(pNode *bt, int key)
    {
        
    	if ((*bt) == NULL)
    	{
        
    		//二叉排序树为空，直接插入
    		pNode ptmp = (pNode)malloc(sizeof(Node));
    		*bt = ptmp;
    		(*bt)->key = key;
    		(*bt)->left = (*bt)->right=NULL;
    		return 1;//插入成功
    	}
    	else if (key == (*bt)->key)
    		return 0;//key已经存在，不予插入
    	else if (key < (*bt)->key)
    	{
        
    		return BSTInsert(&((*bt)->left), key);//递归插入左子树
    	}		
    	else
    	{
        
    		return BSTInsert(&((*bt)->right), key);//递归插入右子树
    	}
    		
    }
    
    //构建二叉排序树
    void CreateBST(pNode *bt, int *key)
    {
        
    	int i;
    	(*bt) = NULL;//清空树
    	for (i = 0; i < N; i++)
    		BSTInsert(bt,key[i]);
    }

--------------------

**2、二叉排序树的查找**

思路：

*  从根结点开始查找，若相等，则查找成功；
 *  若查找的值小于根结点，则查找左子树；
 *  若查找的值大于根结点，则查找右子树；

具体实现：

//二叉排序树的查找
    pNode BSTSearch(pNode bt, int key)
    {
        
    	while (bt != NULL && key != bt->key)
    	{
        
    		if (key < bt->key)
    			bt = bt->left;//小于，查找左子树
    		else
    			bt = bt->right;//大于，查找右子树
    	}
    	return bt;
    }

--------------------

**3、二叉排序树的删除**

思路：

*  若删除的结点时叶子结点，则直接删除；
 *  若删除的结点i只有一棵子树，则让i的子树成为i父结点的子树（替代i，独子继承父业）；
 *  若被删除结点i有两棵子树，则让i的中序序列直接后继替代i，并删除后继结点；

--------------------

以上就是二叉排序树的构建及查找，删除思路。接下来我们在main()函数中测试一下：

int main()
    {
        
    	int arr[N] = {
         1,4,2,7,5,6,9,8,3,0 };
    	pNode bt;
    
    	CreateBST(&bt, arr);//结束后，bt指向arr[0]
    
    	//中序打印
    	printf("中序遍历：");
    	midorder(bt);
    	printf("\n");
    
    	printf("bt->key=%d\n", bt->key);
    
    	pNode pSearchNode = BSTSearch(bt,5);
    	if (pSearchNode != NULL)
    	{
        
    		printf("pSearchNode的key：%d\n", pSearchNode->key);
    	}
    	else
    	{
        
    		printf("查找的值不存在!\n");
    	}
    	
    
    
    	return 0;
    }

测试结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70_pic_center]  
**可以看到二叉排序树的中序遍历时递增的！**

--------------------

tips：生是偶然，活是必然，生活不是易然。人在一生的向往面前，有时只是一叶草的语言。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/ef095da2f02b47709fb0d60778611817.png