二叉搜索树相关操作及其应用

柔光的暖阳◎ 2022-05-11 14:52 155阅读 0赞

### 文章目录 ###

*   *  二叉搜索树
     *  查找
     *   *   *  递归查找
             *  非递归查找
     *  插入
     *   *   *  递归插入
             *  非递归插入
     *  删除

## 二叉搜索树 ##

*  左孩子小于根节点
 *  右孩子大于根节点  
    **二叉排序树中序的结果是升序的**

int arr[] = { 5, 3, 7, 1, 4, 6, 8, 0, 2, 9 };

![在这里插入图片描述][70]

typedef int Key;
    	
    	typedef struct BSTreeNode
    	{
    		Key key;
    		struct BSTreeNode *left;
    		struct BSTreeNode *right;
    	
    	}BSTreeNode;

## 查找 ##

先判断根节点  
    找到了，return  
    没找到，开始查找左孩子  
            查找右孩子

#### 递归查找 ####

int BSTreeSearch(BSTreeNode *root, Key key)
    	{
    		if (root == NULL)
    		{
    			return -1; //-1表示没找到哦，0表示找到了
    		}
    		if (root->key == key)
    		{
    			return 0;
    		}
    		else if (root->key < key)
    		{
    			return BSTreeSearch(root->right, key);
    		}
    		else
    		{
    			return BSTreeSearch(root->left, key);
    		}
    	}

#### 非递归查找 ####

int BSTreeSearchLoop(BSTreeNode *root, Key key)
    	{
    		BSTreeNode *cur = root;
    		while (cur != NULL)
    		{
    			if (cur->key == key)
    			{
    				return 0;
    			}
    			else if (cur->key < key)
    			{
    				cur = cur->right;
    			}
    			else
    			{
    				cur = cur->left;
    			}
    		}
    		return -1;
    	}

## 插入 ##

#### 递归插入 ####

BSTreeNode *CreateBSTreeNode(Key key)
    {
    	BSTreeNode *node = (BSTreeNode *)malloc(sizeof(BSTreeNode));
    	node->key = key;
    	node->left = NULL;
    	node->right = NULL;
    	return node;
    }
    
    int BSTreeInsert(BSTreeNode **pproot, Key key)
    {
    	if (*pproot == NULL)
    	{
    		*pproot = CreateBSTreeNode(key);
    		return 0;
    	}
    	if ((*pproot)->key == key)
    	{
    		return -1;
    	}
    	else if ((*pproot)->key < key)
    	{
    		return BSTreeInsert(&(*pproot)->right, key);
    	}
    	else
    	{
    		return BSTreeInsert(&(*pproot)->left, key);
    	}
    }

#### 非递归插入 ####

int BSTreeInsertLoop(BSTreeNode **pproot, Key key)
    	{
    		assert(pproot);
    		BSTreeNode *cur = *pproot;
    		BSTreeNode *parent = NULL;
    		
    		while (cur != NULL)
    		{
    			if (cur->key == key)
    			{
    				return -1;
    			}
    			parent = cur;
    			if (cur->key < key)
    			{
    				cur = cur->right;
    			}
    			else
    			{
    				cur = cur->left;
    			}
    		}
    		BSTreeNode *node = CreateBSTreeNode(key);
    		if (parent == NULL)
    		{
    			*pproot = node;
    		}
    		else if (parent->key < key)
    		{
    			parent->right = node;
    		}
    		else if (parent->key > key)
    		{
    			parent->left = node;
    		}
    		return 1;
    	}

## 删除 ##

删除将会分为8种情况：  
![在这里插入图片描述][70 1]

int BSTreeRemove(BSTreeNode **pproot, Key key)
    	{
    		assert(pproot);
    		BSTreeNode *cur = *pproot;
    		BSTreeNode *parent = NULL;
    	
    		while (cur != NULL)
    		{
    			if (cur->key == key)
    			{
    				if (cur->left == NULL)
    				{
    					if (parent == NULL)
    					{
    						*pproot = cur->right;
    					}
    					else if (cur->key < parent->key)
    					{
    						parent->left = cur->right;
    					}
    					else
    					{
    						parent->right = cur->right;
    					}
    					free(cur);
    					return 0;
    				}
    				else if (cur->right == NULL)
    				{
    					if (parent == NULL)
    					{
    						*pproot= cur->left;
    					}
    					else if (cur->key < parent->key)
    					{
    						parent->left = cur->left;
    					}
    					else
    					{
    						parent->right = cur->left;
    					}
    					free(cur);
    					return 0;
    				}
    				else
    				{
    					BSTreeNode *del = cur->right;
    					BSTreeNode *delParent = cur;
    					while (del->left != NULL)
    					{
    						delParent = del;
    						del = del->left;
    					}
    					cur->key = del->key;
    					if (delParent == cur)
    					{
    						delParent->right = del->right;
    					}
    					else
    					{
    						delParent->left = del->right;
    					}
    					free(del);
    					return 0;
    				}
    			}
    			parent = cur;
    			if (cur->key < key)
    			{
    				cur = cur->right;
    			}
    			else
    			{
    				cur = cur->left;
    			}
    		}
    		return -1;
    	}

[70]: /images/20220505/7f2a539d50da48dea7d3b2444d24024b.png
[70 1]: /images/20220505/e1ab55e235754e41974a15536fd29a8e.png