二叉树进阶

目录

前言

二叉搜索树(非递归)

二叉搜索树(递归)

二叉树的性能分析

Key模型与Key-Value模型

全部代码

---

前言

二叉搜索树又称二叉排序树，它或者是一棵空树，因为它的左子树的值<根的值<右子树的值(左右子树不为空时)，左右子树也是二叉搜索树，所以它的中序遍历则是升序

节点封装如下

注意：为了避免存储重复数，以及找不到要删除的数的节点，插入与删除的返回类型采用布尔类型

二叉搜索树具有排序+去重的作用

二叉搜素树的实现(非递归)

插入

如果是一颗空树，则直接插入即可

要插入节点，需要找到前驱节点，所以一般都需要遍历这颗树，就需要两个指针parent和cur，类似于单链表插入节点

新插入节点的值与二叉树中某个节点的值一致时，则直接返回，即插入失败

找到前驱节点之后，再判断节点值的大小，来确定插入左边还是右边，然后返回即可

 

删除

先查找要删除的元素

找到之后，要删除的元素只有右节点，或者左右节点均为空时，如果只有根节点，就删除根节点，否则就删除找到的节点，然后让它的父亲指向它的右孩子

找到之后，要删除的元素只有左节点，或者左右节点均为空时，如果只有根节点，就删除根节点，否则就删除找到的节点，然后让它的父亲指向它的左孩子

 

找到之后，左右孩子都存在时，先找到右子树的最左节点，然后把找到节点的值赋值给要删除的节点，如果找到的最左节点，有右孩子时，则让它的父亲指向它的右孩子，然后删除刚刚找到的左节点或右节点

二叉搜索树的实现(递归)

因为节点指针是私有的，而递归写法的插入与删除都要用到根节点，所以需要再套一层

 

插入

递归和非递归类似，都是先找到其前驱节点，然后再连接即可，比如下图，开始值为3的节点的右孩子是nullptr，然后再展开后，将指向nullptr的指针指向值为5的节点，则值为3的节点的右孩子是值为5的节点了

删除

和非递归类似，都是先找到要删除的节点，如果要删除的节点为不存在，则删除失败

要删除的节点的右孩子为nullptr时，让它的左孩子变为它的父节点的左孩子即可

 要删除的节点的左孩子为nullptr时，让它的右孩子变为它的父节点的左孩子即可

要删除的节点既有左孩子又有右孩子时，先将要删除的节点的值与根节点的右子树的最左节点的值交换，然后遍历根节点的右子树来删除最左节点

二叉树的性能分析

最优情况：当二叉搜索树是完全二叉树时，其平均比较次数为log2 n

最差情况：当二叉搜索树退化为单支树时，其平均比较次数为n/2

解决方法

将二叉树进一步优化，使其成为平衡二叉树，有AVL树或红黑树两种

Key模型与Key-Value模型

Key模型

门禁系统，存储该栋楼所有同学学号或小区所有业主的车牌号，有就让进入，没有就无法进入

Key—Value模型

字典,通过一个单词的英文，从而知道它的中文意思

Key—Value模型则需要存储两个值，一个是Key,另一个则是Value

 

全部代码

//二叉搜索树
 
#pragma once
#include<iostream>
using namespace std;
 
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>
struct BSTree
{
	typedef BSTreeNode<K> Node;
public:
	BSTree():_root(nullptr)
	{}
 
	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 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 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
			{
				//找到，准备开始删除
				if (cur->_left == nullptr)
				{
					if (parent == nullptr)
					{
						_root = cur->_right;
					}
					else
					{
						if (parent->_left == cur)
							parent->_left = cur->_right;
						else
							parent->_right = cur->_right;
					}
					delete cur;
				}
				else if (cur->_right == nullptr)
				{
					if (parent == nullptr)
					{
						_root = cur->_left;
					}
					else
					{
						if (parent->_left == cur)
							parent->_left = cur->_left;
						else
							parent->_right = cur->_left;
					}
					delete cur;
				}
				else
				{
					Node* minParent = cur;
					Node* min = cur->_right;
					while (min->_left)
					{
						minParent = min;
						min = min->_left;
					}
					cur->_key = min->_key;
					if (minParent->_left == min)
						minParent->_left = min->_right;
					else
						minParent->_right = min->_right;
					delete min;
				}
				return true;
			}
		}
		return false;
	}
 
	bool InsertR(const K& key)
	{
		return _InsertR(_root, key);
	}
 
	Node* FindR(const K& key)
	{
		return _FindR(_root, key);
	}
 
	Node* EraseR(const K& key)
	{
		return _Erase(_root, key);
	}
 
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
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* min = root->_right;
				while (min->_left)
				{
					min = min->_left;
				}
				swap(min->_key, root->_key);
				//递归到右子树去删除
				return _EraseR(root->_right, key);
			}
			delete del;
			return true;
		}
	}
 
	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;
	}
	
	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 == nullptr)
		{
			return;
		}
		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);
	}
private:
	Node* _root;
};
 
void TestBSTree()
{
	BSTree<int> t;
	int a[] = { 5,3,4,1,7,8,2,6,0,9,5,5 };
	for (auto e : a)
	{
		t.InsertR(e);
	}
	//排序+去重
	t.InOrder();
 
	t.Erase(7);
	t.InOrder();
 
	t.Erase(5);
	t.InOrder();
 
	t.Erase(0);
	t.InOrder();
 
	t.Erase(1);
	t.InOrder();
 
	for (auto e : a)
	{
		t.Erase(e);
		t.InOrder();
	}
	t.InOrder();
}
 
 
namespace KV
{
	template<class K,class V>
	struct BSTreeNode
	{
		BSTreeNode<K,V>* _left;
		BSTreeNode<K,V>* _right;
		K _key;
		V _value;
 
		//pair<K,V> _kv;
 
		BSTreeNode(const K& key,const V& value) :_left(nullptr), _right(nullptr), _key(key),_value(value)
		{}
	};
 
	template<class K,class V>
	struct BSTree
	{
		typedef BSTreeNode<K, V> Node;
	public:
		BSTree() :_root(nullptr)
		{}
 
		bool Insert(const K& key, const V& value)
		{
			if (_root == nullptr)
			{
				_root = new Node(key, value);
				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, value);
			if (parent->_key < key)
			{
				parent->_right = cur;
			}
			else
			{
				parent->_left = cur;
			}
			return true;
		}
 
		Node* 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 cur;
				}
			}
			return nullptr;
		}
 
		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
				{
					//找到，准备开始删除
					if (cur->_left == nullptr)
					{
						if (parent == nullptr)
						{
							_root = cur->_right;
						}
						else
						{
							if (parent->_left == cur)
								parent->_left = cur->_right;
							else
								parent->_right = cur->_right;
						}
						delete cur;
					}
					else if (cur->_right == nullptr)
					{
						if (parent == nullptr)
						{
							_root = cur->_left;
						}
						else
						{
							if (parent->_left == cur)
								parent->_left = cur->_left;
							else
								parent->_right = cur->_left;
						}
						delete cur;
					}
					else
					{
						Node* minParent = cur;
						Node* min = cur->_right;
						while (min->_left)
						{
							minParent = min;
							min = min->_left;
						}
						cur->_key = min->_key;
						if (minParent->_left == min)
							minParent->_left = min->_right;
						else
							minParent->_right = min->_right;
						delete min;
					}
					return true;
				}
			}
			return false;
		}
 
		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}
	private:
		void _InOrder(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}
			_InOrder(root->_left);
			cout << root->_key << ":" << root->_value << endl;
			_InOrder(root->_right);
		}
		Node* _root;
	};
 
	void TestBstree1()
	{
		//字典KV模型
		BSTree<string, string> dict;
		dict.Insert("sort", "排序");
		dict.Insert("left", "左边");
		dict.Insert("right", "右边");
		dict.Insert("map", "地图、映射");
		//...
 
		string str;
		while (cin >> str)
		{
			BSTreeNode<string, string>* ret = dict.Find(str);
			if (ret)
			{
				cout << "对应中文解释: " << ret->_value << endl;
			}
			else
			{
				cout << "无此单词" << endl;
			}
		}
	}
 
	void TestBstree2()
	{
		//统计水果出现次数
		string arr[] = { "苹果" , "西瓜" ,"草莓" , "苹果", "西瓜" , "苹果" , "苹果" , "西瓜" ,"苹果","香蕉" ,"苹果" , "香蕉" };
		BSTree<string, int> countTree;
		for (auto& str : arr)
		{
			//BSTreeNode<string,int>* ret = cout << countTree.Find(str);
			auto ret = countTree.Find(str);
			if (ret != nullptr)
			{
				ret->_value++;
			}
			else
			{
				countTree.Insert(str, 1);
			}
		}
 
		countTree.InOrder();
	}
}