C++知识点汇总（3）

内容分享2个月前发布

8 0 0

1.写在前面

1.多态的概念

2.多态的实现

3.虚函数

虚函数的重写

题目练习

协变

析构函数的重写

重载重写隐藏

3.纯虚函数和抽象类

4.多态的原理

1.虚表

2.虚函数指针

总结：

二叉搜索树的介绍

1.概念介绍

2.性能分析

3.二叉搜索树的插入

4.二叉树的查找

5.二叉树的删除

2.二叉搜索树的模拟实现

1.创建节点

2.构造函数

3.二叉搜索树的成员变量

4.插入操作

5.查找操作

6.中序遍历

7.删除节点

8.析构函数

9.拷贝构造函数

10.赋值运算符的重载

3.⼆叉搜索树key和key/value使⽤场景

1.map和set

2.set系列的使用

1.set和multiset的使用文档介绍

2.set类的介绍

编辑

3.迭代器的使用

3.set和multise的差别

4.map的使用

5.pair

6.这里介绍一下map的[]的使用方法

7.题目练习

下面我们借助一个题目来熟悉一下map和multimap的接口，体会一下k-v的使用方法：

编辑

1.写在前面

我们的C++学习完之后，想把以前的博客汇总成一篇，方便以后复习查看，所以写了这篇博客。

在这其中，我们以后系统中学习的先描述在组织以及在我们的代码解耦和中常用的把我们的方法当做参数传递给一个类都让我们理解到了只是串联性，描述用结构体来，组织选用合适的结构体来，我们的学习都是贯穿始终，在学中用，用中学。实践与理论的结合让我们更好的理解知识！！！

1.多态的概念

说人话就是在继承的基础上传不同的对象实现不同的功能。

多态分为静态多态和动态多态，静态多态又称编译时多态，就是编译时就确定调用哪个函数，例如函数重载传不同的参数调用不同的函数这在编译时就是确定的，动态多态又称运行时多态，就是在运行时根据实际对象才决定调用哪个函数。

2.多态的实现

1.必须是基类的指针或引用调用的虚函数。

2.被调用的虚函数完成了重写。

下面代码打印的是B的fun()。就是满足了多态的两个实现条件。

那么我们要反问一句为什么要必须调用基类的指针或引用呢？赋值不行吗？答案是不行，因为前面继承中我们学习过派生类给基类赋值会发生切片，直接把派生类部分给切掉然后进行拷贝构造进行赋值，无法调用派生类f()。

我们现在记住一句话叫做是根据对象的实际类型进行多态函数的调用。我们传引用它的类型还是派生类只不过我们不能访问派生类的派生类新增部分，但是如果我们去传值进行拷贝构造的话，它的类型就是基类而不再是派生类。



class A {
public:
    virtual void f() 
    {
        cout << "A::f()" << endl;
    }
};
 
class B : public A 
{
private:
    virtual void f() override 
    {
        cout << "B::f()" << endl;
    }
};
 
int main() {
    A* a = new B;
    a->f();
    return 0;
}

3.虚函数

下面我们来了解多态的实现的重要工具虚函数，在函数前面加virtual就是虚函数，它的作用就是来实现多态。

虚函数的重写

当派生类与父类的成员函数有同名时，该成员函数构成隐藏，当父类和父类的成员函数，它们的函数名相同，并且参数类型相同，返回值相同时，并且它们都是虚函数时啊，这时我们就构成了虚函数的重写。父类的虚函数是一个实现方式，子类的虚函数是一个实现方式，虚函数的复写是我们实现传不同对象调用不同函数的关键。

注意：正常情况下，我们父类和子类的虚函数都要加virtual，但是实际上，如果我们父类加虚函数关键字，子类不加，它仍然能够复写，但是如果父类没加虚函数关键字，但是子类加了，它就不能构成复写，这里是一个比较特殊的点。

题目练习

这个题目我们可以看出它是通过B类型的指针去调用test，B的test是从A中继承的，这时调用test又会调用func,但是它构成了多态所以我们调用B类的func，但是，这里重写仅仅是实现的重写，但是val仍然是父类的val。所以这道题选B，非常的坑。



以下程序输出结果是什么（）
A: A->0 B: B->1 C: A->1 D: B->0 E: 编译出错 F: 以上都不正确
class A
{
public:
virtual void func(int val = 1){ std::cout<<"A->"<< val <<std::endl;}
virtual void test(){ func();}
};
class B : public A
{
public:
void func(int val = 0){ std::cout<<"B->"<< val <<std::endl; }
};
int main(int argc ,char* argv[])
{
B*p = new B;
 
p->test();
return 0;
}

协变

派⽣类重写基类虚函数时，与基类虚函数返回值类型不同。即基类虚函数返回基类对象的指针或引

⽤，派⽣类虚函数返回派⽣类对象的指针或者引⽤时，称为协变。协变的实际意义并不⼤，所以们

了解⼀下即可。

析构函数的重写

在继承中虚构函数要进行重写，我们要对析构函数进行谨慎处理，核心问题在于：

当通过 基类指针删除派生类对象 时，如果基类的析构函数 不是虚函数，会导致：

派生类的析构函数不被调用，仅调用基类的析构函数。

派生类独有的资源（如动态内存、文件句柄）泄漏。

下面我们用代码来解释一下。

如果我们不写析构函数的虚函数的话，它析构只会调用A的析构。核心问题再次强调一下：基类指针删除派生类对象，不写析构不会调派生类的析构。



using namespace std;
 
class A {
public:
    virtual void f() 
    {
        cout << "A::f()" << endl;
    }
    virtual ~A()
    {
        cout << "~A";
    }
};
 
class B : public A 
{
private:
    virtual void f() override 
    {
        cout << "B::f()" << endl;
    }
    virtual ~B()
    {
        cout << "~B";
    }
};
 
int main() {
    A* a = new A;
    A* b = new B;
    delete a;
    delete b;
    return 0;
}

了解完析构函数继承要写多态后，有的人就要问了，主播主播构造函数和静态函数需不需要写呢？

这个问题我们下面来解答会更清晰一点！

重载重写隐藏

重载是在同一作用域内，函数名相同参数不同的函数构成重载，根据不同的参数进行调用。

重写是在不同作用域父类和子类同名，同参数，同返回值的虚函数（函数名前加virtual）进行传不同的对象调用不同的函数实现多态。

隐藏是在不同作用域，父类和子类成员同名父类成员在派生类中会被隐藏。

3.纯虚函数和抽象类

在虚函数后加=0构成纯虚函数，它没有实际的定义。包含纯虚函数的类叫抽象类。抽象类不能实例化出对象，派生类如果继承后不重写纯虚函数也会是抽象类。纯虚函数某种程度上强制了派生类重写虚函数，因为不重写的话还是抽象类，无法实例化出对象。

了解完多态的定义和概念后，我们下来了解多态的原理。

4.多态的原理

多态是依赖虚表和虚指针来实现的。

1.虚表

每个包含虚函数的类都含有一个虚表，存储虚函数的地址。

当派生类继承含义虚函数的父类时，如果派生类不重写虚函数，它的虚表的内容和父类的虚表内容一致，只不过会新增派生类中新增的虚函数。如果派生类重写父类的虚函数，重写的虚函数就会覆盖原有的父类的虚函数。

注意：即使派生类中不重写父类的虚函数，它的vptr指向的物理地址也不一样。一个类共享一个vptr。

虚函数表细则：

基类对象的虚函数表中存放基类所有虚函数的地址。同类型的对象共⽤同⼀张虚表，不同类型的对

象各⾃有独⽴的虚表，所以基类和派⽣类有各⾃独⽴的虚表。

派⽣类由两部分构成，继承下来的基类和⾃⼰的成员，⼀般情况下，继承下来的基类中有虚函数表

指针，⾃⼰就不会再⽣成虚函数表指针。但是要注意的这⾥继承下来的基类部分虚函数表指针和基

类对象的虚函数表指针不是同⼀个，就像基类对象的成员和派⽣类对象中的基类对象成员也独⽴

的。

•

派⽣类中重写的基类的虚函数，派⽣类的虚函数表中对应的虚函数就会被覆盖成派⽣类重写的虚函

数地址。

•

派⽣类的虚函数表中包含，(1)基类的虚函数地址，(2)派⽣类重写的虚函数地址完成覆盖，派⽣类

⾃⼰的虚函数地址三个部分。

•

虚函数表本质是⼀个存虚函数指针的指针数组，⼀般情况这个数组最后⾯放了⼀个0x00000000标

记。(这个C++并没有进⾏规定，各个编译器⾃⾏定义的，vs系列编译器会再后⾯放个0x00000000

标记，g++系列编译不会放)

•

虚函数存在哪的？虚函数和普通函数⼀样的，编译好后是⼀段指令，都是存在代码段的，只是虚函

数的地址⼜存到了虚表中。

•

虚函数表存在哪的？这个问题严格说并没有标准答案C++标准并没有规定，我们写下⾯的代码可以

对⽐验证⼀下。vs下是存在代码段(常量区)

2.虚函数指针

每个含有虚函数的类中有虚函数指针，指向虚函数表，我们通过这个指针来调用虚函数。

结合下图我们再结合我们继承的知识，我们来复盘一下虚函数调用的具体过程，__vfptr是指向虚表的指针，虚表里存储的虚函数的地址，如果我们父类含有虚函数，子类不对它进行重写，子类依旧会继承父类的虚函数并有自己独特的虚函数表，只不过它的定义和父类相同，如果我们对父类的虚函数进行重写，那么我们重写的虚函数会覆盖原有的虚函数。这样我们就可以调用重写的虚函数了。

当我们把派生类对象的引用或地址传给父类的引用或地址时，它不会发生切片，仅仅是我们不能通过它访问派生类新增的对象，但是__vfptr是可以访问的。且我们访问的是修改之后的__vfptr，我们借助代码再来理解一下。

C++知识点汇总（3）

“派生类对象会拥有自己的 __vfptr，它默认指向派生类的虚表。如果派生类重写了基类的虚函数，则虚表中对应条目会更新为派生类的函数地址；否则保留基类的实现。

注意：这里的虚表都是独立的并不是基类的虚表和派生类的虚表共享一份，他们之间是独立的独立的独立的！！！

再借鉴下面这句话来理解一下，

派⽣类由两部分构成，继承下来的基类和⾃⼰的成员，⼀般情况下，继承下来的基类中有虚函数表

指针，⾃⼰就不会再⽣成虚函数表指针。但是要注意的这⾥继承下来的基类部分虚函数表指针和基

类对象的虚函数表指针不是同⼀个，就像基类对象的成员和派⽣类对象中的基类对象成员也独⽴

的。

这里就是虚函数的调用是根据其实际类型进行调用的。



class Person {
public:
virtual void BuyTicket() { cout << "买票-全价" << endl; }
private:
string _name;
};
class Student : public Person {
public:
virtual void BuyTicket() { cout << "买票-打折" << endl; }
private:
string _id;
};
class Soldier: public Person {
public:
virtual void BuyTicket() { cout << "买票-优先" << endl; }
private:
string _codename;
};
void Func(Person* ptr)
{
// 这⾥可以看到虽然都是Person指针Ptr在调⽤BuyTicket
// 但是跟ptr没关系，⽽是由ptr指向的对象决定的。
ptr->BuyTicket();
}
int main()
 
{
// 其次多态不仅仅发⽣在派⽣类对象之间，多个派⽣类继承基类，重写虚函数后
// 多态也会发⽣在多个派⽣类之间。
Person ps;
Student st;
Soldier sr;
Func(&ps);
Func(&st);
Func(&sr);
return 0;
}

总结：

相信到了这里大家就该大致了解多态和继承了，继承的基础上我们定义了多态来实现编程的方便，继承是父类的成员继承给派生类，但是它们之间的成员并没有关联，父类有int a，派生类继承int a，派生类中的a和父类的a实际是没有关系的，因为本质上它们是属于两个不同的类，多态我们引入了虚函数指针和虚函数表，虚函数表中的虚函数继承了父类的虚函数，如果我们再派生类中对他们进行重写，重写的虚函数就会覆盖原有的虚函数表中对应的虚函数。

附言：上文中我们提到了构造函数和静态函数不可以虚函数化，现在我们可以给出解释，构造函数不可以虚函数化是因为函数前面加virtual会调用虚函数指针，但是虚函数指针是构造中生成的，这会发生矛盾，编译无法通过，至于静态函数不可以虚函数化，静态函数不属于某个类的对象，它是属于整个类，它不通过对象调用，没有this指针，前面我们说过多态就是根据不同的对象调用来实现多态，但是静态函数不通过对象调用，所以我们的静态函数不可以虚函数化！！！

二叉搜索树的介绍

1.概念介绍

当学完了vector和list等容器和封装继承多态等特性后，接下来学习的就是BS树了，它的特性是：

1.所有的左子树小于根结点的值。

2.所有的右子树大于根结点的值。

3.它的左右子树也为二叉搜索树。

4.⼆叉搜索树中可以⽀持插⼊相等的值，也可以不⽀持插⼊相等的值，具体看使⽤场景定义，后我

们学习map/set/multimap/multiset系列容器底层就是⼆叉搜索树，其中map/set不⽀持插⼊相等

值，multimap/multiset⽀持插⼊相等值。

2.性能分析

当它接近满二叉树时，它的性能接近log2N,这得益于它的结构，由于它的左子树小于根节点，右子树大于根节点，每次比较就干掉一半的值，效率非常高。

C++知识点汇总（3）

相反当它的结构到达极端情况时，搜索效率会降低到O(n)，退化成链表的结构。

C++知识点汇总（3）

3.二叉搜索树的插入

1.树为空，直接赋值给_root节点

2.树不为空，按照二叉搜索树的性质来，比根节点大，再去和右子树比较，比根节点小，再去和左子树比较，直到找到空位置。

注意：这个特性表示了它的插入顺序很可能影响搜索效率，比如在下面的二叉树中，如果我一开始就插入100这样的大值，那么根结点的右边就会不再插入值，会去左节点插入。

C++知识点汇总（3）

4.二叉树的查找

二叉树的查找是根据特性，当要查找的值比根节点大，向右子树走，比根节点小，向左子树走，直到找到与要查找的值相等的节点。

5.二叉树的删除

二叉树的删除我们分成几种情况来讨论：

1.要删除的节点左右子树都为空，由于左右子树都为空，所以删除它不影响其它节点，所以直接删除它即可。

2.删除的节点左子树为空但右子树不为空，这个时候把它的左子树托付给它的父节点即可，这时需要注意是向父节点的哪边插入。

3.删除的节点右子树为空但左子树不为空，这个时候和上述类似，思路就是把它的子节点托付给它的父节点，注意插入的方向即可。

4.删除的节点左右子树均不为空，这个时候我们要去查找该节点的右子树的最小值或者左子树的最大值来替代这个节点。这是由于二叉搜索树的特性导致的，该节点的右子树的所以节点大于该节点，这时需要找一个大于该节点的所以值中找一个最小的值，保证它比左子树的所有值大，比右子树的所有值小。类似的，左子树的所以节点的值都小于该节点，这时就需要在左子树中找一个最大的值来替代它，保证该值比左子树的所以值大，比右子树的所以值小。

当然，也可以这么说，找到它们左右子树中最特殊的来替代它就可以了。

C++知识点汇总（3）

这里可以结合图片来理解一下：

C++知识点汇总（3）

2.二叉搜索树的模拟实现

接下来进入到我们的模拟实现环节，通过模拟实现二叉搜索树我们可以更好的理解它的特性，我们通过前面的知识了解到，当它的结构趋近于满二叉树时，它的搜索效率是非常高的，一下干掉一半的值，每进入到下一个节点时就会让数减半，试想，一亿个数按近似于满二叉树存入，我们每次进入下一个节点时就干掉一半的值，举个例子，一亿个数查找一个数，每次进入下一个节点时我们直接就令查找的数目减半。大大提高我们的搜索效率！！！

1.创建节点

二叉搜索树的数据是存储在节点中的，我们先实现一个节点。这里使用了类模板来实现了泛型编程，可以传int,string等。



template<class T>
struct node
{
	node(const T& data )
	{
		_left = _right = nullptr;
		_val = data;
	}
	node<T>* _left;
	node<T>* _right;
	T _val = 0;
};

2.构造函数

构造函数我们不写，因为下面的私有变量中我们给了nullptr的缺省值，直接按缺省值进行初始化。



BSTREE()
{
 
}

3.二叉搜索树的成员变量

我们给一个跟节点即可，因为我们根节点存储的地址可以让操作者访问所有的二叉搜索树。



	private:
		node<T>* _root = nullptr;

4.插入操作

插入操作在上面介绍过了，在这里再简单说一下，根节点为空，直接new一个节点赋值给根节点，不为空根据二叉搜索树的特性，要插入的值比根节点小，向左走，大向右走，直到找到空位置进行插入。



bool Insert(const T& key)
{
	if (_root == nullptr)
	{
		auto root = new node<T>(key);
		_root = root;
		return true;
	}
		node<T>* parent = _root;
		node<T>* cur = _root;
		while (cur != nullptr)
		{
			if (cur->_val > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_val < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
			}
		}
		/*cur->_val = key;*///理解一下这里为什么不对。。。原因是cur是空指针，对空指针赋值我简直太聪明了
		cur = new node<T>(key);
		if (parent->_val > key)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		return true;
}

5.查找操作

查找的操作和插入的操作有异曲同工之妙，只不过把插入的目的变成了判断相等。

比跟节点大，向右走，小，向左走，相等返回，若找到nullptr还未找到要查找的值返回false表示未找到。



	node<T>* Find(const T& key)
	{
		if (_root==nullptr)
		{
			return nullptr;
		}
		else
		{
			auto cur = _root;
			while (cur!=nullptr)
			{
				if (cur->_val > key)
				{
					cur = cur->_left;
				}
				else if (cur->_val < key)
				{
					cur = cur->_right;
				}
				else
				{
					return cur;
				}
			}
		}
		return nullptr;
	}

6.中序遍历

由于外部无法访问二叉搜索树的根节点，所以遍历我们写成私有，类的内部可以访问私有值，让接口来调用这个私有即可。

接下来介绍写法的重点：递归

核心思想是把一个问题分成若干个小问题，当满足某个条件时返回作为终止条件。

中序遍历是左根右，假如我们先简化，先访问左节点的值，然后打印，再去访问右节点的值，打印。终止条件为传的地址为nullptr。然后再推广，当它们的节点还有很多时，人脑是无法很快反应过来的，我们要从总体去看一下，就是将问题分解为相似的子问题，依赖终止条件回溯结果。

C++知识点汇总（3）



void InOrder()
{
	_InOrder(_root);
	cout << endl;
}
private:
void _InOrder(node<T>* root)//中序遍历
{
	if (root==nullptr)
	{
		return ;
	}
	_InOrder(root->_left);
	cout << root->_val<<" ";
	_InOrder(root->_right);
}

7.删除节点

删除节点上述我们介绍过，这里强调一下特殊情况，

1.当cur==_root时，特殊处理一下，直接删掉根节点置空。

2.当_minright==_pminright时，这表明要删除的节点的右节点没有左孩子节点了，特殊处理，这这交换之后直接删掉有节点置空。

3.当cur==parent说明要删除的节点为头节点并且minright==pminright，特殊处理，交换值之后进行直接指向minright的右节点即可。



	   bool Erase(const T&key)
		{
		   if (_root==nullptr)
		   {
			   return false;
			}
		   else
		   {
			   node<T>* cur = _root;
			   node<T>* parent = _root;
			   while (cur)
			   {
				   if (cur->_val > key)
				   {
					   parent = cur;
					   cur = cur->_left;
				   }
				   else if (cur->_val < key)
				   {
					   parent = cur;
					   cur = cur->_right;
				   }
				   else
				   {
					   break;
				   }
			   }
		   
			   if (cur == nullptr)return false;
			   if (cur == _root && cur->_left == nullptr && cur->_right == nullptr)
			   {
				   delete _root;
				   _root = nullptr;
			   }
			   else if(cur->_left==nullptr&&cur->_right==nullptr)//左右孩子都为空
			   {
				   //不确定哪边孩子
				   if (parent->_val > key)//左孩子
				   {
					   parent->_left = nullptr;
					   delete cur;
				   }
				   else
				   {
					   parent->_right = nullptr;
					   delete cur;
					   cur = nullptr;
				   }
				   return true;
			   }
			   else if (cur->_left == nullptr)//左孩子为空
			   {
				   if (parent->_val > key)//左孩子
				   {
					   parent->_left = cur->_right;
					   delete cur;
					   cur = nullptr;
				   }
				   else
				   {
					   parent->_right = cur->_right;
					   delete cur;
					   cur = nullptr;
				   }
				   return true;
			   }
			   else if (cur->_right == nullptr)
			   {
				   if (parent->_val > key)//左孩子
				   {
					   parent->_left = cur->_left;
					   delete cur;
					   cur = nullptr;
				   }
				   else
				   {
					   parent->_right = cur->_left;
					   delete cur;
					   cur = nullptr;
				   }
				   return true;
			   }
			   else
			   {
				   //找到右孩子的最小
				   auto pminright = cur->_right;
				   auto minright = cur->_right;
				   while (minright->_left != nullptr)
				   {
					   pminright = minright;
					   minright = minright->_left;
				   }
				   swap(minright->_val, cur->_val);
				   if (cur == parent && pminright == minright)
				   {
					   cur->_right = minright->_right;
					   delete minright;
					   minright = nullptr;
				   }
				   else if (pminright == minright)
				   {
					   delete minright;
					   minright = nullptr;
				   }
				   else
				   {
					   delete pminright->_left;
					   pminright->_left = nullptr;
				   }
			   }
			  }
		   return true;
		}

8.析构函数

析构函数应该是后续析构，不然删除根节点无法找到子节点，我们类似的简单想，应该先去左子树或者右子树去删除，假设只有三个节点，先去左子树，然后删除左子树，再去右子树，删除右子树，最后析构根节点。所以递归的结构就能写出来



		void shanchu(node<T>* root)
		{
			if (root == nullptr)return;
			shanchu(root->_left);
			shanchu(root->_right);
			delete root;
		}

9.拷贝构造函数

拷贝构造是先序构造，先构造一个值相等的根节点，再去构造左子树，最后构造右子树，递归结构也可以这样写出：



		 node<T>* copy(node<T>* root)
		{
			if (root == nullptr)
			{
				return nullptr;
			}
			node<T>* nroot = new node<T>(root->_val);//构造根节点。
			nroot->_left=copy(root->_left);//构造左节点
			nroot->_right=copy(root->_right);//构造右节点。
			return nroot;
		}

10.赋值运算符的重载

在进行重载时，要特别注意浅拷贝。去复用拷贝构造即可。



		BSTREE operator=(BSTREE<T>& t)
		{
			*this(t);
			return *this;
		}

下面给出整个的二叉搜索树key的实现代码方便查阅：



#pragma once
#include<iostream>
using namespace std;
namespace zb
{
	template<class T>
	struct node
	{
		node(const T& data )
		{
			_left = _right = nullptr;
			_val = data;
		}
		node<T>* _left;
		node<T>* _right;
		T _val = 0;
	};
	template<class T>
	class BSTREE
	{
	public:
		BSTREE()
		{
 
		}
		BSTREE(const BSTREE<T>& t)
		{
			_root=copy(t._root);
		}
		~BSTREE()//左右根
		{
			shanchu(_root);
			_root = nullptr;
		}
		BSTREE operator=(BSTREE<T>& t)
		{
			*this(t);
			return *this;
		}
		bool Insert(const T& key)
		{
			if (_root == nullptr)
			{
				auto root = new node<T>(key);
				_root = root;
				return true;
			}
				node<T>* parent = _root;
				node<T>* cur = _root;
				while (cur != nullptr)
				{
					if (cur->_val > key)
					{
						parent = cur;
						cur = cur->_left;
					}
					else if (cur->_val < key)
					{
						parent = cur;
						cur = cur->_right;
					}
					else
					{
						return false;
					}
				}
				/*cur->_val = key;*///理解一下这里为什么不对。。。原因是cur是空指针，对空指针赋值我简直太聪明了
				cur = new node<T>(key);
				if (parent->_val > key)
				{
					parent->_left = cur;
				}
				else
				{
					parent->_right = cur;
				}
				return true;
		}
		node<T>* Find(const T& key)
		{
			if (_root==nullptr)
			{
				return nullptr;
			}
			else
			{
				auto cur = _root;
				while (cur!=nullptr)
				{
					if (cur->_val > key)
					{
						cur = cur->_left;
					}
					else if (cur->_val < key)
					{
						cur = cur->_right;
					}
					else
					{
						return cur;
					}
				}
			}
			return nullptr;
		}
		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}
	   bool Erase(const T&key)
		{
		   if (_root==nullptr)
		   {
			   return false;
			}
		   else
		   {
			   node<T>* cur = _root;
			   node<T>* parent = _root;
			   while (cur)
			   {
				   if (cur->_val > key)
				   {
					   parent = cur;
					   cur = cur->_left;
				   }
				   else if (cur->_val < key)
				   {
					   parent = cur;
					   cur = cur->_right;
				   }
				   else
				   {
					   break;
				   }
			   }
		   
			   if (cur == nullptr)return false;
			   if (cur == _root && cur->_left == nullptr && cur->_right == nullptr)
			   {
				   delete _root;
				   _root = nullptr;
			   }
			   else if(cur->_left==nullptr&&cur->_right==nullptr)//左右孩子都为空
			   {
				   //不确定哪边孩子
				   if (parent->_val > key)//左孩子
				   {
					   parent->_left = nullptr;
					   delete cur;
				   }
				   else
				   {
					   parent->_right = nullptr;
					   delete cur;
					   cur = nullptr;
				   }
				   return true;
			   }
			   else if (cur->_left == nullptr)//左孩子为空
			   {
				   if (parent->_val > key)//左孩子
				   {
					   parent->_left = cur->_right;
					   delete cur;
					   cur = nullptr;
				   }
				   else
				   {
					   parent->_right = cur->_right;
					   delete cur;
					   cur = nullptr;
				   }
				   return true;
			   }
			   else if (cur->_right == nullptr)
			   {
				   if (parent->_val > key)//左孩子
				   {
					   parent->_left = cur->_left;
					   delete cur;
					   cur = nullptr;
				   }
				   else
				   {
					   parent->_right = cur->_left;
					   delete cur;
					   cur = nullptr;
				   }
				   return true;
			   }
			   else
			   {
				   //找到右孩子的最小
				   auto pminright = cur->_right;
				   auto minright = cur->_right;
				   while (minright->_left != nullptr)
				   {
					   pminright = minright;
					   minright = minright->_left;
				   }
				   swap(minright->_val, cur->_val);
				   if (cur == parent && pminright == minright)
				   {
					   cur->_right = minright->_right;
					   delete minright;
					   minright = nullptr;
				   }
				   else if (pminright == minright)
				   {
					   delete minright;
					   minright = nullptr;
				   }
				   else
				   {
					   delete pminright->_left;
					   pminright->_left = nullptr;
				   }
			   }
			  }
		   return true;
		}
	private:
		void _InOrder(node<T>* root)//中序遍历
		{
			if (root==nullptr)
			{
				return ;
			}
			_InOrder(root->_left);
			cout << root->_val<<" ";
			_InOrder(root->_right);
		}
		void shanchu(node<T>* root)
		{
			if (root == nullptr)return;
			shanchu(root->_left);
			shanchu(root->_right);
			delete root;
		}
		 node<T>* copy(node<T>* root)
		{
			if (root == nullptr)
			{
				return nullptr;
			}
			node<T>* nroot = new node<T>(root->_val);//构造根节点。
			nroot->_left=copy(root->_left);//构造左节点
			nroot->_right=copy(root->_right);//构造右节点。
			return nroot;
		}
	private:
		node<T>* _root = nullptr;
	};
}

3.⼆叉搜索树key和key/value使⽤场景

最后再介绍一下key/value的使用场景，这个本质是多存储一个value值。可以实现以下诸多操作：

中英互译，门牌号查找。注意key的值不可被修改，否则会打乱二叉树的顺序，乱序了。

1.map和set

set存储的是key值，map存储的是key-value值，它们都属于关联式容器，正常情况下map和set不支持冗余，想要插入相同的数据，需要使用multiset和multimap来进行冗余数据的插入，这里冗余指的是key值相等。

2.set系列的使用

1.set和multiset的使用文档介绍

<set> – C++ Reference

2.set类的介绍

库中给出了set的一些接口，我们介绍一下，和其他容器一样，set也支持迭代器，它的迭代是中序遍历，insert是插入一个数据，这里插入之后会自动进行排序，find是在set中寻找你想要的值，找到返回迭代器，未找到返回end()，count是返回容器中有一个要寻找的值，未找到返回0.

3.迭代器的使用

这里要注意一下，set的迭代器不能修改数据，因为一旦修改数据，会导致树的结构错乱，破坏了树结构。

3.set和multise的差别

set不支持冗余数据的插入，multise支持冗余数据的插入。

4.map的使用

map和set的区别是它支持key-value的插入，我们不可以修改key值，但是可以修改value的值，它本质是加了一个变量value来帮助我们实现更多的功能，比如字典某一个字母出现的次数。它的查找效率是logN。

5.pair

map底层的红⿊树节点中的数据，使⽤pair<Key, T>存储键值对数据。

6.这里介绍一下map的[]的使用方法

map的[]里应该是key值，如果有，则返回value的值，没有则插入。

下列代码中，如果在map中未找到str，就会插入，并且value值+1。



int main()
{
	// 利⽤[]插⼊+修改功能，巧妙实现统计⽔果出现的次数
	string arr[] = { "苹果", "西⽠", "苹果", "西⽠", "苹果", "苹果", "西⽠",
	"苹果", "⾹蕉", "苹果", "⾹蕉" };
	map<string, int> countMap;
	for (const auto& str : arr)
	{
		// []先查找⽔果在不在map中
		// 1、不在，说明⽔果第⼀次出现，则插⼊{⽔果, 0}，同时返回次数的引⽤，
			// 2、在，则返回⽔果对应的次数++
			countMap[str]++;
	}
	for (const auto& e : countMap)
	{
		cout << e.first << ":" << e.second << endl;
	}
	cout << endl;
	return 0;
}



int main()
{
map<string, string> dict;
dict.insert(make_pair("sort", "排序"));
// key不存在->插⼊ {"insert", string()}
dict["insert"];
// 插⼊+修改
dict["left"] = "左边";
// 修改
dict["left"] = "左边、剩余";
// key存在->查找
cout << dict["left"] << endl;
return 0;
}

7.题目练习

下面我们借助一个题目来熟悉一下map和multimap的接口，体会一下k-v的使用方法：

这道题目让我们打印各个单词出现的次数，我们先把这个stringd单词存到map中去，让它的字母按顺序排，然后按降序再存入map<int,string,greater<int>>中去，方便我们的打印，这样第一次存我们按照字母的顺序存入，第二次存入我们按照出现次数进行存入，既保证了次数相同字母的出现顺序，又保证了从大到小的存入。

注：二次存入的一个原因是key无法修改，只能修改v，如果我们只存入一次，第一次只会得到字母的顺序，无法得到按v的顺序，第二次存入是得到v的顺序和k的顺序。

下面我们给出相应的代码参考



#include<iostream>
#include<map>
using namespace std;
int main() 
{
    string a;
    map<string, int>mup;
    int count = 0;
    while (cin >> a)
    {
        if (a[0] <= 'Z' && a[0] >= 'A')
        {
            a[0] = a[0] + 32;
         }
        if (a[a.size()-1] == '.')
        {
             a.pop_back();
 auto it1= mup.find(a);
 if (it1 == mup.end())
 {
     mup.insert({ a, 1 });
 }
 else
 {
     mup[a]++;
 }
 break;
 }
        else
        {
            auto it = mup.find(a);
            if (it == mup.end())
            {
                mup.insert({ a, 1 });
            }
            else
            {
                mup[a]++;
            }
        }
    }
    multimap<int, string, greater<int>>mup2;
    for (auto e : mup)
    {
        mup2.insert({ e.second,e.first });
    }
    for (auto e : mup2)
    {
        cout << e.second << ":" << e.first << endl;
    }
    return 0;
}