笔触狂放9

这个屌丝很懒，什么也没留下！

热门标签

【数据结构】二叉搜索树_给定一串正整数,代表所要构建的二叉搜索树,计算并返回二叉搜索树的平均查找长度结

作者：笔触狂放9 | 2024-05-04 06:21:18

踩

给定一串正整数,代表所要构建的二叉搜索树,计算并返回二叉搜索树的平均查找长度结

二叉搜索树又称二叉排序树，是一种key搜索模型，它或是一棵空树，亦或是具有以下性质的二叉树:

若根的左子树不为空，则左子树上所有节点的值都小于根节点的值；
若根的右子树不为空，则右子树上所有节点的值都大于根节点的值；
根的左右子树也分别为二叉搜索树。

由以下数据构建出一棵二叉搜索树：

int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};

将得到形如下图的一棵二叉搜索树：

若中序遍历输出这棵二叉搜索树，将得到这样一个序列：

    1    3    4    6    7    8    10    13    14

而这个序列恰好是升序的。这也是二叉搜索树的意义所在，对于一个有序数组来说，插入和删除的效率低（因为它是基于二分查找实现的），而一棵二叉搜索树的查找、排序、插入和删除效率较优良。

本篇博客将通过C++来模拟实现二叉搜索树的重要功能，旨在让读者更好地理解它的功能及其原理。

• 二叉搜索树的模拟实现

0 - 创建一棵二叉搜索树


    //树的节点
    template<class K>
	struct BSTreeNode
	{
		BSTreeNode<K>* _left;    //左子树
		BSTreeNode<K>* _right;   //右子树
		K _key;                  //节点的值
 
		BSTreeNode(const K& key)    //通过初始化列表来构造一个树节点  
			:_left(nullptr)
			, _right(nullptr)
			, _key(key)
		{}
	};
    
    //二叉搜索树
	template<class K>
	class BSTree
	{
		typedef BSTreeNode<K> Node;
	public:
		BSTree()              //通过初始化列表来构造一棵二叉搜索树       
			:_root(nullptr)
		{}
		BSTree<K>& operator=(BSTree<K> t)    //赋值重置
		{
			swap(_root, t._root);
			return *this;
		}
	private:
		Node* _root;
	};

1 - 查找

从根开始，将目标值与节点挨个比较查找，节点的值比根大就去根的右子树里查找，比根小就去左子树里查找。如果走到了空节点也还没找到，就说明这个值在树中不存在。这种方式最多查找树的高度次。


		bool Find(const K& key)
		{
			Node* cur = _root; //从根节点（当前节点）开始找
			while (cur)        //节点不为空就继续找
			{
				if (cur->_key < key)         //比根（当前节点）大走右子树
				{
					cur = cur->_right;
				}
				else if (cur->_key > key)    //比根（当前节点）小走左子树
				{
					cur = cur->_left;
				}
				else
				{
					return true;    //找到了就返回true
				}
			}
			return false;
		}

也可以通过递归的方式来实现查找。


//ps：在类内部写递归，需要先对递归进行一层封装
 
    //public:	
		bool FindR(const K& key)
		{
			return _FindR(_root, key);
		}
    //private:
		bool _FindR(Node* root, const K& key)
		{
			if (root == nullptr)
				return false;
			if (root->_key < key)
			{
				return _FindR(root->_right, key);
			}
			else if (root->_key > key)
			{
				return _FindR(root->_left, key);
			}
			else
			{
				return true;
			}
		}

2 - 插入

利用插入的值创建一个新的树节点。树为空，就直接将新节点赋给根节点的指针；树不为空，就按二叉搜索树的性质查找到合适的插入位置，在合适位置插入新节点。


		bool Insert(const K& key)
		{
            //树为空，就直接将新节点赋给根节点的指针
			if (_root == nullptr)
			{
				_root = new Node(key);
				return true;
			}
            //树不为空，就按二叉搜索树的性质查找到合适的插入位置
			Node* parent = nullptr;    //父节点，用于记录当前节点的位置
			Node* cur = _root;         //子节点，用于记录下一个要查找的节点
			while (cur)
			{
				if (cur->_key < key)   //比根大就去右子树找
				{
					parent = cur;      //将子节点更新为新的父节点
					cur = cur->_right; //子节点向右子树走
				}
				else if (cur->_key > key)    //比根小就去左子树找
				{
					parent = cur;            //将子节点更新为新的父节点
					cur = cur->_left;        //子节点向左子树走
				}
				else
				{
					return false;    //要插入的值已在树中就不插入了。在二叉搜索树中，每个值是不重复的
				}
			}
            //最后，父节点记录了合适的插入位置
            //在合适位置插入新节点
			cur = new Node(key);
			if (parent->_key < key)
			{
				parent->_right = cur;    //比合适位置的值大就插入在右边
			}
			else
			{
				parent->_left = cur;     //比合适位置的值小就插入在左边
			}
			return true;
		}

同样，也可以通过递归的方式来实现插入。


    //public:
		bool InsertR(const K& key)
		{
			return _InsertR(_root, key);
		}
    //private:
	    bool _InsertR(Node*& root, const K& key)
		{
			if (root == nullptr)
			{
				root = new Node(key);
				return true;
			}
			if (root->_key < key)
			{
				return _InsertR(root->_right, key);
			}
			else if (root->_key > key)
			{
				return _InsertR(root->_left, key);
			}
			else
			{
				return false;
			}
		}

3 - 删除

首先查找验证元素是否在树中，若不存在，则返回false；若存在，就删除目标节点。

删除节点的确容易，直接释放节点即可，但删除的同时还应维护二叉搜索树原本的结构特性，于是，要删除的节点存在树中时，删除的处理就可能存在以下情况：

要删除的节点没有孩子节点；
要删除的节点只有左孩子；
要删除的节点只有右孩子；
要删除的节点既有左孩子又有右孩子。

而编写时，情况1其实可以与情况2或者情况3合并，故节点删除的真正过程为：

若要删除的节点没有左孩子，就将它的右孩子给父节点，然后将它直接删除；
若要删除的节点没有右孩子，就将它的左孩子给父节点，然后将它直接删除；
若要删除的节点既有左孩子又有右孩子，就先用替换法做删除处理，然后再将它删除。

【Tips】替换法：用要删除节点的左子树的最大节点或右子树的最小节点（即左子树的最右节点或右子树的最左节点）替换要删除的节点。要删除的节点的左子树的最大节点或右子树的最小节点，它们的值是最接近要删除节点的，用它们中任意一个代替要删除的节点，不会破坏二叉搜索树原本的结构特性。所以，找不论左子树的最右节点，还是右子树的最左节点来替代要删除节点，均可。


 
		bool Erase(const K& key)
		{
			Node* parent = nullptr;   //父节点/当前节点
			Node* cur = _root;        //子节点/当前节点
			//先找到要删除的节点
			while (cur)
			{
				if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else // 找到了要删除的节点，此时parent储存了要删除节点的父节点，cur储存了要删除的节点
				{
					// 要删除的节点没有左孩子
					if (cur->_left == nullptr)
					{
                        //要删除的节点为根节点
						if (cur == _root)
						{
							_root = cur->_right;//因为cur没有左孩子，所以将cur的右孩子置为新的根节点
						}
                        //不为根节点
						else
						{   
                            //如果cur是parent的右孩子，就把cur的右孩子置为parent新的右孩子（因为cur没有左孩子）
							if (parent->_right == cur)
							{
								parent->_right = cur->_right;
							}
                            //但如果cur是parent的左孩子，就把cur的右孩子置为parent新的左孩子
							else
							{
								parent->_left = cur->_right;
							}
						}
					}
                    // 要删除的节点没有右孩子
					else if (cur->_right == nullptr)
					{
                        //当前节点为根节点
						if (cur == _root)
						{
							_root = cur->_left;//因为cur没有右孩子，所以将cur的左孩子置为新的根节点
						}
                        //不为根节点
						else
						{    
                            //如果cur是parent的右孩子，就把cur的左孩子置为parent新的右孩子（因为cur没有右孩子）
							if (parent->_right == cur)
							{
								parent->_right = cur->_left;
							}
                            //但如果cur是parent的左孩子，就把cur的右孩子置为parent新的左孩子
							else
							{
								parent->_left = cur->_left;
							}
						}
					}
                    // 要删除的节点既有左孩子又有右孩子
					else
					{
						//那就先找到替代节点（即左子树的最右节点或右子树的最左节点）					
						parent = cur;              //更新parent为要删除的节点
						Node* leftMax = cur->_left;//定义leftMax初始为cur的左孩子
                        //ps：要删除节点的左子树的最右节点或右子树的最左节点，它们的值是最接近要删除节点的，用它们中任意一个代替要删除的节点，不会破坏二叉搜索树原本的结构特性
                        //所以，找不论左子树的最右节点，还是右子树的最左节点来替代要删除节点，均可
 
                        //这里是找左子树的最右节点
						while (leftMax->_right)
						{
							parent = leftMax;
							leftMax = leftMax->_right;
						}
                        //找到后，交换替代节点和要删除节点的值
						swap(cur->_key, leftMax->_key);
 
		                //然后，做节点的删除处理，
                        //经过上面找左子树的最右节点的代码逻辑，parent当前是leftMax的父节点
                        //如果leftMax是parent的左孩子，就把leftMax的左孩子置为parent新的左孩子
                        //如果leftMax是parent的右孩子，就把leftMax的左孩子置为parent新的右孩子
                        //ps：leftMax已经是左子树的最右节点了，理论上它不会再有右孩子，但可能有左孩子。就算没有左孩子（即leftMax->_left==NULL），也不妨碍下面的代码重置parent的新孩子
						if (parent->_left == leftMax)
						{
							parent->_left = leftMax->_left;
						}
						else
						{
							parent->_right = leftMax->_left;
						}
                        //然后让cur去指向替代节点
						cur = leftMax;
						
					}
                    //做完删除的处理后，最终释放cur
					delete cur;
					return true;
				}
			}
		    //树为空或树中没有要删除的值，就返回false
			return false;
		}

同样，也可以通过递归的方式来实现删除。


    //public:
		bool EraseR(const K& key)
		{
			return _EraseR(_root, key);
		}
    //private:
		bool _EraseR(Node*& root, const K& key)
		{
			if (root == nullptr)
				return false;
			if (root->_key < key)
			{
				return _EraseR(root->_right, key);
			}
			else if (root->_key > key)
			{
				return _EraseR(root->_left, key);
			}
			else
			{
				Node* del = root;
				//左为空
				if (root->_left == nullptr)
				{
					root = root->_right;
				}
				//右为空
				else if (root->_right == nullptr)
				{
					root = root->_left;
				}
				//左右不空
				else
				{
					Node* leftMax = root->_left;
					while (leftMax->_right)
					{
						leftMax = leftMax->_right;
					}
 
					swap(root->_key, leftMax->_key);
 
					return _EraseR(root->_left, key);
				}
 
				delete del;
				return true;
			}
		}

4 - 拷贝

将一棵二叉搜索树拷贝一份给另一棵二叉搜索树，不仅仅是将树中的值进行拷贝，还要将树的结构（即节点指针）拷贝下来，所以这个过程应是深拷贝。

可以通过递归结合前序遍历的方式来实现这个深拷贝，并且可以通过调用拷贝构造来进行深拷贝。


    //public:
		BSTree(const BSTree<K>& t)
		{
			_root = Copy(t._root);
		}
	//private:
		Node* Copy(Node* root)
		{
			if (root == nullptr)
				return nullptr;
 
			Node* copyroot = new Node(root->_key);
			copyroot->_left = Copy(root->_left);
			copyroot->_right = Copy(root->_right);
			return copyroot;
		}

5 - 销毁

销毁一棵二叉搜索树，需要将其所有的节点释放。这个过程可以通过递归结合后序遍历的方式来实现，并且可以通过调用析构来销毁一棵二叉搜索树。


    //public:
		~BSTree()
		{
			Destroy(_root);
		}
    //private:
		void Destroy(Node*& root)
		{
			if (root == nullptr)
				return;
 
			Destroy(root->_left);
			Destroy(root->_right);
			delete root;
			root = nullptr;
		}

6 - 完整代码


//搜索二叉树 - 根的左边比根小，右边比根大
//key搜索模型
namespace key
{
	template<class K>
	struct BSTreeNode
	{
		BSTreeNode<K>* _left;
		BSTreeNode<K>* _right;
		K _key;
 
		BSTreeNode(const K& key)
			:_left(nullptr)
			, _right(nullptr)
			, _key(key)
		{}
	};
 
	template<class K>
	class BSTree
	{
		typedef BSTreeNode<K> Node;
	public:
		BSTree()
			:_root(nullptr)
		{}
		~BSTree()
		{
			Destroy(_root);
		}
		BSTree(const BSTree<K>& t)
		{
			_root = Copy(t._root);
		}
 
		BSTree<K>& operator=(BSTree<K> t)
		{
			swap(_root, t._root);
			return *this;
		}
 
		//bool Insert(const K& key)
		//{
		//	if (_root == nullptr)
		//	{
		//		_root = new Node(key);
		//		return true;
		//	}
		//	Node* parent = nullptr;
		//	Node* cur = _root;
		//	while (cur)
		//	{
		//		if (cur->_key < key)
		//		{
		//			parent = cur;
		//			cur = cur->_right;
		//		}
		//		else if (cur->_key > key)
		//		{
		//			parent = cur;
		//			cur = cur->_left;
		//		}
		//		else
		//		{
		//			return false;
		//		}
		//	}
		//	cur = new Node(key);
		//	if (parent->_key < key)
		//	{
		//		parent->_right = cur;
		//	}
		//	else
		//	{
		//		parent->_left = cur;
		//	}
		//	return true;
		//}
 
		bool InsertR(const K& key)
		{
			return _InsertR(_root, key);
		}
 
		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}
 
 
		/*bool Find(const K& key)
		{
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key < key)
				{
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					cur = cur->_left;
				}
				else
				{
					return true;
				}
			}
			return false;
		}*/
 
		bool FindR(const K& key)
		{
			return _FindR(_root, key);
		}
 
		//bool Erase(const K& key)
		//{
		//	//替换法：左子树的最大节点或右子树的最小节点（即左子树的最右节点或右子树的最左节点）
		//	Node* parent = nullptr;
		//	Node* cur = _root;
		//	//先找key
		//	while (cur)
		//	{
		//		if (cur->_key < key)
		//		{
		//			parent = cur;
		//			cur = cur->_right;
		//		}
		//		else if (cur->_key > key)
		//		{
		//			parent = cur;
		//			cur = cur->_left;
		//		}
		//		else // 找到了
		//		{
		//			// 左为空
		//			if (cur->_left == nullptr)
		//			{
		//				if (cur == _root)
		//				{
		//					_root = cur->_right;
		//				}
		//				else
		//				{
		//					if (parent->_right == cur)
		//					{
		//						parent->_right = cur->_right;
		//					}
		//					else
		//					{
		//						parent->_left = cur->_right;
		//					}
		//				}
		//			}// 右为空
		//			else if (cur->_right == nullptr)
		//			{
		//				if (cur == _root)
		//				{
		//					_root = cur->_left;
		//				}
		//				else
		//				{
		//					if (parent->_right == cur)
		//					{
		//						parent->_right = cur->_left;
		//					}
		//					else
		//					{
		//						parent->_left = cur->_left;
		//					}
		//				}
		//			} // 左右都不为空
		//			else
		//			{
		//				//找替代节点
		//			
		//				Node* parent = cur;
		//				Node* leftMax = cur->_left;
		//				while (leftMax->_right)
		//				{
		//					parent = leftMax;
		//					leftMax = leftMax->_right;
		//				}
		//				swap(cur->_key, leftMax->_key);
		//
		//				if (parent->_left == leftMax)
		//				{
		//					parent->_left = leftMax->_left;
		//				}
		//				else
		//				{
		//					parent->_right = leftMax->_left;
		//				}
		//				cur = leftMax;
		//				
		//			}
		//			delete cur;
		//			return true;
		//		}
		//	}
		//
		//	return false;
		//}
 
		bool EraseR(const K& key)
		{
			return _EraseR(_root, key);
		}
 
	private:
		Node* Copy(Node* root)
		{
			if (root == nullptr)
				return nullptr;
 
			Node* copyroot = new Node(root->_key);
			copyroot->_left = Copy(root->_left);
			copyroot->_right = Copy(root->_right);
			return copyroot;
		}
 
		void Destroy(Node*& root)
		{
			if (root == nullptr)
				return;
 
			Destroy(root->_left);
			Destroy(root->_right);
			delete root;
			root = nullptr;
		}
 
		bool _InsertR(Node*& root, const K& key)
		{
			if (root == nullptr)
			{
				root = new Node(key);
				return true;
			}
			if (root->_key < key)
			{
				return _InsertR(root->_right, key);
			}
			else if (root->_key > key)
			{
				return _InsertR(root->_left, key);
			}
			else
			{
				return false;
			}
		}
 
		void _InOrder(Node* root)
		{
			if (root == NULL)
			{
				return;
			}
			_InOrder(root->_left);
			cout << root->_key << " ";
			_InOrder(root->_right);
		}
 
		bool _FindR(Node* root, const K& key)
		{
			if (root == nullptr)
				return false;
			if (root->_key < key)
			{
				return _FindR(root->_right, key);
			}
			else if (root->_key > key)
			{
				return _FindR(root->_left, key);
			}
			else
			{
				return true;
			}
		}
 
		bool _EraseR(Node*& root, const K& key)
		{
			if (root == nullptr)
				return false;
			if (root->_key < key)
			{
				return _EraseR(root->_right, key);
			}
			else if (root->_key > key)
			{
				return _EraseR(root->_left, key);
			}
			else
			{
				Node* del = root;
				//左为空
				if (root->_left == nullptr)
				{
					root = root->_right;
				}
				//右为空
				else if (root->_right == nullptr)
				{
					root = root->_left;
				}
				//左右不空
				else
				{
					Node* leftMax = root->_left;
					while (leftMax->_right)
					{
						leftMax = leftMax->_right;
					}
 
					swap(root->_key, leftMax->_key);
 
					return _EraseR(root->_left, key);
				}
 
				delete del;
				return true;
			}
		}
 
	private:
		Node* _root;
	};
 
	void TestBSTree1()
	{
		int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
		BSTree<int> t;
		for (auto e : a)
		{
			t.InsertR(e);
		}
 
		t.InOrder();
 
		t.EraseR(4);
		t.InOrder();
		t.EraseR(6);
		t.InOrder();
		t.EraseR(7);
		t.InOrder();
		t.EraseR(3);
		t.InOrder();
		for (auto e : a)
		{
			t.EraseR(e);
		}
		t.InOrder();
	}
 
	void TestBSTree2()
	{
		int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
		BSTree<int> t;
		for (auto e : a)
		{
			t.InsertR(e);
		}
 
		BSTree<int> t1(t);
 
		t.InOrder();
		t1.InOrder();
	}
 
}

补、两种搜索模型

• K模型

K模型是一种只有key作为关键码（即需要搜索到的值），结构中只需要存储key的搜索模型，其模型本质是“在不在”。

模型的应用情景例如，输入法自动检查在键盘上输入的一个单词的拼写是否正确，其方式之一是将输入的单词与词库中的单词进行匹配，若匹配成功，则说明拼写正确，若在词库中匹配不到，则说明拼写错误。

最普通的二叉搜索树就是一个K模型，即每个树节点只存储一个数据，树节点的实际意义就是所存储的数据的实际意义。

• KV模型

在KV模型中，每一个关键码key都有与之一一对应的值value，也就是说，模型中所存的其实是<key，value>的键值对。其模型本质是key和value的映射关系。

模型的应用情景例如，在英汉词典中，英文与中文的对应关系，通过英文单词可以快速找到与之对应的中文，英文单词与其对应的中文就构成一种<英文，中文>的键值对。

二叉搜索树也可以改造为一个KV模型，即每个树节点存储了一个<key，value>的键值对，树节点的实际意义更加丰富多元。


//key-value搜索模型
namespace key_value
{
	template<class K, class V>
	struct BSTreeNode
	{
		BSTreeNode<K, V>* _left;
		BSTreeNode<K, V>* _right;
		K _key;
		V _value;
 
		BSTreeNode(const K& key, const V& value)
			:_left(nullptr)
			, _right(nullptr)
			, _key(key)
			, _value(value)
		{}
	};
 
	template<class K, class V>
	class BSTree
	{
		typedef BSTreeNode<K, V> Node;
	public:
		BSTree()
			:_root(nullptr)
		{}
 
		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}
 
		Node* FindR(const K& key)
		{
			return _FindR(_root, key);
		}
 
		bool InsertR(const K& key, const V& value)
		{
			return _InsertR(_root, key, value);
		}
 
		bool EraseR(const K& key)
		{
			return _EraseR(_root, key);
		}
 
	private:
		bool _EraseR(Node*& root, const K& key)
		{
			if (root == nullptr)
				return false;
 
			if (root->_key < key)
			{
				return _EraseR(root->_right, key);
			}
			else if (root->_key > key)
			{
				return _EraseR(root->_left, key);
			}
			else
			{
				Node* del = root;
 
				// 1、左为空
				// 2、右为空
				// 3、左右都不为空
				if (root->_left == nullptr)
				{
					root = root->_right;
				}
				else if (root->_right == nullptr)
				{
					root = root->_left;
				}
				else
				{
					Node* leftMax = root->_left;
					while (leftMax->_right)
					{
						leftMax = leftMax->_right;
					}
 
					swap(root->_key, leftMax->_key);
 
					return _EraseR(root->_left, key);
				}
 
				delete del;
				return true;
			}
		}
 
		bool _InsertR(Node*& root, const K& key, const V& value)
		{
			if (root == nullptr)
			{
				root = new Node(key, value);
				return true;
			}
 
			if (root->_key < key)
			{
				return _InsertR(root->_right, key, value);
			}
			else if (root->_key > key)
			{
				return _InsertR(root->_left, key, value);
			}
			else
			{
				return false;
			}
		}
 
		Node* _FindR(Node* root, const K& key)
		{
			if (root == nullptr)
				return nullptr;
 
			if (root->_key < key)
			{
				return _FindR(root->_right, key);
			}
			else if (root->_key > key)
			{
				return _FindR(root->_left, key);
			}
			else
			{
				return root;
			}
		}
 
		void _InOrder(Node* root)
		{
			if (root == NULL)
			{
				return;
			}
 
			_InOrder(root->_left);
			cout << root->_key << ":" << root->_value << endl;
			_InOrder(root->_right);
		}
	private:
		Node* _root;
	};
 
	void TestBSTree1()
	{
		//BSTree<string, Date> carTree;
 
		BSTree<string, string> dict;
		dict.InsertR("insert", "插入");
		dict.InsertR("sort", "排序");
		dict.InsertR("right", "右边");
		dict.InsertR("date", "日期");
 
		string str;
		while (cin >> str)
		{
			BSTreeNode<string, string>* ret = dict.FindR(str);
			if (ret)
			{
				cout << ret->_value << endl;
			}
			else
			{
				cout << "无此单词" << endl;
			}
		}
	}
 
	void TestBSTree2()
	{
		// 统计水果出现的次数
		string arr[] = { "西瓜", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
		BSTree<string, int> countTree;
		for (auto& str : arr)
		{
			auto ret = countTree.FindR(str);
			if (ret == nullptr)
			{
				countTree.InsertR(str, 1);
			}
			else
			{
				ret->_value++;
			}
		}
 
		countTree.InOrder();
	}
}

补、二叉搜索树的性能问题

二叉搜索树中涉及树节点的的主要操作都必须做查找，所以查找的效率就基本代表了二叉搜索树中各操作的性能。

设一棵有n个节点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度即为节点在二叉搜索树的深度的函数，节点越深，查找得就越久。而对于同一个关键码key的集合，如果每个关键码key插入树的次序不同，就可能得到不同结构的二叉搜索树：

最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为logN。但是最坏情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：N^2。所以，当二叉搜索树退化成单支树，它就失去了原本的性能优势。

那么，是否存在一种可能，不论以什么次序插入关键码，都使二叉搜索树的性能达到最优？这个问题可以由另外两种树结构——AVL树（详见【数据结构】平衡树之AVL树）和红黑树（详见【数据结构】平衡树之红黑树）来解决。

补、二叉搜索树的相关OJ

根据二叉树创建字符串


class Solution {
public:
    string tree2str(TreeNode* root) {
        if (root == nullptr)
            return "";
        string str = to_string(root->val);
 
        if (root->left || root->right)
        {
            str += '(';
            str += tree2str(root->left);
            str += ')';
        }
        if (root->right)
        {
            str += '(';
            str += tree2str(root->right);
            str += ')';
 
        }
        return str;
    }
};

二叉树的最近公共祖先


 
// 法1.搜索二叉树倒着走-> 链表相交
//  a、三叉链 - o（N）
//  b、普通树 - o（N）
// 法2.一个在左一个在右，此个即公共祖先
//  a、普通树暴力求解 - o（N^2）
//  b、搜索二叉树 - o（N）
// 
// 搜索二叉树
class Solution {
public:
    bool Find(TreeNode* tree, TreeNode* x)
    {
        if (tree == nullptr)
            return false;
        return tree == x
            || Find(tree->left, x)
            || Find(tree->right, x);
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr)
            return nullptr;
        if (root == p || root == q)
            return root;
 
        bool pInLeft, pInRight, qInLeft, qInRight;
        pInLeft = Find(root->left, p);
        pInRight = !pInLeft;
        qInLeft = Find(root->left, q);
        qInRight = !qInLeft;
 
        if (pInLeft && qInLeft)
        {
            return lowestCommonAncestor(root->left, p, q);
        }
        else if (pInRight && qInRight)
        {
            return lowestCommonAncestor(root->right, p, q);
        }
        else
        {
            return root;
        }
    }
};


//前序遍历，非所要数据则分别入栈，遇到所要数据则停止入栈
//最终比较两个栈的数据，不相同则删除栈顶，相同即公共祖先
class Solution {
    bool FindPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& path)
    {
        if (root == nullptr)
        {
            return false;
        }
        path.push(root);
        if (root == x)
        {
            return true;
        }
        if (FindPath(root->left, x, path))
            return true;
        if (FindPath(root->right, x, path))
            return true;
        path.pop();
        return false;
 
    }
 
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        stack<TreeNode*> pPath,qPath;
        FindPath(root, p, pPath);
        FindPath(root, q, qPath);
        while (pPath.size() > qPath.size())
        {
            pPath.pop();
        }
        while (pPath.size() < qPath.size())
        {
            qPath.pop();
        }
        while (pPath.top() != qPath.top())
        {
            pPath.pop();
            qPath.pop();
        }
        return pPath.top();    
    }
};

二叉搜索树与双向链表


//左路节点->左路节点的右子树->左路节点
//cur指向一个节点意味着访问另一棵树的开始
//栈里面的节点意味着压迫访问它的右子树
class Solution {
public:
    void InOrder(TreeNode* cur,TreeNode*& prev)
    {
        if (cur == nullptr)
            return;
        InOrder(cur->left,prev);
        //当前left指向前一个节点
        cur->left = prev;
        //前一个right指向当前节点
        if(prev)
            prev->right = cur;
 
        prev = cur;
        
        InOrder(cur->right,prev);
    }
    TreeNode* Convert(TreeNode* pRootOfTree) {
        TreeNode* prev = nullptr;
        InOrder(pRootOfTree, prev);
 
        TreeNode* head = pRootOfTree;
        while (head && head->left)
        {
            head = head->left;
        }
        return head;
    }
};

从前序与中序遍历序列构造二叉树


class Solution {
public:
    TreeNode* _build(vector<int>& preorder, vector<int>& inorder,
        int& prei, int inbegin, int inend)
    {
        if (inbegin > inend)
            return nullptr;
 
        TreeNode* root = new TreeNode(preorder[prei]);
        int rooti = inbegin;
        while (rooti <= inend)
        {
            if (preorder[prei] == inorder[rooti])
                break;
            ++rooti;
        }
        //[inbegin,rooti-1] rooti [rooti+1,inend]
        ++prei;
        root->left = _build(preorder, inorder, prei, inbegin, rooti - 1);
        root->right= _build(preorder, inorder, prei, rooti + 1,inend);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int i = 0;
       return _build(preorder,inorder, i, 0, inorder.size() - 1);
        
    }
};

二叉树的前序遍历，非递归迭代实现


class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* cur = root;
        vector<int> v;
        //访问一棵树的开始
        //1.访问左路节点，左路节点入栈，后续依次访问左路节点的右子树
        while (cur || !st.empty())
        {
            while(cur)
            {
                v.push_back(cur->val);
                st.push(cur);
                cur = cur->left;
            }
 
            //依次访问左路节点的右子树
            TreeNode* top = st.top();
            st.pop();
 
            //子问题的方式访问右子树
            cur = top->right;
        }
        return v;
    } 
};

二叉树中序遍历，非递归迭代实现


//从栈里面取到一个节点意味着这个节点的左子树已经访问完了
//1、左路节点入栈
//2、访问左路节点及左路节点的右子树
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* cur = root;
        vector<int> v;
        //访问一棵树的开始
        //1.访问左路节点，左路节点入栈，后续依次访问左路节点的右子树
        while (cur || !st.empty())
        {
            while (cur)
            {
                st.push(cur);
                cur = cur->left;
            }
            //依次访问左路节点及其右子树
            TreeNode* top = st.top();
            st.pop();
            v.push_back(top->val);
            //子问题的方式访问右子树
            cur = top->right;
        }
        return v;
    }
};

二叉树的后序遍历，非递归迭代实现


class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* prev = nullptr;
        TreeNode* cur = root;
        vector<int> v;        
        while (cur || !st.empty())
        {
            while (cur)
            {
                st.push(cur);
                cur = cur->left;
            }
 
            TreeNode* top = st.top();
            //一个节点右子树为空或上一个访问的节点是右子树的根
            //那么都说明相当于右树访问过了可以访问当前根节点
            
            if (top->right == nullptr || top->right == prev)
            {
                prev = top;
                v.push_back(top->val);
                st.pop();
            }
            else
            {
                cur = top->right;
            }           
        }
        return v;
    }
};

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/533201