C++中树的定义及其相关概念

在 C++ 中，树可以使用类来表示，其基本定义如下：

class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

其中，TreeNode 表示树的节点，val 表示节点的值，left 和 right 分别指向左子树和右子树的根节点，如果一个节点没有左子树或右子树，则对应指针为 nullptr。使用这个基本定义，可以构建出各种树形结构，如二叉树、二叉搜索树、平衡二叉树等。

下面是一些树相关的概念：

• 根节点：树中唯一没有父节点的节点。

• 叶子节点：没有子节点的节点。

• 子树：以某个节点为根节点的子树，包括该节点和该节点的所有子孙节点。

• 祖先节点：某个节点的所有父节点和父节点的父节点等。

• 后代节点：某个节点的所有子节点和子节点的子节点等。

• 节点的度：一个节点的子树个数称为该节点的度。

• 树的度：树中所有节点的度的最大值称为树的度。

• 深度：从根节点到某个节点的唯一路径长度，根节点的深度为 0。

• 高度：从某个节点到其所有叶子节点的最长路径长度，叶子节点的高度为 0。

• 层次遍历：按照树的深度从小到大的顺序，一层一层地遍历所有节点。

• 先序遍历：先访问根节点，然后先序遍历左子树，再先序遍历右子树。

• 中序遍历：先中序遍历左子树，然后访问根节点，再中序遍历右子树。

• 后序遍历：先后序遍历左子树，然后后序遍历右子树，最后访问根节点。

TreeNode(int x) : val(x), left(nullptr), right(nullptr) 是 C++ 中的构造函数初始化列表（Constructor Initialization List）语法格式，用于在对象创建时初始化其成员变量。

在这个语法格式中，int x 是构造函数的参数，用于初始化节点的 val 成员变量。而后面的冒号和成员变量列表则是初始化列表，用于初始化节点的 left 和 right 成员变量。

具体来说，left(nullptr) 表示将 left 成员变量初始化为 nullptr，即空指针；right(nullptr) 同理，表示将 right 成员变量初始化为 nullptr。这里的 nullptr 是 C++11 引入的空指针常量，可以用于初始化指针类型的变量。

使用构造函数初始化列表可以有效地提高代码的效率和可读性，特别是在初始化类成员变量时，可以避免使用赋值语句，提高代码的效率。同时，也可以更加明确地表达出对象的初始化过程，提高代码的可读性。

用结构体定义树

在 C++ 中，可以使用结构体来定义树，如下所示：

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

这个结构体和前面使用类定义树的例子相似，不同的是使用了 struct 关键字而不是 class 关键字来定义结构体类型。另外，该结构体中的成员变量和构造函数也和之前的例子一样，用于表示树的节点。

需要注意的是，使用结构体定义树时，成员变量默认为公有的，因此可以在程序中直接访问。而使用类定义树时，成员变量默认为私有的，需要通过公有的成员函数来访问。这是结构体和类的一个主要区别。但是，为了封装数据和保证代码的健壮性，建议在类或结构体中使用私有成员变量，并提供公有的成员函数来访问和修改这些成员变量。