返回：0200 C++总目录 · 上一课：0208 Chap8 多态性 · 下一课：0210 Chap10 泛型程序设计与C++标准模板库

1、资料清单

资料 内容 入口
教材 《C++语言程序设计（第4版）》Chap9，原书页码 362-413 抽取 Markdown 下载
课件 Chap9 课件，位于本地郑莉 C++ 资料目录 本地资料夹
例题源代码 C++V5 源代码 下载
VS2019 工程 C++V5 VS2019 solution 下载

Chap9 的主线是模板 → 数组类 → 链表 → 栈 → 队列 → 双端队列 → 二叉树。这一章是数据结构课程的入口：先学会把一组对象组织起来，再考虑它们的访问、插入、删除和遍历规则。

2、颜色标注

颜色 含义 使用位置
蓝色 核心术语、定义 群体类、线性结构、栈、队列、树
绿色 推荐写法、主线 模板复用、RAII、STL 容器适配器
黄色 易错点、边界条件 数组越界、空栈访问、空队列访问、链表指针
红色 不建议做法 手写裸指针后忘记释放、在空容器上调用 top() / front()

3、学习目标

目标 要会到什么程度
群体类 理解为什么需要把多个对象组织成一个整体
模板 会写简单函数模板和类模板，知道模板用于类型复用
数组类 理解动态数组、越界检查、复制和扩容
链表 理解节点、单链表、双向链表和指针连接关系
栈 掌握后进先出，熟悉 std::stack 的常用接口
队列 掌握先进先出，熟悉 std::queue 的常用接口
双端队列 知道 std::deque 可在两端高效插入删除
二叉树 理解根、左右子树、深度和简单建树

4、章节目录

小节 内容 本节关键词
9.1 函数模板与类模板 泛型、类型参数
9.2 线性群体 顺序访问、线性结构
9.3 数组类 动态数组、下标访问、扩容
9.4 链表类 节点、指针、插入、删除
9.5 栈类 LIFO、push、pop、top
9.6 队列类 FIFO、front、back
9.7 双端队列 deque、两端操作、迭代器
9.8 二叉树 根节点、左右孩子、递归释放

5、群体类与数据结构

群体类用来表示一组对象。它解决的问题不是“一个对象有什么属性”，而是“多个对象如何组织、访问和修改”。

结构 访问特点 常见操作
数组 连续存储，支持随机访问 下标访问、遍历、扩容
链表 非连续存储，通过指针连接 插入、删除、顺序遍历
栈 只能访问栈顶 入栈、出栈、取栈顶
队列 队尾入队，队头出队 入队、出队、取队头/队尾
双端队列 两端都能插入删除 头插、尾插、头删、尾删
树 层次结构 建树、遍历、递归处理

复盘时可以把本章当作数据结构的预热：C++ 语法层面关注模板、类、动态内存；数据结构层面关注存储方式和操作规则。

6、模板基础

模板让同一份代码适配多种类型。

6.1 函数模板

1
2
3
4
template <typename T>
T maxValue(const T& a, const T& b) {
    return a < b ? b : a;
}

调用：

1
2
std::cout << maxValue(3, 5) << '\n';
std::cout << maxValue(3.14, 2.71) << '\n';

6.2 类模板

1
2
3
4
5
6
7
8
9
10
11
12
template <typename T>
class Box {
public:
    explicit Box(const T& value) : value_(value) {}

    const T& value() const {
        return value_;
    }

private:
    T value_;
};

调用：

1
2
Box<int> intBox(10);
Box<std::string> stringBox("C++");

模板代码通常要放在头文件里。因为编译器需要在看到具体类型时生成对应版本的代码。

7、数组类

数组类的目标是把 C 风格数组封装成一个更安全的类。

它至少应该解决三件事：

问题 数组类的处理方式
动态申请空间 构造函数申请，析构函数释放
下标越界 operator[] 中检查范围
对象复制 拷贝构造和赋值运算符执行深拷贝

一个现代 C++ 版本的 Array 可以这样写：

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
62
63
64
#include <algorithm>
#include <cstddef>
#include <memory>
#include <stdexcept>

template <typename T>
class Array {
public:
    explicit Array(std::size_t size = 50)
        : size_(size), data_(std::make_unique<T[]>(size)) {
        if (size == 0) {
            throw std::invalid_argument("array size must be positive");
        }
    }

    Array(const Array& other) : Array(other.size_) {
        std::copy(other.data_.get(), other.data_.get() + size_, data_.get());
    }

    Array& operator=(Array other) {
        swap(other);
        return *this;
    }

    T& operator[](std::size_t index) {
        if (index >= size_) {
            throw std::out_of_range("array index out of range");
        }
        return data_[index];
    }

    const T& operator[](std::size_t index) const {
        if (index >= size_) {
            throw std::out_of_range("array index out of range");
        }
        return data_[index];
    }

    std::size_t size() const {
        return size_;
    }

    void resize(std::size_t newSize) {
        if (newSize == 0) {
            throw std::invalid_argument("array size must be positive");
        }

        auto newData = std::make_unique<T[]>(newSize);
        const std::size_t count = std::min(size_, newSize);
        std::copy(data_.get(), data_.get() + count, newData.get());

        data_ = std::move(newData);
        size_ = newSize;
    }

    void swap(Array& other) noexcept {
        std::swap(size_, other.size_);
        data_.swap(other.data_);
    }

private:
    std::size_t size_;
    std::unique_ptr<T[]> data_;
};

和教材旧版本相比，这里用 std::unique_ptr<T[]> 管理动态数组，避免手写 delete[] 时漏掉释放。

8、链表

链表由一个个节点组成。每个节点通常包含两部分：

部分 作用
数据域 保存当前节点的数据
指针域 保存其他节点的地址

单链表节点只有后继指针：

1
2
3
4
5
template <typename T>
struct Node {
    T data;
    Node* next;
};

双向链表节点有前驱和后继两个指针：

1
2
3
4
5
6
template <typename T>
struct DNode {
    T data;
    DNode* prev;
    DNode* next;
};
结构 指针数量 方向
单链表 1 个 只能向后
双向链表 2 个 可以向前，也可以向后

链表最容易错的不是“数据怎么存”，而是“指针怎么连”。插入和删除时，要先想清楚前驱、当前节点、后继节点三者的关系。

9、栈、队列与双端队列

9.1 栈

栈是后进先出结构。

操作 STL 接口 说明
入栈 push() 把元素压入栈顶
出栈 pop() 删除栈顶元素，不返回值
取栈顶 top() 返回栈顶元素
判空 empty() 判断是否为空
元素个数 size() 返回栈中元素数量

9.2 队列

队列是先进先出结构。

操作 STL 接口 说明
入队 push() 从队尾插入
出队 pop() 从队头删除
取队头 front() 返回最早进入的元素
取队尾 back() 返回最后进入的元素
判空 empty() 判断是否为空
元素个数 size() 返回队列中元素数量

9.3 双端队列

std::deque 是双端队列，两端都可以插入和删除。

操作 STL 接口
头部插入 push_front()
尾部插入 push_back()
头部删除 pop_front()
尾部删除 pop_back()
访问头部 front()
访问尾部 back()
重新设置长度 resize()

10、二叉树

二叉树是每个节点最多有两个孩子的树形结构。

概念 说明
根节点 整棵树的入口
左孩子 当前节点的左子节点
右孩子 当前节点的右子节点
叶子节点 没有孩子的节点
深度 从根向下经过的层次

简单节点定义：

1
2
3
4
5
6
7
8
9
10
#include <memory>

template <typename T>
struct TreeNode {
    explicit TreeNode(const T& value) : data(value) {}

    T data;
    std::unique_ptr<TreeNode<T>> left;
    std::unique_ptr<TreeNode<T>> right;
};

如果使用 std::unique_ptr，树释放时会自动递归释放子树。

11、课后习题答案

9-1 用数组类模板保存学生成绩并计算平均值

要求：输入学生人数 N，再输入 N 个课程 A 成绩，计算平均成绩。这里用上面整理过的 Array<float>。

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
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <algorithm>
#include <cstddef>
#include <iomanip>
#include <iostream>
#include <memory>
#include <stdexcept>

template <typename T>
class Array {
public:
    explicit Array(std::size_t size = 50)
        : size_(size), data_(std::make_unique<T[]>(size)) {
        if (size == 0) {
            throw std::invalid_argument("array size must be positive");
        }
    }

    Array(const Array& other) : Array(other.size_) {
        std::copy(other.data_.get(), other.data_.get() + size_, data_.get());
    }

    Array& operator=(Array other) {
        swap(other);
        return *this;
    }

    T& operator[](std::size_t index) {
        if (index >= size_) {
            throw std::out_of_range("array index out of range");
        }
        return data_[index];
    }

    const T& operator[](std::size_t index) const {
        if (index >= size_) {
            throw std::out_of_range("array index out of range");
        }
        return data_[index];
    }

    std::size_t size() const {
        return size_;
    }

    void swap(Array& other) noexcept {
        std::swap(size_, other.size_);
        data_.swap(other.data_);
    }

private:
    std::size_t size_;
    std::unique_ptr<T[]> data_;
};

int main() {
    std::size_t n;
    std::cout << "请输入学生人数：";
    std::cin >> n;

    Array<float> scores(n);
    double total = 0;

    for (std::size_t i = 0; i < n; ++i) {
        std::cout << "请输入第 " << i + 1 << " 个学生的课程 A 成绩：";
        std::cin >> scores[i];
        total += scores[i];
    }

    const double average = total / n;
    std::cout << "平均成绩为 " << std::fixed << std::setprecision(2)
              << average << '\n';

    return 0;
}

示例：

1
2
3
4
5
请输入学生人数：3
请输入第 1 个学生的课程 A 成绩：80
请输入第 2 个学生的课程 A 成绩：80
请输入第 3 个学生的课程 A 成绩：81
平均成绩为 80.33

9-2 链表中的一个节点包含哪些数据成员？单链表和双向链表的区别是什么？

链表节点通常包含：

数据成员 说明
数据域 保存节点本身的数据
指针域 保存其他节点地址

单链表和双向链表区别：

类型 节点指针 遍历方向
单链表 一个后继指针 只能从前往后
双向链表 前驱指针 + 后继指针 可以向前，也可以向后

9-3 链表中元素的最大数目是多少？

链表元素个数没有固定上限，主要受可用内存限制。

数组需要连续空间，而链表节点可以分散存放，所以链表更适合频繁插入、删除且数量变化较大的场景。

9-4 定义双向链表节点类 DNode

双向链表节点比单链表节点多一个前驱指针。

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
template <typename T>
class DNode {
public:
    explicit DNode(const T& value = T())
        : data(value), prev(this), next(this) {}

    void insertRight(DNode* node) {
        node->next = next;
        node->prev = this;
        next->prev = node;
        next = node;
    }

    void insertLeft(DNode* node) {
        node->prev = prev;
        node->next = this;
        prev->next = node;
        prev = node;
    }

    DNode* remove() {
        prev->next = next;
        next->prev = prev;
        prev = this;
        next = this;
        return this;
    }

    DNode* nextNode() const {
        return next;
    }

    DNode* prevNode() const {
        return prev;
    }

    T data;

private:
    DNode* prev;
    DNode* next;
};

这里采用循环双向链表节点写法：单个节点初始化时，前驱和后继都指向自己。

9-5 定义两个整型链表 A 和 B，把 B 加入 A 尾部

原答案提示见实验指导。这里给出一个完整的单链表复盘版。

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
62
63
64
65
66
#include <iostream>
#include <memory>

class IntList {
private:
    struct Node {
        explicit Node(int value) : data(value) {}

        int data;
        std::unique_ptr<Node> next;
    };

public:
    void pushBack(int value) {
        auto node = std::make_unique<Node>(value);
        Node* raw = node.get();

        if (!head_) {
            head_ = std::move(node);
            tail_ = raw;
            return;
        }

        tail_->next = std::move(node);
        tail_ = raw;
    }

    void append(const IntList& other) {
        for (Node* current = other.head_.get(); current; current = current->next.get()) {
            pushBack(current->data);
        }
    }

    void print(const char* name) const {
        std::cout << name << ": ";
        for (Node* current = head_.get(); current; current = current->next.get()) {
            std::cout << current->data << ' ';
        }
        std::cout << '\n';
    }

private:
    std::unique_ptr<Node> head_;
    Node* tail_ = nullptr;
};

int main() {
    IntList a;
    IntList b;

    for (int value : {1, 3, 5, 7, 9}) {
        a.pushBack(value);
    }

    for (int value : {2, 4, 6, 8, 10}) {
        b.pushBack(value);
    }

    a.print("A before append");
    b.print("B");

    a.append(b);
    a.print("A after append");

    return 0;
}

输出：

1
2
3
A before append: 1 3 5 7 9
B: 2 4 6 8 10
A after append: 1 3 5 7 9 2 4 6 8 10

9-6 建立有序链表并合并

要求：两个整型有序链表 A 和 B，分别按递增顺序插入 5 个元素，然后把 B 中元素插入 A，保持 A 递增。

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
#include <algorithm>
#include <iostream>
#include <list>

class OrderedList {
public:
    void insertOrdered(int value) {
        auto position = std::find_if(values_.begin(), values_.end(),
                                     [value](int current) {
                                         return value < current;
                                     });
        values_.insert(position, value);
    }

    void mergeFrom(const OrderedList& other) {
        for (int value : other.values_) {
            insertOrdered(value);
        }
    }

    void print(const char* name) const {
        std::cout << name << ": ";
        for (int value : values_) {
            std::cout << value << ' ';
        }
        std::cout << '\n';
    }

private:
    std::list<int> values_;
};

int main() {
    OrderedList a;
    OrderedList b;

    for (int value : {1, 3, 7, 6, 5}) {
        a.insertOrdered(value);
    }

    for (int value : {2, 6, 8, 5, 4}) {
        b.insertOrdered(value);
    }

    a.print("A");
    b.print("B");

    a.mergeFrom(b);
    a.print("A after merge");

    return 0;
}

输出：

1
2
3
A: 1 3 5 6 7
B: 2 4 5 6 8
A after merge: 1 2 3 4 5 5 6 6 7 8

复盘：链表有序插入的关键是先找到第一个“大于当前值”的位置，再把新节点插到它前面。

9-7 什么叫栈？栈中元素操作有何特性？

栈是只能从一端访问的线性群体，这一端称为栈顶。

操作 含义
压栈 向栈顶添加元素
出栈 删除栈顶元素
取栈顶 访问最近压入的元素

栈的特点是后进先出，英文是 LIFO：Last In, First Out。

9-8 构造整型栈并调用常用函数

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
#include <iostream>
#include <stack>

int main() {
    std::stack<int> stack;

    std::cout << std::boolalpha;
    std::cout << "stack.empty(): " << stack.empty() << '\n';

    for (int value : {2, 5, 11}) {
        stack.push(value);
        std::cout << "push " << value << ", top = " << stack.top() << '\n';
    }

    stack.top() = 6;
    std::cout << "modify top to 6\n";

    while (!stack.empty()) {
        std::cout << "size = " << stack.size()
                  << ", top = " << stack.top() << '\n';
        stack.pop();
    }

    std::cout << "size = " << stack.size() << '\n';

    return 0;
}

输出：

1
2
3
4
5
6
7
8
9
stack.empty(): true
push 2, top = 2
push 5, top = 5
push 11, top = 11
modify top to 6
size = 3, top = 6
size = 2, top = 5
size = 1, top = 2
size = 0

调用 top() 或 pop() 前要先判断 empty()。空栈上取栈顶是未定义行为。

9-9 构造两个栈，观察 == 和 <

std::stack 的比较依赖底层容器的字典序比较。可以理解为：从底层容器的起始位置开始逐个比较。

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
#include <iostream>
#include <stack>

void compare(const std::stack<double>& a, const std::stack<double>& b) {
    std::cout << "a == b: " << std::boolalpha << (a == b) << '\n';
    std::cout << "a <  b: " << std::boolalpha << (a < b) << "\n\n";
}

int main() {
    std::stack<double> stack1;
    std::stack<double> stack2;

    stack1.push(4.0);
    stack1.push(3.0);

    stack2.push(4.0);
    compare(stack1, stack2);

    stack2.push(6.0);
    compare(stack1, stack2);

    stack2.push(8.0);
    compare(stack1, stack2);

    stack2.pop();
    stack2.pop();
    stack2.push(3.0);
    compare(stack1, stack2);

    return 0;
}

复盘：这题不是栈的核心用法，核心还是后进先出。比较运算更多是 STL 容器适配器的附加能力。

9-10 什么叫队列？队列中元素操作有何特性？

队列是只能从一端添加元素、从另一端删除元素的线性群体。

位置 说明
队尾 添加元素的位置
队头 删除元素的位置

队列的特点是先进先出，英文是 FIFO：First In, First Out。

9-11 构造整型队列和字符型队列

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
#include <iostream>
#include <queue>
#include <string>

template <typename T>
void drainQueue(std::queue<T>& queue, const char* name) {
    std::cout << name << " size: " << queue.size() << '\n';
    while (!queue.empty()) {
        std::cout << queue.front() << '\n';
        queue.pop();
    }
}

int main() {
    std::queue<int> numbers;
    for (int value : {42, 100, 49, 201}) {
        numbers.push(value);
    }

    std::queue<std::string> words;
    for (const std::string& word : {"cat", "ape", "dog", "mouse", "horse"}) {
        words.push(word);
    }

    std::cout << "last word: " << words.back() << '\n';

    drainQueue(numbers, "numbers");
    drainQueue(words, "words");

    return 0;
}

输出：

1
2
3
4
5
6
7
8
9
10
11
12
last word: horse
numbers size: 4
42
100
49
201
words size: 5
cat
ape
dog
mouse
horse

9-12 使用 deque::assign() 和 deque::swap()

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>

void print(const std::deque<char>& values, const char* name) {
    std::cout << name << ": ";
    for (char value : values) {
        std::cout << value << ' ';
    }
    std::cout << '\n';
}

int main() {
    std::deque<char> a(3, 'A');
    std::deque<char> b(4, 'B');

    print(a, "a");
    print(b, "b");

    a.swap(b);
    print(a, "a after swap");
    print(b, "b after swap");

    a.assign(b.begin(), b.end());
    print(a, "a assign b");

    a.assign(b.begin(), b.begin() + 2);
    print(a, "a assign first two of b");

    a.assign(3, 'Z');
    print(a, "a assign Z");

    return 0;
}

输出：

1
2
3
4
5
6
7
a: A A A
b: B B B B
a after swap: B B B B
b after swap: A A A
a assign b: A A A
a assign first two of b: A A
a assign Z: Z Z Z

9-13 使用 deque::front() 和 deque::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
#include <deque>
#include <iostream>

void print(const std::deque<char>& values) {
    for (char value : values) {
        std::cout << value << ' ';
    }
    std::cout << '\n';
}

int main() {
    std::deque<char> values = {'A', 'B', 'C', 'D'};

    print(values);
    std::cout << "front: " << values.front() << '\n';
    std::cout << "back: " << values.back() << '\n';

    values.front() = 'X';
    values.back() = 'Y';

    print(values);

    return 0;
}

输出：

1
2
3
4
A B C D
front: A
back: D
X B C Y

9-14 使用 deque::insert() 和两端插入删除

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
#include <deque>
#include <iostream>

void print(const std::deque<char>& values) {
    std::cout << "values: ";
    for (char value : values) {
        std::cout << value << ' ';
    }
    std::cout << '\n';
}

int main() {
    std::deque<char> a(3, 'A');
    std::deque<char> b(2, 'B');

    print(a);
    print(b);

    a.insert(a.begin(), 'X');
    print(a);

    a.insert(a.end(), 'Y');
    print(a);

    a.insert(a.end() - 1, 3, 'Z');
    print(a);

    a.insert(a.end(), b.begin(), b.end());
    print(a);

    a.push_front('F');
    a.push_back('L');
    print(a);

    a.pop_front();
    a.pop_back();
    print(a);

    return 0;
}

输出：

1
2
3
4
5
6
7
8
values: A A A
values: B B
values: X A A A
values: X A A A Y
values: X A A A Z Z Z Y
values: X A A A Z Z Z Y B B
values: F X A A A Z Z Z Y B B L
values: X A A A Z Z Z Y B B

9-15 使用 deque::resize()、size()、max_size()

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
#include <deque>
#include <iostream>

void print(const std::deque<char>& values, const char* name) {
    std::cout << name << ": ";
    for (char value : values) {
        std::cout << value << ' ';
    }
    std::cout << '\n';
}

int main() {
    std::deque<char> values = {'A', 'B', 'C', 'D'};

    print(values, "values");
    std::cout << "size: " << values.size() << '\n';
    std::cout << "max_size: " << values.max_size() << '\n';

    values.resize(10, 'X');
    print(values, "resize to 10");
    std::cout << "size: " << values.size() << '\n';

    values.resize(5);
    print(values, "resize to 5");
    std::cout << "size: " << values.size() << '\n';

    return 0;
}

输出中的 max_size() 和编译器、平台有关，不需要记具体数值。

9-16 深度为 n 的二叉树最大节点数是多少？给定节点数的最小深度是多少？

若按教材习惯，把根节点深度记为 0，深度为 n 的二叉树最大节点数为：

1
2^(n + 1) - 1

给定节点数的最小深度：

节点数 最小深度 验算
5 2 2^(2+1)-1 = 7
9 3 2^(3+1)-1 = 15
25 4 2^(4+1)-1 = 31
250 7 2^(7+1)-1 = 255

有些数据结构教材把根节点所在层记为第 1 层，这时公式会写成 2^h - 1。做题时要先看清“深度”的定义。

9-17 建立一个简单二叉树

原题图在文字抽取中缺失。根据原答案代码，可恢复为如下结构：

1
2
3
4
5
    A
   / \
  B   C
 / \
D   E

现代 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
#include <iostream>
#include <memory>

template <typename T>
struct TreeNode {
    explicit TreeNode(const T& value) : data(value) {}

    T data;
    std::unique_ptr<TreeNode<T>> left;
    std::unique_ptr<TreeNode<T>> right;
};

template <typename T>
void preorder(const TreeNode<T>* node) {
    if (!node) {
        return;
    }

    std::cout << node->data << ' ';
    preorder(node->left.get());
    preorder(node->right.get());
}

int main() {
    auto root = std::make_unique<TreeNode<char>>('A');
    root->left = std::make_unique<TreeNode<char>>('B');
    root->right = std::make_unique<TreeNode<char>>('C');
    root->left->left = std::make_unique<TreeNode<char>>('D');
    root->left->right = std::make_unique<TreeNode<char>>('E');

    preorder(root.get());
    std::cout << '\n';

    return 0;
}

输出：

1
A B D E C

复盘：这里使用前序遍历，顺序是根、左子树、右子树。

12、本章复盘清单

检查点 是否掌握
能解释群体类为什么需要模板 待复盘
能写一个带越界检查的数组类模板 待复盘
能说清单链表和双向链表的区别 待复盘
能写出链表节点的插入和删除指针变化 待复盘
能解释栈的 LIFO 和队列的 FIFO 待复盘
能熟练使用 stack、queue、deque 常用接口 待复盘
能根据节点数计算二叉树最小深度 待复盘
能手写一个简单二叉树并做前序遍历 待复盘

这一章可以和数据结构课程一起复盘：C++ 这边看模板、类和容器接口；数据结构那边看逻辑结构、存储结构和基本操作。