set和multiset

Set的特性是。所有元素都会根据元素的值自动被排序。Set不允许两个元素有相同的值。 不可通过set的迭代器改变set元素的值，set的iterator是一种const_iterator. set拥有和list某些相同的性质，当对容器中的元素进行插入操作或者删除操作的时候，操作之前所有的迭代器，在操作完成之后依然有效，被删除的那个元素的迭代器必然是一个例外。 multiset特性及用法和set完全相同，唯一的差别在于它允许值重复。set和multiset的底层实现是红黑树，红黑树为平衡二叉树的一种。

1.二叉树

二叉树就是任何节点最多只允许有两个字节点。分别是左子结点和右子节点

1.1 二叉搜索树

二叉搜索树，是指二叉树中的节点按照一定的规则进行排序，使得对二叉树中元素访问更加高效。二叉搜索树的放置规则是：任何节点的元素值一定大于其左子树中的每一个节点的元素值，并且小于其右子树的值。因此从根节点一直向左走，一直到无路可走，即得到最小值，一直向右走，直至无路可走，可得到最大值。那么在二叉搜索树中找到最大元素和最小元素是非常简单的事情。

假如又一串数字：18，13，22，11，9，8，10，25，23，27，16，那么他们所组成的二叉搜索树如下

他们排放的顺序是，从二叉树根部开始

若当前数比根节点大，则放右边
若当前数比根节点大，则放左边

若左右节点已有数字，则根据这个规则继续比较，以此类推

1.2 二叉树遍历

常见的二叉树遍历有如下几种

先序遍历：中、左、右
中序遍历：左、中、右
后序遍历：左、右、中

set数据结构的遍历就是二叉树的中序遍历

下面二叉树的中序遍历为，8，9，10，11，13，16，18，22，13，25，27

我们可以发现set的遍历是升序的

1.set和multiset

使用set和multiset都需要引入set包

c++

#include <set>
#include <iostream>

int main(){
    set<int> s;
    multiset<int> ms;
}

1.1 常用语法

c++

#include <set>
#include <iostream>

int main(){
    set<int> s;
    multiset<int> ms;
    
    s.insert(11);   // 插入元素
    
    set<int>::iterator it=s.begin();
    s.erase(it);		// 删除
    s.erase(it,it+3);  // 区间删除
    
    set<int>::iterator target =s.find(11);   // 查找元素是否存在，存在则返回此元素的迭代器，否则返回set.end()
    
    cout<< s.count(11)<<endl;   // 查找元素的个数
    
    set<int>::iterator res1 =s.lower_bound(11);  // 返回第一个元素小于等于指定元素的迭代器
    
    set<int>::iterator res =s.upper_bound(11);  // 返回第一个元素大于指定元素的迭代器
    
    cout<< s.size()<<endl;   // 查找set的长度
    
    cout<< s.empty()<<endl;   // 判断容器是否为空
}

注意

set容器中添加元素后会自动排序，使用指针删除时，s.begin()指向的排序过后的首元素

set和mutiset的区别：set中不会有重复元素，mutiset可以有

set和multiset ​

1.二叉树 ​

1.1 二叉搜索树 ​

1.2 二叉树遍历 ​

1.set和multiset ​

1.1 常用语法 ​