2、C++程序设计与数据结构

2.1 类

2.1.1 类的概念及简单应用

​ 在C++中，类（Class）是一种复合数据类型，它不仅可以包含多种类型的数据成员（属性），还可以包含函数成员（方法）。类是面向对象编程（OOP）的基础，它提供了封装、继承和多态等核心特性。

类的定义

类的定义使用关键字class，后跟类名和类体。类体内可以定义属性和方法，用来表示对象的状态和行为。

1
2
3
4
5
6

class ClassName {
public:
    // 公有数据成员和方法
private:
    // 私有数据成员和方法
};

• 公有成员（Public）：可以被任何外部函数或类的对象访问。
• 私有成员（Private）：只能被类的成员函数访问。

类的简单应用

下面是一个简单的类Circle的定义和使用，它代表一个圆，拥有半径属性和计算面积的方法。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <iostream>
using namespace std;

class Circle {
public:
    double radius; // 半径

    // 构造函数，初始化半径
    Circle(double r) {
        radius = r;
    }

    // 成员函数，计算面积
    double area() {
        return 3.14159 * radius * radius;
    }
};

int main() {
    Circle circle(10.0); // 创建Circle对象，半径为10.0
    cout << "Circle area: " << circle.area() << endl; // 输出圆的面积
    return 0;
}

​ 在这个例子中，Circle类有一个公有的数据成员radius和一个公有的成员函数area，后者用于计算圆的面积。Circle的一个对象被创建时，它的半径通过构造函数初始化。然后，我们可以使用这个对象调用area方法来获取圆的面积。

类的特点

• 封装：类可以将数据和操作数据的方法封装在一起，对外隐藏实现细节。
• 继承：允许创建新的类（派生类）继承基类（父类）的特性和行为。
• 多态：通过继承和虚函数，允许使用基类的指针或引用来调用派生类的方法。

通过使用类，C++程序员可以实现复杂的数据抽象和面向对象设计，这有助于创建更加模块化和可重用的代码。

2.1.2 成员函数和运算符重载

​ 在C++中，成员函数是定义在类内部的函数，用于操作类的属性或执行与类相关的任务。运算符重载则是一种特殊的成员函数，它使得自定义类型的对象可以使用C++内置的运算符进行操作。

成员函数

​ 成员函数可以定义为类的一部分，用来访问和操作类的私有成员。它们可以是普通的成员函数、构造函数、析构函数或者是静态成员函数。

• 构造函数：用于初始化对象的状态。它的名称与类名相同，可以有参数，但不能有返回类型。
• 析构函数：用于执行清理操作，如释放资源。它的名称是在类名前加上~符号，不能有参数也没有返回类型。
• 静态成员函数：不依赖于类的任何对象就可以被调用。它通过在成员函数声明前加上关键字static来定义。静态成员函数只能访问静态成员变量或调用其他静态成员函数。

运算符重载

运算符重载允许给已有的运算符分配额外的用户定义的含义，使得我们可以对自定义类型进行操作就像它们是内置类型一样。

• 运算符重载可以通过成员函数或全局函数来实现。如果是成员函数，其第一个操作数必须是对象本身。
• 重载的运算符的语法与普通函数相似，但其名称是由关键字operator后跟要重载的运算符符号组成的。

示例：重载加法运算符

下面是一个简单的示例，展示了如何为一个自定义的Vector类重载加法运算符+。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#include <iostream>
using namespace std;

class Vector {
public:
    int x, y;

    Vector(int x, int y) : x(x), y(y) {}

    // 重载+运算符
    Vector operator+(const Vector& rhs) const {
        return Vector(x + rhs.x, y + rhs.y);
    }
};

int main() {
    Vector v1(5, 4), v2(2, 10);
    Vector v3 = v1 + v2; // 使用重载的+运算符
    cout << "v3: (" << v3.x << ", " << v3.y << ")" << endl;
    return 0;
}

​ 在这个例子中，我们为Vector类重载了+运算符，使得可以直接通过+运算符来实现两个Vector对象的加法。operator+是作为成员函数实现的，它接受一个Vector对象作为参数，并返回两个Vector对象成员变量x和y相加后的新对象。

​ 运算符重载的使用使得代码更加直观和简洁，但也需要谨慎使用，以避免引入歧义或降低代码的可读性。

2.2 STL模板

2.2.1 集合（set）

​ 在C++中，set是标准模板库（STL）的一部分，提供了一种存储唯一元素的容器模型，其中的元素按照一定的顺序排列。set底层通常实现为红黑树，这是一种自平衡的二叉搜索树。由于这种实现方式，set中的元素会自动排序，并且插入、删除、搜索操作的时间复杂度为O(log n)，其中n是集合中元素的数量。

set的基本用法

要使用set，你需要包含头文件<set>。

1

#include <set>

创建set

你可以像下面这样创建一个set：

1

std::set<int> mySet;

向set中插入元素

使用insert方法向set中添加元素：

1
2
3

mySet.insert(10);
mySet.insert(5);
mySet.insert(15);

由于set中的元素是唯一的，如果尝试插入一个已经存在的元素，操作将不会改变set。

访问set中的元素

set不支持随机访问，所以不能使用下标操作符[]访问元素。要遍历set中的所有元素，你可以使用迭代器：

1
2
3

for(auto it = mySet.begin(); it != mySet.end(); ++it) {
    std::cout << *it << std::endl;
}

或者更简洁的范围for循环：

1
2
3

for(const auto& element : mySet) {
    std::cout << element << std::endl;
}

删除元素

从set中删除元素可以使用erase方法：

1

mySet.erase(10);

查找元素

使用find方法在set中查找元素，如果找到，则返回指向该元素的迭代器，否则返回end()迭代器：

1
2
3
4
5
6

auto search = mySet.find(10);
if(search != mySet.end()) {
    std::cout << "Found " << *search << std::endl;
} else {
    std::cout << "Not found" << std::endl;
}

特点

• 自动排序：元素插入时会自动排序。
• 唯一性：不允许有重复的元素。
• 高效的查找、插入和删除操作：时间复杂度通常为O(log n)。

set非常适合于需要快速查找、插入和删除且元素不重复的场景。在信息学奥赛等编程竞赛中，set可以用来高效地解决许多涉及集合操作的问题。

2.2.2 列表（list），双端队列（deque），优先队列（priority_queue）

1.列表（list）

​ 在C++标准模板库（STL）中，list是一个双向链表容器，提供了快速的元素插入和删除操作。与vector相比，list在任何位置插入或删除元素的时间复杂度都是O(1)，但它不支持随机访问，即不能像数组那样通过下标访问元素，访问任意位置的元素时间复杂度是O(n)。

list的基本用法

要使用list，需要包含头文件<list>。

1

#include <list>

创建list

你可以像下面这样创建一个list：

1

std::list<int> myList;

向list中添加元素

• 使用push_back在列表末尾添加元素。
• 使用push_front在列表开头添加元素。

1
2

myList.push_back(10); // 在末尾添加元素10
myList.push_front(5); // 在开头添加元素5

访问list中的元素

由于list不支持随机访问，遍历list需要使用迭代器：

1
2
3

for(auto it = myList.begin(); it != myList.end(); ++it) {
    std::cout << *it << " ";
}

或者使用范围for循环：

1
2
3

for(const auto& element : myList) {
    std::cout << element << " ";
}

删除元素

• 使用pop_back删除列表末尾的元素。
• 使用pop_front删除列表开头的元素。
• 使用erase删除指定位置的元素。

1
2

myList.pop_back(); // 删除末尾元素
myList.pop_front(); // 删除开头元素

插入元素

在指定位置插入元素可以使用insert方法，需要提供插入位置的迭代器和插入的值：

1
2
3

auto it = myList.begin();
std::advance(it, 2); // 将迭代器向前移动2个位置
myList.insert(it, 20); // 在第3个位置插入元素20

查找元素

由于list不支持随机访问，查找特定元素需要遍历整个列表：

1
2
3
4
5
6

auto it = std::find(myList.begin(), myList.end(), 20);
if(it != myList.end()) {
    std::cout << "Found " << *it << std::endl;
} else {
    std::cout << "Not found" << std::endl;
}

特点

• 动态大小：可以根据需要动态地添加或删除元素，容器大小不固定。
• 非连续存储：list的元素在内存中可能是非连续存储的，每个元素通过指针与前后元素连接。
• 双向遍历：支持正向和反向遍历。
• 高效插入和删除：在任何位置插入和删除元素都非常高效。

list适合于频繁插入和删除元素的场景，特别是在元素的中间位置。然而，如果需要频繁访问元素，其他支持随机访问的容器（如vector或deque）可能更加适合。

2.双端队列（deque）

​ 在C++标准模板库（STL）中，双端队列（deque，全名为double-ended queue）是一种具有动态大小的序列容器，它允许在容器的前端和后端快速插入和删除元素。与vector相比，deque提供了在容器两端操作元素的额外功能，而与list不同，它支持随机访问，即可以直接通过下标访问元素。

deque的基本用法

要使用deque，需要包含头文件<deque>。

1

#include <deque>

创建deque

你可以像下面这样创建一个deque：

1

std::deque<int> myDeque;

向deque中添加元素

• 使用push_back在队列末尾添加元素。
• 使用push_front在队列开头添加元素。

1
2

myDeque.push_back(10); // 在末尾添加元素10
myDeque.push_front(5); // 在开头添加元素5

访问deque中的元素

• 使用下标操作符[]直接访问元素，如myDeque[0]。
• 使用at方法访问元素，如myDeque.at(0)，它会进行边界检查。
• 使用迭代器遍历deque。

1
2
3
4
5
6
7
8

for(int i = 0; i < myDeque.size(); ++i) {
    std::cout << myDeque[i] << " ";
}

// 或者使用迭代器
for(auto it = myDeque.begin(); it != myDeque.end(); ++it) {
    std::cout << *it << " ";
}

删除元素

• 使用pop_back删除队列末尾的元素。
• 使用pop_front删除队列开头的元素。
• 使用erase删除指定位置的元素或元素范围。

1
2

myDeque.pop_back(); // 删除末尾元素
myDeque.pop_front(); // 删除开头元素

修改deque中的元素

可以直接通过下标或迭代器修改deque中的元素。

1
2
3
4

myDeque[0] = 20; // 修改第一个元素的值

auto it = myDeque.begin();
*it = 15; // 修改第一个元素的值

特点

• 动态大小：根据需要自动扩展和收缩。
• 随机访问：支持通过下标直接访问元素。
• 双端插入和删除：在容器的前端和后端插入和删除操作都很高效。
• 非连续存储：deque的实现通常是一系列固定大小的数组，这些数组的索引被保存在一个中央数据结构中。这种实现支持快速的随机访问，同时保持在两端插入和删除操作的高效性。

deque非常适合于需要频繁在两端添加或删除元素，同时又需要随机访问元素的场景。例如，它可以被用作队列或栈的实现基础，也适合作为滑动窗口算法的数据结构。

3.优先队列（priority_queue）

​ 在C++标准模板库（STL）中，priority_queue是一种容器适配器，它提供了队列的功能，其中每个元素都有一个优先级。元素被添加到任意位置，但访问元素时会按照优先级从最高到最低的顺序进行，这意味着你总是从队列中获取优先级最高的元素。

priority_queue默认使用std::less<T>作为比较函数，这意味着最大的元素会被视为优先级最高的元素。如果你想要改变顺序，使得最小的元素优先级最高，可以通过传递std::greater<T>作为第三个模板参数来实现。

priority_queue的基本用法

要使用priority_queue，需要包含头文件<queue>。

1

#include <queue>

创建priority_queue

你可以像下面这样创建一个默认的priority_queue（最大元素优先）：

1

std::priority_queue<int> myPQ;

如果想要最小元素优先，可以这样创建：

1

std::priority_queue<int, std::vector<int>, std::greater<int>> myMinPQ;

向priority_queue中添加元素

使用push方法向priority_queue中添加元素：

1
2
3

myPQ.push(10);
myPQ.push(5);
myPQ.push(20);

添加这些元素后，20会是优先级最高的元素。

访问priority_queue中的元素

由于priority_queue是一个适配器，它不提供遍历所有元素的能力。你只能访问优先级最高的元素：

1

int topElement = myPQ.top(); // 获取优先级最高的元素，这里是20

删除元素

使用pop方法删除优先级最高的元素：

1

myPQ.pop(); // 删除了20

检查priority_queue的大小

使用size方法检查priority_queue包含的元素数量：

1

size_t size = myPQ.size();

特点

• priority_queue通常通过堆（通常是二叉堆）来实现，提供了高效的元素插入和删除最高优先级元素的操作。
• 插入操作和删除最高优先级元素的操作的时间复杂度通常为O(log n)，其中n是priority_queue中元素的数量。
• priority_queue非常适合于那些需要频繁插入元素并且需要快速访问最高（或最低）优先级元素的场景，比如任务调度、带权图的算法（如Dijkstra算法）等。

通过这种方式，priority_queue可以在多种场景下高效地管理具有优先级的数据集合。

2.2.3 多重集合（multiset）

​ 在C++标准模板库（STL）中，multiset是一种关联容器，与set类似，它可以自动将元素排序，并且所有元素都会按照特定的排序标准进行排序。不同于set，multiset允许存储重复的元素。也就是说，你可以在multiset中有多个值完全相同的元素。

multiset的基本用法

要使用multiset，需要包含头文件<set>。

1

#include <set>

创建multiset

你可以像下面这样创建一个multiset：

1

std::multiset<int> myMultiset;

向multiset中添加元素

使用insert方法向multiset中添加元素：

1
2
3

myMultiset.insert(10);
myMultiset.insert(5);
myMultiset.insert(10); // 允许重复

在这个例子中，即使10已经存在于multiset中，第二次插入10依然有效，multiset中现在有两个10。

访问multiset中的元素

由于multiset不支持随机访问（如通过下标访问元素），所以必须使用迭代器来遍历multiset中的所有元素：

1
2
3

for(auto it = myMultiset.begin(); it != myMultiset.end(); ++it) {
    std::cout << *it << " ";
}

或者使用范围for循环：

1
2
3

for(const auto& element : myMultiset) {
    std::cout << element << " ";
}

删除元素

• 使用erase方法删除指定值的元素，这将删除multiset中所有值匹配的元素。
• 如果只想删除一个特定值的一个实例，可以先用find找到这个元素的迭代器，然后用erase删除：

1
2
3
4

auto it = myMultiset.find(10);
if(it != myMultiset.end()) {
    myMultiset.erase(it); // 删除一个值为10的元素
}

检查multiset的大小

使用size方法检查multiset包含的元素数量：

1

size_t size = myMultiset.size();

特点

• 自动排序：multiset的元素在插入时会自动排序。
• 允许重复元素：与set不同，multiset允许存储重复的元素。
• 高效的查找、插入和删除操作：与set相似，multiset的查找、插入和删除操作的时间复杂度通常为O(log n)，其中n是容器中元素的数量。

​ multiset非常适合于需要维护一个有序序列且序列中包含重复元素的场景。例如，在统计数据或进行范围查询时，multiset提供了一个既灵活又高效的解决方案。

2.2.4 映射（map），多重映射（multimap）

​ 在C++标准模板库（STL）中，map是一种关联容器，它存储键值对（key-value pairs），其中每个键都唯一地映射到一个值。map中的元素按照键的顺序排序，搜索、插入和删除操作的时间复杂度都是对数时间O(log n)，其中n是map中元素的数量。map底层通常实现为红黑树。

map的基本用法

要使用map，需要包含头文件<map>。

1

#include <map>

创建map

你可以像下面这样创建一个map：

1

std::map<std::string, int> myMap;

这里创建了一个map，其键（key）类型为std::string，值（value）类型为int。

向map中添加元素

使用operator[]或insert方法向map中添加元素：

1
2

myMap["apple"] = 5;
myMap.insert(std::make_pair("banana", 3));

如果使用operator[]添加一个已经存在的键，其对应的值会被新值替换。如果使用insert方法，当键已存在时，插入操作会失败。

访问map中的元素

• 使用operator[]访问元素：

1

std::cout << myMap["apple"] << std::endl; // 输出5

• 使用at方法访问元素（如果键不存在，会抛出std::out_of_range异常）：

1

std::cout << myMap.at("apple") << std::endl; // 输出5

• 使用迭代器遍历map：

1
2
3

for(auto it = myMap.begin(); it != myMap.end(); ++it) {
    std::cout << it->first << ": " << it->second << std::endl;
}

• 或者使用范围for循环：

1
2
3

for(const auto& pair : myMap) {
    std::cout << pair.first << ": " << pair.second << std::endl;
}

删除元素

• 使用erase方法删除指定键的元素：

1

myMap.erase("apple");

检查map中的元素数量

使用size方法检查map包含的元素数量：

1

size_t size = myMap.size();

特点

• 唯一键：每个键在map中唯一对应一个值。
• 自动排序：元素会根据键自动排序，排序方式可以通过自定义比较函数来指定。
• 直接访问：可以直接通过键访问对应的值。
• 高效的查找、插入和删除：时间复杂度为O(log n)。

map适合于需要快速查找元素（基于键）、保持元素有序且键值唯一的场景。例如，它常用于实现字典、数据库索引等。

​ 在C++标准模板库（STL）中，multimap是一种关联容器，与map相似，它存储的是键值对（key-value pairs）。不同之处在于，multimap允许多个元素拥有相同的键，也就是说，同一个键可以映射到多个值。这使得multimap非常适合处理具有非唯一键的情况。

multimap的基本用法

要使用multimap，需要包含头文件<map>。

1

#include <map>

创建multimap

你可以像下面这样创建一个multimap：

1

std::multimap<std::string, int> myMultimap;

在这个例子中，myMultimap的键类型是std::string，值类型是int。

向multimap中添加元素

使用insert方法向multimap中添加元素：

1
2
3

myMultimap.insert(std::make_pair("apple", 5));
myMultimap.insert(std::pair<std::string, int>("apple", 10)); // 同一个键，不同的值
myMultimap.insert({"banana", 3});

访问multimap中的元素

由于multimap允许键重复，不能使用operator[]来访问元素。要访问multimap中的元素，通常使用迭代器遍历：

1
2
3

for(auto it = myMultimap.begin(); it != myMultimap.end(); ++it) {
    std::cout << it->first << ": " << it->second << std::endl;
}

如果你只对特定键的所有值感兴趣，可以使用equal_range方法或者lower_bound和upper_bound来获取某个键对应的所有值的范围：

1
2
3
4

auto range = myMultimap.equal_range("apple");
for(auto it = range.first; it != range.second; ++it) {
    std::cout << it->first << " => " << it->second << '\n';
}

删除元素

• 使用erase方法删除指定键的所有元素：

1

myMultimap.erase("apple");

• 如果想删除某个具体的键值对，需要先找到这个键值对对应的迭代器，然后删除：

1
2
3
4

auto it = myMultimap.find("banana");
if (it != myMultimap.end()) {
    myMultimap.erase(it);
}

检查multimap的大小

使用size方法检查multimap包含的元素数量：

1

size_t size = myMultimap.size();

特点

• 非唯一键：multimap允许多个元素共享同一个键。
• 自动排序：multimap中的元素会根据键自动排序，排序规则可以通过自定义比较函数来指定。
• 高效的查找、插入和删除：与map类似，multimap的查找、插入和删除操作的时间复杂度也是O(log n)。

​ multimap适合于需要根据键快速查找元素且元素的键可能不唯一的场景。例如，可以用multimap来存储一个公司员工的ID和他们所在的部门之间的映射，其中部门名称作为键，员工ID作为值，因为一个部门可以有多个员工。

2.2.5 对（pair），元组（tuple）

​ 在C++标准模板库（STL）中，pair是一个非常简单的容器，它可以存储两个值，这两个值可以是不同的类型。pair广泛用于那些需要将两个值视为单个单元的场景，例如，在map和multimap中存储键值对，或者当函数需要返回两个值时。

pair的基本用法

要使用pair，需要包含头文件<utility>。

1

#include <utility>

创建pair

你可以使用多种方法来创建一个pair：

1

std::pair<std::string, int> myPair("apple", 5);

或者使用std::make_pair函数：

1

auto myPair = std::make_pair("apple", 5);

访问pair中的元素

pair中的元素可以通过.first和.second成员访问：

1

std::cout << "The fruit is " << myPair.first << " and its count is " << myPair.second << std::endl;

修改pair中的元素

你可以直接修改pair中的元素：

1
2

myPair.first = "banana";
myPair.second = 10;

比较pair

pair支持比较操作（如==, !=, <, <=, >, >=）。比较是首先基于.first成员的，如果它们相等，则基于.second成员的。

1
2
3
4
5
6
7
8

std::pair<int, int> pair1 = std::make_pair(1, 5);
std::pair<int, int> pair2 = std::make_pair(1, 10);

if (pair1 < pair2) {
    std::cout << "pair1 is less than pair2" << std::endl;
} else {
    std::cout << "pair1 is not less than pair2" << std::endl;
}

在这个例子中，pair1小于pair2，因为它们的.first成员相同，但pair1的.second成员小于pair2的.second成员。

pair的使用场景

• 在map和multimap中，每个元素都是一个pair，.first是键，.second是值。
• 函数通过pair返回多个值。
• 在算法和数据结构中，pair常用于将两个数据组合成单个单元，例如在图算法中表示边的权重。

pair是C++中一个非常基础而强大的工具，它简单却能在多种场合发挥重要作用。

​ 在C++标准模板库（STL）中，tuple是一个可以存储不同类型值的固定大小的容器。与pair相比，tuple更加通用，它可以容纳两个以上的元素。tuple非常适用于那些需要将一组值聚合成单一对象，但又不想创建全新结构体或类的场景。

tuple的基本用法

要使用tuple，需要包含头文件<tuple>。

1

#include <tuple>

创建tuple

你可以使用多种方法来创建一个tuple：

1

std::tuple<std::string, int, double> myTuple("apple", 5, 0.99);

或者使用std::make_tuple函数：

1

auto myTuple = std::make_tuple("apple", 5, 0.99);

访问tuple中的元素

要访问tuple中的元素，可以使用std::get：

1
2
3
4
5

std::string fruit = std::get<0>(myTuple);
int count = std::get<1>(myTuple);
double price = std::get<2>(myTuple);

std::cout << "The fruit is " << fruit << ", count is " << count << ", price is " << price << std::endl;

修改tuple中的元素

与pair类似，你可以通过std::get直接修改tuple中的元素：

1

std::get<1>(myTuple) = 10; // 修改数量为10

tuple的其他功能

• 比较操作：tuple支持全面的比较操作（==, !=, <, <=, >, >=），比较是从第一个元素开始逐个进行的，直到找到不相等的元素。
• tuple_size：可以通过std::tuple_size<decltype(tuple)>::value来获取tuple中元素的数量。
• tuple_cat：可以使用std::tuple_cat来将两个或多个tuple合并成一个新的tuple。

示例：合并tuple

1
2
3
4
5

std::tuple<int, std::string> tuple1 = std::make_tuple(1, "apple");
std::tuple<double, char> tuple2 = std::make_tuple(0.99, 'A');

auto tuple3 = std::tuple_cat(tuple1, tuple2);
// tuple3 现在包含：int, string, double, char

tuple的使用场景

• 函数返回多个值时，tuple可以容纳这些值而无需定义新的结构体或类。
• 在泛型编程中，当需要处理不同类型集合的数据时。
• 在数据结构和算法中，将多个数据组合成单一对象，例如图的边（可以包含边的两个顶点和权重）。

tuple提供了一种灵活的方式来处理多个不同类型的数据，使得数据的聚合和操作更加便捷。

3.1 线性结构

3.1.1 双端栈

​ 双端栈（Double-ended Stack，也被称为双栈）是一种数据结构，它允许从数据结构的两端进行push和pop操作。这种结构结合了栈和队列的部分特性，使得它可以在两端进行操作。双端栈不是C++标准模板库（STL）中的一个直接数据结构，但可以使用两个栈或者双端队列（deque）来实现。

使用两个栈实现双端栈

​ 使用两个栈实现双端栈的基本思想是：一个栈用于管理一端的入栈（push）和出栈（pop）操作，另一个栈用于管理另一端的操作。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include <stack>
#include <iostream>
#include <cassert>
using namespace std;

template <typename T>
class DoubleEndedStack {
private:
    std::stack<T> stack1;
    std::stack<T> stack2;

public:
    // 向第一端添加元素
    void push_front(const T& value) {
        stack1.push(value);
    }

    // 从第一端移除元素
    void pop_front() {
        assert(!stack1.empty()); // 确保栈不为空
        stack1.pop();
    }

    // 向第二端添加元素
    void push_back(const T& value) {
        stack2.push(value);
    }

    // 从第二端移除元素
    void pop_back() {
        assert(!stack2.empty()); // 确保栈不为空
        stack2.pop();
    }
};

使用deque实现双端栈

由于双端队列（deque）本身就支持从两端进行push和pop操作，所以使用deque实现双端栈会更加直接和简洁。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

#include <deque>
#include <iostream>
#include <cassert>
using namespace std;

template <typename T>
class DoubleEndedStack {
private:
    std::deque<T> deque;

public:
    // 向第一端添加元素
    void push_front(const T& value) {
        deque.push_front(value);
    }

    // 从第一端移除元素
    void pop_front() {
        assert(!deque.empty()); // 确保deque不为空
        deque.pop_front();
    }

    // 向第二端添加元素
    void push_back(const T& value) {
        deque.push_back(value);
    }

    // 从第二端移除元素
    void pop_back() {
        assert(!deque.empty()); // 确保deque不为空
        deque.pop_back();
    }
};

使用场景

​ 双端栈的使用场景相对特殊，但在某些算法设计中非常有用，特别是在需要同时对数据的两端进行操作的情况下。例如，在某些特定的算法问题中，可能需要同时从两端添加或移除数据，以保持数据结构的平衡或实现特定的数据处理逻辑。

下面是一个使用双端栈的示例代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include <iostream>
#include <deque>

using namespace std;

int main() {
    deque<int> myDeque;

    // push elements to back of deque
    myDeque.push_back(10);
    myDeque.push_back(20);
    myDeque.push_back(30);

    // push elements to front of deque
    myDeque.push_front(5);
    myDeque.push_front(15);

    // output deque contents
    cout << "deque contents: ";
    for (auto i : myDeque) {
        cout << i << " ";
    }
    cout << endl;

    // pop element from back of deque
    myDeque.pop_back();

    // pop element from front of deque
    myDeque.pop_front();

    // output deque contents
    cout << "deque contents: ";
    for (auto i : myDeque) {
        cout << i << " ";
    }
    cout << endl;

    return 0;
}

​ 在上面的示例中，我们使用了deque容器来实现一个双端栈。首先将元素10、20、30依次插入到双端栈的尾部，然后将元素5、15依次插入到双端栈的头部。输出双端栈的内容，可以看到元素的顺序是15 5 10 20 30。接着分别从双端栈的尾部和头部删除一个元素，输出双端栈的内容，可以看到元素的顺序变为5 10 20。

3.1.2 双端队列

​ 在C++标准模板库（STL）中，双端队列（deque，全称为double-ended queue）是一种序列容器，它支持在两端高效地插入和删除元素。与vector相比，deque不仅能够动态地增长和缩小，而且能够在容器的前端插入元素，而vector只能在后端插入元素（尽管从技术上来讲，vector也可以在前端插入元素，但这样做的效率非常低）。与list相比，deque支持随机访问，这意味着你可以直接访问任何位置的元素，而不需要从头开始遍历容器。

deque的基本用法

要使用deque，你需要包含头文件<deque>。

1

#include <deque>

创建deque

你可以像下面这样创建一个deque：

1

std::deque<int> myDeque;

向deque中添加元素

• 在末尾添加元素：push_back()
• 在开头添加元素：push_front()

1
2

myDeque.push_back(10); // 在末尾添加元素10
myDeque.push_front(5); // 在开头添加元素5

访问deque中的元素

• 使用下标操作符：myDeque[0]
• 使用at()方法：myDeque.at(0)，它会检查下标是否越界。
• 使用迭代器遍历deque。

1
2
3

for (int& element : myDeque) {
    std::cout << element << " ";
}

删除deque中的元素

• 从末尾删除元素：pop_back()
• 从开头删除元素：pop_front()

1
2

myDeque.pop_back(); // 删除末尾元素
myDeque.pop_front(); // 删除开头元素

deque的特点

• 动态大小：根据需要自动扩展和缩小。
• 双端操作：支持在容器的前端和后端快速插入和删除元素。
• 随机访问：支持通过下标直接访问元素，与vector类似，但性能略低于vector。
• 非连续存储：deque可能由多个分散的内存块组成，保证了在两端操作的高效性，但也意味着与vector相比，随机访问的性能稍差。

使用场景

​ deque非常适合于那些需要从两端添加或移除元素的场景。例如，在需要一个队列但又频繁在队列前端插入元素的场合，或者在需要随机访问元素同时又需要在两端动态调整大小的场合，deque都是一个很好的选择。双端队列（deque，即double-ended queue），是一种可以在两端进行插入和删除操作的数据结构，支持队列和栈的所有操作。它类似于双向链表，但在实现上通常使用数组或向量实现，因此可以更高效地支持随机访问操作。

​ 下面是一个使用双端队列的示例代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

#include <iostream>
#include <deque>
using namespace std;

int main() {
    deque<int> myDeque;

    // push elements to back of deque
    myDeque.push_back(10);
    myDeque.push_back(20);
    myDeque.push_back(30);

    // push elements to front of deque
    myDeque.push_front(5);
    myDeque.push_front(15);

    // output deque contents
    cout << "deque contents: ";
    for (auto i : myDeque) {
        cout << i << " ";
    }
    cout << endl;

    // pop element from back of deque
    myDeque.pop_back();

    // pop element from front of deque
    myDeque.pop_front();

    // output deque contents
    cout << "deque contents: ";
    for (auto i : myDeque) {
        cout << i << " ";
    }
    cout << endl;

    return 0;
}

​ 在上面的示例中，我们使用了deque容器来实现一个双端队列。首先将元素10、20、30依次插入到双端队列的尾部，然后将元素5、15依次插入到双端队列的头部。输出双端队列的内容，可以看到元素的顺序是15 5 10 20 30。接着分别从双端队列的尾部和头部删除一个元素，输出双端队列的内容，可以看到元素的顺序变为5 10 20。

3.1.3 有序队列

​ 在C++中，"有序队列"一词并不是指一个特定的标准库容器，但这个概念可以通过几种不同的方式实现，根据你的需求选择最合适的实现方式。通常，当我们谈论有序队列时，我们可能是在指一种数据结构，它可以维护元素的某种排序顺序，同时允许高效地插入新元素、删除元素以及访问队列中的最小或最大元素。以下是几种实现有序队列概念的方法：

使用std::priority_queue

std::priority_queue是C++ STL中的一个容器适配器，它提供了一种方式来维护一个集合，这个集合总是被排序以确保最大元素（或根据提供的比较函数，可能是最小元素）总是位于“顶部”。这使得它非常适合实现最大堆或最小堆。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#include <iostream>
#include <queue>
using namespace std;

int main() {
    std::priority_queue<int> maxHeap;
    // 对于最小堆，可以这样定义：std::priority_queue<int, std::vector<int>, std::greater<int>>

    maxHeap.push(1);
    maxHeap.push(5);
    maxHeap.push(3);

    std::cout << "Max element: " << maxHeap.top() << std::endl;

    maxHeap.pop(); // 移除最大元素
}

使用std::set或std::multiset

std::set和std::multiset是基于红黑树实现的，可以自动排序其元素。与priority_queue不同，这些容器允许你遍历元素，set保证了元素的唯一性，而multiset允许重复元素。这些容器非常适合当你需要一个总是排序的集合，并且可能需要访问除了最小或最大元素以外的元素。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

#include <iostream>
#include <set>
using namespace std;

int main() {
    std::set<int> orderedSet;

    orderedSet.insert(3);
    orderedSet.insert(1);
    orderedSet.insert(4);

    std::cout << "Elements in order: ";
    for (int elem : orderedSet) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
}

选择正确的数据结构

• 如果你的主要需求是快速访问、插入和删除最大元素（或最小元素），priority_queue可能是最好的选择。
• 如果你需要保持元素的排序顺序，并且需要频繁地遍历这些元素或者操作除了最大或最小元素以外的元素，set或multiset可能更适合。
• 如果需要允许重复元素并保持排序，应选择multiset。
• 如果除了有序性之外，还需要通过索引快速访问元素，可以考虑使用std::vector或std::deque，在每次插入或删除操作后进行排序，虽然这在效率上通常不是最佳选择。

选择哪种实现取决于你的具体需求，包括你需要哪种类型的排序、是否需要遍历元素、以及对插入和删除操作的性能要求。

3.1.4 优先队列

​ 在C++中，priority_queue是一种容器适配器，设计用于保持其元素排序的状态。默认情况下，它构造了一个最大堆，这意味着队列的顶部总是保持最大元素。通过这种方式，priority_queue提供了快速访问集合中最大元素的能力，同时允许在对数时间内插入新元素和移除最大元素。

priority_queue的基本用法

要使用priority_queue，你需要包含头文件<queue>。

1
2

#include <iostream>
#include <queue>

创建priority_queue

你可以像下面这样创建一个priority_queue：

1

std::priority_queue<int> pq;

这将创建一个空的priority_queue，用于存储int类型的元素，并且元素将按照从大到小的顺序排序。

向priority_queue中添加元素

使用push()方法向priority_queue中添加元素：

1
2
3

pq.push(30);
pq.push(10);
pq.push(20);

访问priority_queue中的最大元素

使用top()方法访问priority_queue中的最大元素：

1

std::cout << "The largest element is " << pq.top() << std::endl;

移除priority_queue中的最大元素

使用pop()方法移除priority_queue中的最大元素：

1

pq.pop();

自定义排序

如果你想让priority_queue以不同的顺序排序（例如，构造一个最小堆），你可以在声明时提供额外的参数：

1

std::priority_queue<int, std::vector<int>, std::greater<int>> minPq;

这将创建一个最小堆，使得队列的顶部总是保持最小元素。

priority_queue的使用场景

priority_queue非常适合于需要快速访问和移除最大（或最小）元素的场景，如：

• 算法中的贪心策略，比如Dijkstra算法或Prim算法中使用最小堆来快速找到最小边。
• 任务调度，其中任务有不同的优先级，并且需要首先执行最高优先级的任务。
• 实时数据处理，如数据流中寻找最大的N个元素。

通过为priority_queue提供不同的比较函数，你可以灵活地控制元素的排序方式，使其适应各种不同的需求。

以下是一个示例程序，使用priority_queue实现了一个按照整数值从大到小排序的优先队列：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
  priority_queue<int, vector<int>, less<int>> pq;
  pq.push(5);
  pq.push(2);
  pq.push(7);
  pq.push(1);
  pq.push(8);

  while (!pq.empty()) {
    cout << pq.top() << " ";
    pq.pop();
  }

  return 0;
}

输出结果为：8 7 5 2 1

3.1.5 倍增表（ST表）

​ 倍增表（Sparse Table，简称ST表）是一种用于解决区间查询问题的数据结构，特别适合处理静态数据的区间最小值查询（RMQ问题）、区间最大值查询等问题。ST表的主要优势在于它可以在O(1)的时间复杂度内回答任何区间查询，前提是数据是静态的，即数据在预处理之后不会再发生变化。ST表的预处理时间复杂度是O(NlogN)，其中N是数组的大小。

ST表的工作原理

​ ST表利用了动态规划的思想，预处理出一个二维数组dp[N][K]，其中dp[i][j]表示从第i个元素开始，长度为2^j的区间内的最小（或最大）元素。N是原数组的大小，K是满足2^K <= N的最大整数。

ST表的预处理

以最小值查询为例，预处理代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

void buildST(const std::vector<int>& arr, std::vector<std::vector<int>>& dp) {
    int N = arr.size();
    int K = std::log2(N) + 1;
    dp.assign(N, std::vector<int>(K + 1, 0));

    // 初始化dp数组
    for (int i = 0; i < N; i++) {
        dp[i][0] = arr[i];
    }

    // 动态规划预处理
    for (int j = 1; j <= K; j++) {
        for (int i = 0; i + (1 << j) <= N; i++) {
            dp[i][j] = std::min(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
        }
    }
}

ST表的查询

查询区间[l, r]内的最小值：

1
2
3
4

int queryST(const std::vector<std::vector<int>>& dp, int l, int r) {
    int j = std::log2(r - l + 1);
    return std::min(dp[l][j], dp[r - (1 << j) + 1][j]);
}

优点

• 查询时间复杂度为O(1)，非常适合处理大量的区间查询问题。
• 实现相对简单，易于理解。

缺点

• 只能用于静态数据的查询，如果数据有更新，需要重新预处理。
• 预处理的空间复杂度为O(NlogN)，对于非常大的数据量可能会有较大的内存开销。

应用场景

​ ST表适用于需要频繁查询静态数组的区间最小值、最大值、最大公约数等问题，如在线处理多个区间查询的场景。它在竞赛编程和一些对查询性能要求高的应用中非常有用。

​ 以下是一个使用ST表实现静态区间最值查询的示例代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

#include <iostream>
#include <cmath>
using namespace std;

const int MAXN = 100000;
const int MAXLOG = 20;

int n, q;
int a[MAXN + 1];
int st[MAXN + 1][MAXLOG + 1];

void build_st() {
  int k = log2(n);
  for (int i = 1; i <= n; i++) {
    st[i][0] = a[i];
  }
  for (int j = 1; j <= k; j++) {
    for (int i = 1; i + (1 << j) - 1 <= n; i++) {
      st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
    }
  }
}

int query(int l, int r) {
  int k = log2(r - l + 1);
  return min(st[l][k], st[r - (1 << k) + 1][k]);
}

int main() {
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }

  build_st();

  for (int i = 1; i <= q; i++) {
    int l, r;
    cin >> l >> r;
    cout << query(l, r) << endl;
  }

  return 0;
}

​ 其中，build_st()函数用于构造ST表，query(l, r)函数用于查询区间\([l, r]\)的最值。时间复杂度为\(O(nlogn)\)，空间复杂度为\(O(nlogn)\)。

3.2 集合与森林

3.2.1 等价类

​ 在数学和计算机科学中，等价类（Equivalence Class）是指在集合分割中，通过某种等价关系形成的子集。等价类是根据等价关系将集合中元素进行分组的一种方法，每个分组中的元素对于这种关系来说是不可区分的。

等价关系

要理解等价类，首先需要明白等价关系的概念。在集合A上的一个等价关系是一个二元关系，满足以下三个条件：

1. 自反性（Reflexivity）：对于所有a属于A，a与a是等价的。
2. 对称性（Symmetry）：对于所有a和b属于A，如果a与b是等价的，则b与a也是等价的。
3. 传递性（Transitivity）：对于所有a、b和c属于A，如果a与b是等价的，且b与c是等价的，则a与c也是等价的。

等价类的定义

给定一个集合A和一个在A上的等价关系~，A中的一个元素a的等价类是由所有与a等价的元素组成的子集。通常用[a]表示a的等价类。

等价类的性质

• 分割性（Partitioning）：等价关系将集合A分割成互不相交的子集，这些子集称为A的等价类。每个元素a属于A都恰好属于一个等价类。
• 划分（Partition）：集合A的所有等价类的集合形成了A的一个划分。

示例

假设有一个集合A = {1, 2, 3, 4, 5}，定义等价关系~为“模2同余”，即对于A中的任意两个数a和b，如果a和b除以2的余数相同，则它们是等价的。根据这个等价关系，集合A被分为两个等价类：

• [1] = {1, 3, 5}：包含所有除以2余1的元素。
• [2] = {2, 4}：包含所有除以2余0的元素。

应用

​ 等价类的概念在数学的很多分支中都有应用，包括代数、几何和逻辑等。在计算机科学中，等价类被用于算法设计、数据结构、程序验证和软件测试等多个领域，如等价类划分（Equivalence Partitioning）是一种常用的软件测试技术。

​ 以下是一个基于数组实现等价类的示例代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 1005;

int fa[MAXN];

// 初始化并查集，每个元素的父节点初始化为它本身
void init(int n) {
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
}

// 查找元素x所在的集合的代表元素
int find(int x) {
    if (fa[x] == x) {
        return x;
    }
    return fa[x] = find(fa[x]);  // 路径压缩
}

// 合并元素x和y所在的集合
void unite(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx != fy) {
        fa[fx] = fy;
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    init(n);

    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        unite(a, b);
    }

    vector<int> e[MAXN];  // 存储每个等价类的元素
    for (int i = 1; i <= n; i++) {
        int f = find(i);  // 找到i所在的集合的代表元素
        e[f].push_back(i);  // 将i加入代表元素所在的等价类中
    }

    for (int i = 1; i <= n; i++) {
        if (fa[i] == i) {  // 如果i是代表元素，则输出i所在的等价类
            cout << "等价类" << i << "中的元素为：";
            for (int j = 0; j < e[i].size(); j++) {
                cout << e[i][j] << " ";
            }
            cout << endl;
        }
    }

    return 0;
}

​ 该代码通过并查集维护元素之间的等价关系，最后将每个等价类的元素存储在一个vector中输出。

3.2.2 并查集

​ 并查集（Disjoint Set Union，简称DSU）是一种非常实用的数据结构，主要用于处理一些不交集的合并及查询问题。它支持两种基本操作：查找（Find）和合并（Union）。通过这两种操作，可以非常高效地解决动态连通性问题，例如网络中的连接状态、数学中的集合分类问题等。

基本概念

• 查找（Find）：确定某个元素属于哪一个子集。这通常通过找到该元素所在集合的“代表元”（也叫根节点）来实现。
• 合并（Union）：将两个子集合并成一个集合。这通常意味着将两个集合的代表元链接起来。

数据结构

并查集通常用一维数组实现。每个元素的父节点信息存储在数组中，根节点的父节点指向它自己。因此，从任何一个节点开始，通过连续查找父节点，最终都能找到根节点。

操作实现

初始化

初始化时，每个元素构成一个独立的集合，指向自己作为自己的父节点。

1
2
3
4
5

void makeSet(int n, vector<int>& parent) {
    for(int i = 0; i < n; i++) {
        parent[i] = i;
    }
}

查找

查找操作通过递归或循环查找元素的根节点来实现。

1
2
3
4
5
6

int find(int x, vector<int>& parent) {
    if(x != parent[x]) {
        parent[x] = find(parent[x], parent); // 路径压缩
    }
    return parent[x];
}

合并

合并操作首先找到两个元素的根节点，如果根节点不同，将其中一个根节点的父节点指向另一个根节点。

1
2
3
4
5
6
7

void unionSets(int x, int y, vector<int>& parent) {
    int rootX = find(x, parent);
    int rootY = find(y, parent);
    if(rootX != rootY) {
        parent[rootX] = rootY; // 或者根据树的高度或大小选择合并方向
    }
}

路径压缩

在查找过程中，路径压缩技术可以减少后续查找操作的时间，通过将查找路径上的每个节点直接链接到根节点来实现。

按秩合并

按秩合并是另一种优化技术，它通过保持树的高度最小化来减少查找时间。常见的做法是总是将较矮的树连接到较高的树上。

应用

并查集在解决动态连通性问题中非常高效，常见的应用场景包括：

• 社交网络中的朋友圈问题
• 图的连通分量问题
• 最小生成树的Kruskal算法
• 等价关系和分类问题

并查集是算法竞赛和某些实际应用中的常用工具，因为它简洁且高效。

以下是并查集的 C++ 代码示例，使用数组实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

#include <iostream>
#include <vector>
using namespace std;

const int N = 100010;

int n, m;
int p[N];  // p[x] 表示元素 x 的父节点，如果 p[x] = x，则 x 为该集合的代表元素

// 初始化
void init() {
    for (int i = 1; i <= n; i++) p[i] = i;
}

// 查找元素 x 所在集合的代表元素
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

// 合并两个集合
void merge(int a, int b) {
    int pa = find(a), pb = find(b);
    if (pa != pb) p[pa] = pb;
}

int main() {
    cin >> n >> m;
    init();
    while (m--) {
        int a, b;
        cin >> a >> b;
        merge(a, b);
    }

    // 输出各个元素所在集合的代表元素
    vector<int> ans;
    for (int i = 1; i <= n; i++) {
        if (p[i] == i) ans.push_back(i);
    }
    cout << ans.size() << endl;
    return 0;
}

​ 该代码实现了并查集的三个基本操作：初始化、查找、合并。初始化时将每个元素单独作为一个集合，即将每个元素的父节点设为它本身；查找时可以一路往上找到根节点，即 p[x]=x 的元素；合并时将两个集合的代表元素的父节点指向另一个集合的代表元素。

​ 在本代码中，输入的第一行为元素个数 n 和操作次数 m，接下来 m 行每行两个数表示进行一次合并操作。输出各个元素所在集合的代表元素的个数。

注意：在实际使用中，需要根据具体情况对并查集进行优化，例如按秩合并、路径压缩等。

3.2.3 树与二叉树的转化——孩子兄弟表示法

​ 孩子兄弟表示法，也称为左孩子右兄弟表示法，是一种将普通树（如N叉树）转化为二叉树的技巧。这种表示法的核心思想是使用二叉树的结构来模拟普通树，其中每个节点最多有两个指针：

• 左指针（Left Child）指向该节点的第一个孩子节点。
• 右指针（Right Sibling）指向该节点的兄弟节点，即与该节点有共同父节点的下一个节点。

转化规则

1. 左指针：如果节点X在原始树中有孩子，那么在转化后的二叉树中，X的左指针指向它的第一个孩子。
2. 右指针：如果节点X在原始树中有兄弟，那么在转化后的二叉树中，X的右指针指向它的下一个兄弟。

通过这种方式，原始树中的任何节点在转化后的二叉树中都保持了其孩子和兄弟之间的关系。

示例

假设有一个N叉树，其结构如下：

1
2
3
4
5

       A
     / | \
    B  C  D
   / \    |
  E   F   G

使用孩子兄弟表示法转化为二叉树后，结构变为：

1
2
3
4
5

    A
   /
  B - C - D
 /         \
E - F       G

这里，-表示兄弟关系（右指针），垂直线表示父子关系（左指针）。

优点

​ 孩子兄弟表示法使得普通树的很多操作能够利用二叉树的算法来实现，例如，遍历、查找等，从而提高了算法的复用性。此外，这种表示法只需要两个指针就能表示N叉树的结构，有时可以减少存储空间的消耗。

缺点

​ 在某些情况下，如当原始树的结构非常不平衡时，使用孩子兄弟表示法转化后的二叉树可能会变得非常“偏斜”，这可能会对某些操作的效率产生影响。

应用

​ 孩子兄弟表示法在多叉树和二叉树之间的转换、树的存储、以及树的遍历等算法的实现中有着广泛的应用。尤其是在需要将树结构保存到文件或数据库中时，这种表示法能够简化结构，使得树的恢复更为直接。

下面是一个例子，展示了如何使用孩子兄弟表示法表示一棵树：

1
2
3
4
5
6
7

      A
     / \
    B   C
   / \   \
  D   E   F
         / \
        G   H

使用孩子兄弟表示法，可以将这棵树转化为以下二叉树：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

           A
          /
         B
        / \
       D   E
            \
             C
              \
               F
              / \
             G   H

以下是一个使用孩子兄弟表示法表示树的示例代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57