【数据结构 - - - 二叉搜索树】一篇文章搞定二叉搜索树

心已赠人 2023-01-03 04:22 119阅读 0赞

# 1. 二叉搜索树基本概念 #

二叉搜索树又称为二叉排序树，它或是一颗空树，或者是具有以下性质的二叉树：

*  若节点A的左子树不为空，则左子树上的节点值及其所有的子树的节点值都比节点A的节点值小
 *  若节点A的右子树不为空，则右子树上的节点值及其所有的子树的节点值都比节点A的节点值大
 *  节点A的左右子树都是二叉搜索树

# 2. 二叉搜索树的查找 #

若根结点不为空：

*  如果根节点值== 待查找值 返回true
 *  如果根节点值 < 待查找值 ，在其左子树上查找
 *  如果根节点值 > 待查找值 ，在其右子树上查找

否则，该树上没有该值

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

Node* Find(const T& data)
    	{ 
    		Node* cur = root;
    		while (cur)
    		{ 
    			if (data == cur->data)
    				return cur;
    			else if (data < cur->data)
    				cur = cur->left;
    			else
    				cur = cur->right;
    		}
    		return NULL;
    	}

# 3. 二叉搜索树的插入 #

1.  树为空，直接插入
2.  查找 待插入位置，并在每一次迭代中保存父节点
    
     *  如果根节点值 < 待插入值 ，在其左子树上寻找插入位置
     *  如果根节点值 >= 待插入值 ，在其右子树上寻找插入位置
     *  如果根结点为NULL，则找到待插入位置
3.  插入节点
    
     *  如果父节点值 < 待插入值 ，在其左子树上插入
     *  如果根节点值 > 待插入值 ，在其右子树上插入

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

bool Insert(const T& data)
    { 
        if (nullptr == root)
        { 
            root = new Node(data);
            return true;
        }
    
        //1.找待插入节点在树中的位置
        Node* cur = root;
        Node* parent = root;	//记录待插入节点插入位置的父节点
        while (cur)
        { 
            parent = cur;
            if (data < cur->data)
            cur = cur->left;
            else if (data > cur->data)
            cur = cur->right;
            else
            return false;
        }
        
        //2.插入节点
        cur = new Node(data);
        if (data < parent->data)
        	parent->left = cur;
        else if (data > parent->data)
        	parent->right = cur;
        else
        	return false;
        	
        return true;
    }

# 4. 二叉搜索树的删除 #

首先查找元素是否在二叉搜索树中，如果不存在，则返回\*\*,\*\* 否则要删除的结点可能分下面四种情况：

1.  要删除的结点 无孩子结点
2.  要删除的结点 只有左孩子结点
3.  要删除的结点 只有右孩子结点
4.  要删除的结点 有左、右孩子结点

看起来有待删除节点有4中情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程如下：  
情况**b**：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点  
情况**c**：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点  
情况**d**：在它的右子树中寻找中序下的第一个结点\*\*(**关键码最小**)\*\*，用它的值填补到被删除节点中，  
再来处理该结点的删除问题

bool Erase(const T& data)
    	{ 
    		if (nullptr == root)
    			return false;
    
    		//寻找插入位置及其父节点
    		Node* cur = root;
    		Node* parent = root;
    		while (cur)
    		{ 
    			parent = cur;
    			if (data == cur->data)
    				break;
    			else if (data < cur->data)
    				parent = cur, cur = cur->left;
    			else
    				parent = cur, cur = cur->right;
    		}
    
    		if (cur == NULL)
    			return false;
    
    		if (nullptr == cur->left)	//cur只存在右节点
    		{ 
    			if (nullptr == parent)
    			{ 
    				root = cur->right;
    			}
    			else
    			{ 
    				if (cur == parent->left)
    				{ 
    					parent->left = cur->right;
    				}
    				else
    				{ 
    					parent->right = cur->right;
    				}
    			}
    		}
    		else if (nullptr == cur->right)	 //cur只存在左节点
    		{ 
    			if (nullptr == parent)
    				root = root->left;
    			else
    			{ 
    				if (cur == parent->left)
    					parent->left = cur->left;
    				else
    					parent->right = cur->left;
    			}
    		}
    		else
    		{ 
    			//cur左右孩子都存在
    			Node* delNode = cur->right;
    			parent = cur;
    			while (delNode->right)
    			{ 
    				parent = delNode;
    				delNode = delNode->right;
    			}
    
    			cur->data = delNode->data;
    
    			if (parent->left == delNode)
    				parent->left = delNode->right;
    			else
    				parent->right = delNode->right;
    			cur = delNode;
    		}
    		delete cur;
    		return true;
    	}

# 5.二叉搜索树的模拟实现 #

template<class T>
    struct BSTreeNode 
    { 
    	BSTreeNode(T data)
    	{ 
    		left = nullptr;
    		right = nullptr;
    		this->data = data;
    	}
    	BSTreeNode* left;
    	BSTreeNode* right;
    	T data;
    };
    
    template<class T>
    class BSTree
    { 
    	typedef BSTreeNode<T> Node;
    public:
    	BSTree() : root(nullptr){ }
    	~BSTree()
    	{ 
    		Destroy(root);
    	}
    	//二叉树插入
    	bool Insert(const T& data)
    	{ 
    		if (nullptr == root)
    		{ 
    			root = new Node(data);
    			return true;
    		}
    
    		//1.找待插入节点在树中的位置
    		Node* cur = root;
    		Node* parent = root;	//记录待插入节点插入位置的父节点
    		while (cur)
    		{ 
    			parent = cur;
    			if (data < cur->data)
    				cur = cur->left;
    			else if (data > cur->data)
    				cur = cur->right;
    			else
    				return false;
    		}
    		//2.插入节点
    		cur = new Node(data);
    		if (data < parent->data)
    			parent->left = cur;
    		else if (data > parent->data)
    			parent->right = cur;
    		else
    			return false;
    		return true;
    	}
    	Node* Find(const T& data)
    	{ 
    		Node* cur = root;
    		while (cur)
    		{ 
    			if (data == cur->data)
    				return cur;
    			else if (data < cur->data)
    				cur = cur->left;
    			else
    				cur = cur->right;
    		}
    		return NULL;
    	}
    
    	bool Erase(const T& data)
    	{ 
    		if (nullptr == root)
    			return false;
    
    		//寻找插入位置及其父节点
    		Node* cur = root;
    		Node* parent = root;
    		while (cur)
    		{ 
    			parent = cur;
    			if (data == cur->data)
    				break;
    			else if (data < cur->data)
    				parent = cur, cur = cur->left;
    			else
    				parent = cur, cur = cur->right;
    		}
    
    		if (cur == NULL)
    			return false;
    
    		if (nullptr == cur->left)	//cur只存在右节点
    		{ 
    			if (nullptr == parent)
    			{ 
    				root = cur->right;
    			}
    			else
    			{ 
    				if (cur == parent->left)
    				{ 
    					parent->left = cur->right;
    				}
    				else
    				{ 
    					parent->right = cur->right;
    				}
    			}
    		}
    		else if (nullptr == cur->right)	 //cur只存在左节点
    		{ 
    			if (nullptr == parent)
    				root = root->left;
    			else
    			{ 
    				if (cur == parent->left)
    					parent->left = cur->left;
    				else
    					parent->right = cur->left;
    			}
    		}
    		else
    		{ 
    			//cur左右孩子都存在
    			Node* delNode = cur->right;
    			parent = cur;
    			while (delNode->right)
    			{ 
    				parent = delNode;
    				delNode = delNode->right;
    			}
    
    			cur->data = delNode->data;
    
    			if (parent->left == delNode)
    				parent->left = delNode->right;
    			else
    				parent->right = delNode->right;
    			cur = delNode;
    		}
    		delete cur;
    		return true;
    	}
    	void PrintTree()
    	{ 
    		InOrder(root);
    		cout << endl;
    	}
    private:
    	//中序遍历
    	void InOrder(Node* pRoot)
    	{ 
    		if (pRoot)
    		{ 
    			if (pRoot->left)
    				InOrder(pRoot->left);
    			cout << pRoot->data << " ";
    			if (pRoot->right)
    				InOrder(pRoot->right);
    		}
    	}
    	//二叉树销毁
    	void Destroy(Node*& pRoot)
    	{ 
    		if (pRoot)
    		{ 
    			if (pRoot->left)
    				Destroy(pRoot->left);
    			if (pRoot->right)
    				Destroy(root->right);
    			delete pRoot;
    			pRoot = nullptr;
    		}
    	}
    	Node* root;
    };

# 7. 二叉搜索树的现实应用 #

二叉树的应用：对二叉搜索树上的数据进行搜索/查找

> K模型：每个结点存储的是 单类型 的值

例如：对单词进行拼写错误检查，构建一个二叉搜索树包含所有单词，搜索整个树，若找到该单词代表没拼写错误

> K-V模型：每个结点存储的是 键值对形式 的数据

例如：统计一篇文章进行单词频率统计 <单词，频数>

# 6.二叉搜索树的性能分析 #

> 若二叉搜索树为 **完全二叉树**，则平均比较次数 : **logN**

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

> 若二叉搜索树为 **单只二叉树**，则平均比较次数：**N/2**

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

# 7. 二叉搜索树的OJ题 #

## LeetCode 36.二叉搜索树与双向链表 ##

链接：[二叉搜索树与双向链表][Link 1]

### 解法一：存储在vector中进行链接 ###

*  思路：

> 对树进行中序遍历，将结点存储在vector容器中，然后从左向右进行链接，返回容器中第一个节点

*  时间复杂度：
 *  空间复杂度：O( N )
 *  代码

/* // Definition for a Node. class Node { public: int val; Node* left; Node* right; Node() {} Node(int _val) { val = _val; left = NULL; right = NULL; } Node(int _val, Node* _left, Node* _right) { val = _val; left = _left; right = _right; } }; */
    class Solution { 
    public:
        Node* treeToDoublyList(Node* root) { 
            if(root == NULL) return NULL;
            vector<Node*> v;
            InorderTraversal(v,root);
            for(int i = 0; i < v.size(); i++)
            { 
                if(i != v.size()-1)
                    v[i]->right = v[i+1];
                else
                    v[i]->right = v[0];
                if(i != 0)
                    v[i]->left = v[i-1];
                else
                    v[i]->left = v[v.size()-1];
            }
            return v[0];
        }
    private:
        void InorderTraversal(vector<Node*>& v, Node* root)
        { 
            if(root == NULL)
                return ;
            else
            { 
                InorderTraversal(v,root->left);
                v.push_back(root);
                InorderTraversal(v,root->right);
            }
        }
    };
    i]->right = v[0];
                if(i != 0)
                    v[i]->left = v[i-1];
                else
                    v[i]->left = v[v.size()-1];
            }
            return v[0];
        }
    private:
        void InorderTraversal(vector<Node*>& v, Node* root)
        { 
            if(root == NULL)
                return ;
            else
            { 
                InorderTraversal(v,root->left);
                v.push_back(root);
                InorderTraversal(v,root->right);
            }
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNzAyMg_size_16_color_FFFFFF_t_70]: /images/20221119/da9f7f04113f4b2b86a307c0c14893b0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNzAyMg_size_16_color_FFFFFF_t_70 1]: /images/20221119/0844c7e4c5da424bad6e184e36614468.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNzAyMg_size_16_color_FFFFFF_t_70 2]: /images/20221119/aef768dc23594906b891407b2807e705.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNzAyMg_size_16_color_FFFFFF_t_70 3]: /images/20221119/862af7c9177f462bb70b1b240f9416d2.png
[Link 1]: https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/