二叉树基类#

在总述中，我们介绍了二叉树的基本概念和一些常见的二叉树类型。在本篇博客中，我们将实现一个二叉树的基类，包含基本的二叉树结构和常用的操作方法，以及迭代器实现。

WARNING
注意：本博客中的代码实现仅供参考，实际应用中可能需要根据具体需求进行调整和优化。而且，我并没有很严格的按照c++的规范和习惯，所以可能会有一些不太规范的地方，请读者自行斟酌。

二叉树代码结构#

显然的，二叉树的基本结构是一个节点类和一个二叉树类。节点类包含节点的值、左子树和右子树的指针，而二叉树类包含根节点和一些操作方法。这些构成了二叉树最基本的框架，我们可以在此基础上实现各种二叉树类型和操作方法。当然，在基类中，我们只需要实现一些通用的操作方法，如

~~删除节点~~
查找节点
迭代器

TIP
插入和平衡等操作通常是特定于某些二叉树类型的（如二叉搜索树、AVL树等），因此我们可以将这些方法声明为纯虚函数~~（但是我偷懒直接不声明了）~~，让具体的二叉树类型来实现它们。

要注意的是，为了可拓展性，我们将二叉树类设计为一个基类，具体的二叉树类型（如二叉搜索树、平衡二叉树等）可以继承这个基类并实现特定的功能。那么，模板的使用就必不可少。

二叉树的具体构成#

二叉树节点类#

一个二叉树节点类通常包含以下成员：

data：节点储存的数据，可以是任意类型。
left_child：指向左子树的指针。
right_child：指向右子树的指针。

和以下方法：

构造函数：用于初始化节点，而且禁止无参构造函数，以确保每个节点都有一个有效的数据值。
析构函数：用于释放节点占用的资源，要递归地删除左子树和右子树，以避免内存泄漏。
移动和拷贝函数：事实上，二叉树节点通常不需要实现移动和拷贝函数，因为它们的生命周期由二叉树类管理，且节点之间的关系通过指针维护。于是，我们应当禁止二叉树节点的拷贝和移动操作，以避免不必要的资源管理复杂性和潜在的错误。
operator==：实现比较两个节点是否相等，可以用于查找节点等操作。

二叉树类#

一个二叉树类通常包含以下成员：

root：指向二叉树根节点的指针。
迭代器：用于遍历二叉树的迭代器，可以实现前序、中序、后序等不同的遍历方式。

为什么迭代器要放在二叉树类中？
因为迭代器需要访问二叉树的内部结构（如根节点和子树），将迭代器作为二叉树类的成员可以更方便地实现遍历功能。

和以下方法：

构造函数：用于初始化二叉树，通常会将根节点初始化为nullptr。
析构函数：用于释放二叉树占用的资源，要递归地删除根节点及其子树，以避免内存泄漏。
查找节点：实现一个方法来查找二叉树中的节点，可以根据节点的值进行查找。
~~删除节点~~：相当复杂，懒得实现了，后续有机会再更新。

为了让二叉树类可以直接访问节点类的protected成员，我们可以将节点类定义为二叉树类的嵌套类，或者将节点类的成员声明为public，而我直接将二叉树类设置为节点类的友元类，这样二叉树类就可以访问节点类的protected成员了。

二叉树迭代器#

二叉树迭代器通常包含以下成员：

current：指向当前节点的指针。
stack：由于二叉树的遍历往往是中序遍历，而又不能使用函数栈，所以我们需要一个栈来存储访问过的节点，以便在遍历过程中回退到父节点。

和以下方法：

构造函数：用于初始化迭代器，通常会将current初始化为二叉树的根节点，并将所有左子树的节点压入栈中，以准备进行中序遍历。
operator++：实现迭代器的前缀递增操作，用于移动到下一个节点。
operator*：实现迭代器的解引用操作，用于访问当前节点的数据。
operator==和operator!=：实现迭代器的比较操作，用于判断两个迭代器是否指向同一个节点。

TIP
迭代器的实现可以根据需要进行调整，例如可以实现前序遍历、后序遍历等不同的遍历方式，或者实现双向迭代器等更复杂的功能。

具体代码实现#

下面是一个简单的二叉树基类的代码实现，我会进行逐段解释。

二叉树节点类#

1
#ifndef BINARY_TREE_HPP
2
#define BINARY_TREE_HPP
3
#include <stack>
4

5
namespace myStruct {
6
    template<typename Data, class DerivedNode>
7
    class treeNode
8
    {
9
        using Node = treeNode<Data, DerivedNode>;
10
        friend class BinaryTree<Data, DerivedNode>;
11
    protected:
12
        Data data;
13
        DerivedNode *left_child;
14
        DerivedNode *right_child;

在这一段中，首先是防止头文件被多次包含的预处理指令#ifndef和#define（最后有#endif），如果想用#pragma once也行但不推荐。接着，我们定义了一个命名空间myStruct，以避免命名冲突，和提供更好的代码组织。然后，我们定义了一个模板类treeNode，它接受两个模板参数：Data和DerivedNode。

Data表示节点中存储的数据类型，可以是任意类型。
DerivedNode表示派生节点的类型，这样我们可以在基类中使用DerivedNode来表示具体的节点类型，提供更好的可拓展性。这样做有如下好处：
- 可拓展性：如果不使用DerivedNode，我们只能在基类中使用treeNode来表示节点，这样在派生类中就无法使用更具体的节点类型了。而使用DerivedNode后，我们可以在派生类中定义一个具体的节点类型，并将其作为模板参数传递给基类，这样在基类中就可以使用这个具体的节点类型了。~~偷懒小技巧~~
- CRTP：避免了使用虚函数，让编译器能够更好地优化代码，因为编译器可以根据DerivedNode的具体类型来生成更高效的代码。

接着，我们使用using Node = treeNode<Data, DerivedNode>;来定义一个类型别名Node，这样我们在后续的代码中就可以直接使用Node来表示节点类型了。最后，我们将BinaryTree<Data, DerivedNode>声明为treeNode的友元类，这样BinaryTree就可以访问treeNode的protected成员了。

15
    public:
16
        treeNode() = delete;// 禁止默认构造，必须有初始数据
17
        explicit treeNode(Data data) : data(std::move(data)), left_child(nullptr), right_child(nullptr) {}
18

19
        // 显式禁止拷贝和移动，树节点通常通过指针管理，避免意外拷贝导致内存管理混乱
20
        treeNode(const treeNode&) = delete;
21
        treeNode& operator=(const treeNode&) = delete;
22
        treeNode(treeNode&&) = delete;
23
        treeNode& operator=(treeNode&&) = delete;
24

25
        virtual ~treeNode(){
26
            delete left_child;
27
            delete right_child;
28
        }
29
    };
30
    template <typename Data, class DerivedNode>
31
    bool operator==(const DerivedNode &lhs, const DerivedNode &rhs)
32
    {
33
        return lhs.data == rhs.data;
34
    }

在这一段中，我们定义了treeNode类的构造函数、析构函数和一些特殊成员函数。

treeNode() = delete;：禁止默认构造函数，要求每个节点必须有一个有效的数据值。
被delete的四个函数：禁止拷贝构造函数、拷贝赋值运算符、移动构造函数和移动赋值运算符。因为二叉树节点通常通过指针管理，禁止这些函数可以避免意外的拷贝或移动操作导致内存管理混乱。
virtual ~treeNode()：定义一个虚析构函数，递归地删除左子树和右子树，以避免内存泄漏。使用virtual关键字确保在派生类中正确调用析构函数，释放资源。
treeNode(Data data)：定义一个显式的构造函数，接受一个Data类型的参数来初始化节点的数据，并将左右子树指针初始化为nullptr。explicit关键字用于防止隐式类型转换，确保构造函数只能通过显式调用来使用。std::move(data)用于将传入的数据移动到节点中，避免不必要的复制，提高性能。
operator==：实现比较两个节点是否相等，比较的是节点中的数据值。

二叉树类#

35
    template<class Node>
36
    class BinaryTree
37
    {
38
    protected:
39
        Node *root;
40
    public:
41
        BinaryTree() : root(nullptr) {}
42
        virtual ~BinaryTree() { delete root; }

在这一段中，class Node是一个模板参数，表示二叉树中节点的类型，这样我们可以在派生类中定义一个具体的节点类型，并将其作为模板参数传递给基类。这样有利于提高代码的可拓展性。在这之后，由于我们要实现查找操作，所以最好先把迭代器实现了，这样我们就可以使用迭代器来遍历二叉树并查找节点了。

二叉树迭代器#

42
        class InorderIterator
43
        {
44
        protected:
45
            Node *current;
46
            std::stack<Node*> node_stack;
47
            void pushLeft(Node *node) {
48
                while (node) {
49
                    node_stack.push(node);
50
                    node = node->left_child;
51
                }
52
            }

在这一段中，我们定义了一个嵌套类InorderIterator，用于实现二叉树的中序遍历。

Node *current;：指向当前节点的指针。
std::stack<Node*> node_stack;：一个栈，用于存储访问过的节点，以便在遍历过程中回退到父节点。
void pushLeft(Node *node)：一个辅助函数，用于将当前节点及其所有左子树的节点压入栈中，以准备进行中序遍历。

53
        public:
54
            InorderIterator(Node *root) : current(root) {
55
                pushLeft(current);
56
                operator++(); // 初始化时将current指向第一个节点
57
            }
58
            ~InorderIterator() = default;
59
            auto& operator*(){
60
                return current->data;
61
            }

在这一段中，我们定义了InorderIterator的构造函数、析构函数和解引用操作符。

InorderIterator(Node *root)：构造函数，接受一个指向二叉树根节点的指针，并调用pushLeft函数将根节点及其所有左子树的节点压入栈中，以准备进行中序遍历。然后调用operator++()将current指向第一个节点。
~InorderIterator() = default;：默认析构函数，因为我们没有需要特殊的资源管理。不要想着删除节点，因为节点的生命周期由二叉树类管理，迭代器不负责删除节点。
auto& operator*()：解引用操作符，返回当前节点的数据的引用，以便可以直接访问和修改节点的数据。

62
            // 前置 ++ (++it)
63
            InorderIterator& operator++()
64
            {
65
                if (node_stack.empty())
66
                {
67
                    current = nullptr;
68
                    return *this;
69
                }
70
                current = node_stack.top();
71
                node_stack.pop();
72
                if (current->right_child)
73
                {
74
                    pushLeft(current->right_child);
75
                }
76
                return *this;
77
            }

在这一段中，我们实现了迭代器的前置递增操作符operator++()，用于移动到下一个节点。

首先检查栈是否为空，如果为空，说明已经遍历完所有节点，将current设置为nullptr并返回。
否则，从栈顶弹出一个节点，将其赋值给current。
然后检查current的右子树是否存在，如果存在，调用pushLeft函数将右子树的节点压入栈中，以准备继续进行中序遍历。
最后返回当前迭代器对象，以支持链式调用。

78
InorderIterator& operator=(const InorderIterator& other)
79
            {
80
                if (this != &other)
81
                {
82
                    node_stack = other.node_stack; // 复制栈
83
                    current = other.current; // 复制当前节点指针
84
                }
85
                return *this;
86
            }
87

88
            // 判断是否相等，用于循环结束判断
89
            bool operator==(const InorderIterator& other) const
90
            {
91
                return current == other.current;
92
            }
93

94
            bool operator!=(const InorderIterator& other) const
95
            {
96
                return !(*this == other);
97
            }
98

99
        };

在这一段中，我们实现了迭代器的拷贝赋值操作符和比较操作符。并且到达了迭代器类的结尾。但迭代器还没结束，还有begin和end方法，这两个方法在二叉树类中实现，毕竟迭代器本身怎么能获取begin和end呢？

100
        InorderIterator begin() {
101
            return InorderIterator(root);
102
        }
103

104
        InorderIterator end() {
105
            return InorderIterator(nullptr);
106
        }

在这一段中，我们实现了二叉树类的begin()和end()方法，用于返回迭代器的起始位置和结束位置。

TIP
有没有注意到没有const_iterator?这是因为一旦要写const_iterator，为了不重复代码~~（直接重写，力大砖飞）~~，就要用到template <bool IsConst>模板参数来区分const_iterator和iterator，属于高阶用法了，但这是STL中的常见做法。请注意，const_iterator是有必要的，不然在处理const元素时就无法使用迭代器了，所以后续有机会再更新const_iterator的实现。

二叉树类的查找方法#

107
        Node* find(const Data& value) {
108
            for (auto it = begin(); it != end(); ++it) {
109
                if (*it == value)
110
                    return it.current; // 返回指向找到节点的指针
111
            }
112
            return nullptr; // 如果未找到，返回nullptr
113
        }
114
    };
115
} // namespace myStruct
116
#endif // BINARY_TREE_HPP

在这一段中，我们通过迭代器遍历二叉树来实现查找方法find。已经是宝宝巴士级别了，就不过多说明了。

结语#

二叉树的基类实现是一个重要的基础，提供了二叉树的基本结构和常用的操作方法。通过使用模板和迭代器，我们可以实现一个灵活且可拓展的二叉树类，适用于各种不同类型的二叉树。至于下一步，那就是AVL树了，具体实现请待下回分解。~~不得不说，AVL树真的很麻烦啊~~