跳转至

7、树的相关介绍(入门级)

1、树的概念

​ 树（Tree）是一种非线性的数据结构，它由若干个节点（Node）和连接这些节点的边（Edge）组成。树中有一个节点作为根节点（Root），从根节点开始可到达的所有节点构成一棵子树（Subtree）。除了根节点之外，每个节点都有唯一的一个父节点（Parent），可以有多个子节点（Child）。没有子节点的节点称为叶子节点（Leaf），有子节点的节点称为内部节点（Internal Node）。

​ 树的概念最初来源于计算机科学以外的领域，例如生物分类学、语言学等，后来被引入到计算机科学中，并广泛应用于各个领域。在计算机科学中，树的应用范围非常广泛，例如：文件系统、编译器、数据库索引、图形界面等。

​ 树可以用图形化的方式来表示，其中根节点位于顶部，下方依次排列着其子节点。树的深度（Depth）指从根节点到叶子节点的最长路径长度，树的高度（Height）指从根节点到任意节点的最长路径长度。

树可以分为多个不同的类别，以下是一些常见的树类型：

  • 二叉树（Binary Tree）：每个节点最多有两个子节点的树，左子节点和右子节点之间有明确的区分。
  • 平衡二叉树（Balanced Binary Tree）：一种特殊的二叉树，其左右子树的高度差不超过1，以保持树的平衡性，例如AVL树和红黑树。
  • B树（B-tree）：一种多叉搜索树，用于大型数据集或文件系统中的索引结构。
  • 堆（Heap）：一种特殊的二叉树，用于实现优先队列等数据结构，例如最小堆和最大堆。
  • 二叉查找树（Binary Search Tree）：每个节点最多有两个子节点的树，其中左子节点的值小于当前节点的值，右子节点的值大于当前节点的值，用于快速查找、插入和删除操作。

​ 除了上述常见的树类型外，还有许多其他类型的树，例如树状数组、Trie树等。树的应用非常广泛，在算法理论和实际编程中都非常重要。

2、有根树的相关概念

​ 有根树（Rooted Tree）是一种特殊的树，其中有一个节点被指定为根节点（Root），从根节点开始可以到达所有其他节点。相对于普通树而言，有根树强调了节点之间的方向性关系。

以下是有根树的一些相关概念：

​ 1.父节点（Parent）

一个节点的父节点是指该节点的直接上级节点，即该节点的边所连接的节点。

​ 2.子节点（Child）

一个节点的子节点是指该节点的直接下级节点，即与该节点通过边所连接的节点。

​ 3.兄弟节点（Sibling）

拥有同一父节点的节点互为兄弟节点。

​ 4.祖先节点（Ancestor）

从根节点到该节点路径上的所有节点都是该节点的祖先节点。

​ 5.后代节点（Descendant）

从该节点到根节点路径上的所有节点都是该节点的后代节点。

​ 6.子树（Subtree）

以某个节点作为根节点，包含该节点及其所有子节点和他们的子节点的树称为该节点的子树。

​ 7.深度（Depth）

树中节点到根节点的路径长度称为该节点的深度。

​ 8.高度（Height）

从一个节点到其最远叶子节点的路径长度称为该节点的高度，树的高度是根节点的高度。

​ 9.度（Degree）

一个节点的度（Degree）是指其子节点的数量。叶子节点的度为0，即它没有子节点，而度不为0的节点都称为内部节点（Internal Node）

3、树的性质

以下是树的几个重要性质：

  1. 每个节点最多有一个父节点。
  2. 每个节点可以有多个子节点。
  3. 除了根节点之外，每个节点都有唯一的一个父节点。
  4. 树中没有环（Cycle），也就是说，从任意一个节点开始，沿着任意一条路径都不能回到该节点。
  5. 树中有且仅有一个节点没有父节点，称为根节点（Root）。
  6. 从根节点出发，可以到达树中的每个节点。
  7. 如果一棵树的所有叶子节点（即没有子节点的节点）深度相同，则该树被称为平衡树。
  8. 如果一棵树的每个非叶子节点（即有子节点的节点）恰好有k个子节点，则称该树为k叉树。
  9. 一棵有n个节点的k叉树，第i层最多有ki个节点，总共最多有 (k(h+1) - 1)/(k-1)个节点，其中h为树的高度。

4、树的存储方法

树的存储方法有多种，以下是几种常见的方法：

  1. 双亲表示法（Parent Representation）：对于每个节点保存其父节点的下标或指针。缺点是不方便查找兄弟节点。
  2. 孩子表示法（Child Representation）：对于每个节点保存其所有子节点的下标或指针，但没有指向父节点的指针。缺点是不方便查找父节点。
  3. 孩子兄弟表示法（Left-Child Right-Sibling Representation）：以二叉树为基础，将每个节点的第一个子节点作为其左孩子，将其右兄弟节点作为其右孩子。该表示法比较灵活，但操作复杂度较高。
  4. 邻接表（Adjacency List）：使用一个数组保存每个节点和其相邻节点的信息。每个节点都有一个链表保存其所有子节点的信息。该方法适用于稀疏树。
  5. 邻接矩阵（Adjacency Matrix）：使用一个n x n的矩阵M来表示一棵n个节点的树，其中M(i,j)=1表示i和j之间有边，否则为0。该方法适用于稠密树，但空间开销较大。

选择合适的存储方法取决于应用场景、树的大小和形态等因素。在实际编程中，常常会根据具体情况选择最适合的存储方法。

4.1 有根树的父亲表示法

​ 有根树的父亲表示法（Parent Representation）是一种简单的树的存储方法，它使用一个数组保存每个节点的信息，其中第i个元素表示第i个节点的父节点在数组中的下标或指针。

例如，对于如下所示的有根树：

C++
1
2
3
4
5
      1
     / \
    2   3
   /|\
  4 5 6

可以使用以下数组a来表示：

C++
1
a[] = {-1, 0, 0, 1, 1, 1}

​ 其中，-1表示没有父节点的根节点，0表示节点1的父节点是根节点，1表示节点2的父节点是节点1，以此类推。

使用父亲表示法存储树的优点是简单、直观，且可以方便地遍历节点的所有祖先节点。但缺点是不方便查找兄弟节点和子节点。

​ 在实际应用中，父亲表示法适用于树的深度较小且节点数量较少的情况。对于更大的树，可能需要采用其他的存储方法。

4.2 有根树的图存储方法

​ 有根树的图存储方法有两种，一种是邻接表，一种是邻接矩阵。其中邻接表是指对于每个节点，存储其所有子节点的指针或者下标，而邻接矩阵则是用一个二维数组来表示节点之间的关系。在邻接表中，每个节点的子节点可以用一个链表来存储，这样可以节省空间，但是查询某个节点的子节点时需要遍历整个链表，时间复杂度为O(n)，其中n为该节点的度数。而在邻接矩阵中，可以直接通过数组下标来访问节点之间的关系，查询某个节点的子节点的时间复杂度为O(1)，但是空间复杂度较高，为O(n^2)，其中n为节点的个数。因此，在实际应用中，需要根据具体情况选择合适的存储方法。

​ 邻接矩阵存储的实现代码如下：

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

using namespace std;

vector<vector<int>> build_tree(vector<int>& arr) {
    int n = arr.size();
    vector<vector<int>> matrix(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++) {
        if (arr[i] != -1) {
            matrix[arr[i]][i] = 1;
        }
    }

    return matrix;
}

int main() {
    vector<int> arr = {-1, 0, 0, 1, 1, 1};
    vector<vector<int>> matrix = build_tree(arr);

    // 测试输出树的邻接矩阵
    cout << "Adjacency Matrix:" << endl;
    for (int i = 0; i < matrix.size(); i++) {
        for (int j = 0; j < matrix[i].size(); j++) {
            cout << matrix[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

邻接表存储树的示例代码：

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
44
45
46
47
48
#include <iostream>
#include <vector>

using namespace std;

struct TreeNode {
    int val;
    vector<TreeNode*> children;
    TreeNode(int x) : val(x) {}
};

TreeNode* build_tree(vector<int>& arr) {
    vector<TreeNode*> nodes(arr.size());
    for (int i = 0; i < arr.size(); i++) {
        nodes[i] = new TreeNode(i);
    }

    TreeNode* root = nullptr;
    for (int i = 0; i < arr.size(); i++) {
        if (arr[i] == -1) {
            root = nodes[i];
        } else {
            nodes[arr[i]]->children.push_back(nodes[i]);
        }
    }

    return root;
}

int main() {
    vector<int> arr = {-1, 0, 0, 1, 1, 1, 2};
    TreeNode* root = build_tree(arr);

    // 测试输出树的节点及其子节点
    cout << "Node\tChildren" << endl;
    for (int i = 0; i < arr.size(); i++) {
        cout << i << "\t";
        for (int j = 0; j < root->children.size(); j++) {
            if (root->children[j]->val == i) {
                cout << j << " ";
                break;
            }
        }
        cout << endl;
    }

    return 0;
}

​ 在此示例中，我们创建一个大小为n的节点数组nodes，并遍历输入数组，对于每个节点i，如果它不存在，则创建一个新的TreeNode对象。然后遍历数组，对于每个节点i，如果它有父亲节点，则将其添加到父亲节点的children向量中。最后返回根节点。

5、二叉树

5.1 二叉树的基本概念

二叉树是一种特殊的树形结构，其每个节点最多只有两个子节点，称为左子节点和右子节点。二叉树具有如下基本概念：

  1. 根节点（Root）：二叉树的顶部节点，没有父节点。
  2. 叶子节点（Leaf）：二叉树中没有子节点的节点，也称为终端节点。
  3. 内部节点（Internal node）：除了叶子节点以外的节点。
  4. 子树（Subtree）：一个节点及其所有后代节点组成的子树，可以看作一个新的二叉树。
  5. 高度（Height）：从根节点到叶子节点的最长路径长度，也即树的深度。
  6. 深度（Depth）：从根节点到当前节点所经过的边数。
  7. 前序遍历（Pre-order traversal）：先访问根节点，然后递归地访问左子树和右子树。
  8. 中序遍历（In-order traversal）：先递归地访问左子树，然后访问根节点，最后递归地访问右子树。
  9. 后序遍历（Post-order traversal）：先递归地访问左子树和右子树，最后访问根节点。
  10. 层次遍历（Level order traversal）：按照层次顺序依次访问每个节点，从上到下、从左到右遍历。

5.2 二叉树的性质

二叉树是一种特殊的树形结构，其每个节点最多只有两个子节点。以下是二叉树的一些重要性质：

  1. 在二叉树的第i层上，至多有2(i-1)个节点。
  2. 深度为k的二叉树至多有2k-1个节点。
  3. 对于任意一棵非空二叉树，如果叶子节点数为n0，度为2的节点数为n2，则n0=n2+1。
  4. 一棵深度为k，且有2k-1个节点的二叉树，称为满二叉树（Full Binary Tree）。
  5. 深度为h，有n个节点的二叉树，当且仅当其各节点都与深度为h的满二叉树中编号从1至n的节点对应时，称之为完全二叉树（Complete Binary Tree）。
  6. 对于一棵非空二叉树，若其左子树的深度为h1，右子树的深度为h2，则它的高度h=max(h1, h2)+1。
  7. 若在一棵二叉树中，每个节点的值都大于等于其左子树中任意一个节点的值，且小于等于其右子树中任意一个节点的值，称之为二叉搜索树（Binary Search Tree）。
  8. 二叉树的遍历方式有前序遍历、中序遍历和后序遍历，层次遍历等。

5.3 满二叉树和完全二叉树

满二叉树和完全二叉树是二叉树的两种特殊类型，它们有以下性质：

  1. 满二叉树：一棵深度为k，且有2k-1个节点的二叉树，称为满二叉树。满二叉树的所有非叶子节点都有两个子节点，且所有叶子节点都在同一层上。
  2. 完全二叉树：深度为h，有n个节点的二叉树，当且仅当其各节点都与深度为h的满二叉树中编号从1至n的节点对应时，称之为完全二叉树。完全二叉树的叶子节点从左到右依次排列，除最后一层外，其它层的节点数都达到了最大值，最后一层的节点全部靠左排列。
  3. 满二叉树的高度为log2(n+1)，其中n为节点数。
  4. 完全二叉树的高度为floor(log2(n))或者ceil(log2(n+1))-1，其中n为节点数。
  5. 对于完全二叉树中的每个非叶子节点i，它的左子节点为2i，右子节点为2i+1。
  6. 对于完全二叉树，如果按照从上到下、从左到右的顺序给节点编号，那么节点i的父节点为i/2（向下取整），左子节点为2i，右子节点为2i+1。

5.4 二叉树的实现

5.4.1 二叉树的数组实现

​ 二叉树可以使用数组来描述，其中每个元素表示二叉树中的一个节点。如果用下标i表示某个节点，那么它的左子节点就是2i，右子节点就是2i+1，父节点就是i/2（向下取整）。这种方式可以将二叉树存储在一维数组中，而不需要使用指针，便于实现和操作。

​ 通常情况下，我们会将数组下标从1开始，这样根节点的下标就是1，它的左子节点为2，右子节点为3。对于空节点，我们可以用特定的值来表示，例如-1或0等。如果我们将一棵完全二叉树按层次遍历的顺序依次放入数组中，则数组的大小应该是2(h+1)-1，其中h为树的高度。

以下是C++中用数组表示二叉树的示例代码：

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
const int MAXN = 100;
int tree[MAXN]; // 定义二叉树数组
int n; // 节点数

// 根据下标获取节点的值
int get_value(int index) {
    if (index < 1 || index > n) return -1; // 数组越界，返回-1表示空节点
    return tree[index];
}

// 根据下标设置节点的值
void set_value(int index, int value) {
    if (index < 1 || index > n) return; // 数组越界，无法设置节点的值
    tree[index] = value;
}

// 获取节点的左子节点下标
int get_left_child(int index) {
    int child = index * 2;
    if (child > n) return -1; // 超出数组范围，返回-1表示空节点
    return child;
}

// 获取节点的右子节点下标
int get_right_child(int index) {
    int child = index * 2 + 1;
    if (child > n) return -1; // 超出数组范围，返回-1表示空节点
    return child;
}

// 获取节点的父节点下标
int get_parent(int index) {
    if (index == 1) return -1; // 根节点无父节点，返回-1表示空节点
    return index / 2;
}

​ 以上代码实现了获取和设置节点值、获取左右子节点和父节点等基本操作。这种方式虽然简单但不如指针易于理解，适用于一些简单场景。

5.4.2 二叉树的链表实现

​ 二叉树可以使用链表来描述，其中每个节点包含一个数据域和两个指针域，分别指向左子节点和右子节点。通常情况下，我们将二叉树定义为一个指向根节点的指针。

在C++中，可以通过结构体或类来实现二叉树的链表描述，具体定义方式如下：

​ 1.结构体定义方式：

C++
1
2
3
4
5
6
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

​ 2.类定义方式：

C++
1
2
3
4
5
6
7
class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

​ 以上两种定义方式都包括了一个整数值(val)和指向左右子节点的指针(left和right)。其中，构造函数用于初始化节点的值和左右子节点的指针。

​ 使用链表描述二叉树能够灵活地操作节点，并且不需要预先知道二叉树节点个数。同时，链表描述也方便对二叉树进行遍历等操作。

5.5 二叉树的常用操作

二叉树的常用操作：

  1. 建立二叉树。
  2. 插入节点：将一个节点插入到二叉树中。
  3. 删除节点：从二叉树中删除一个节点，并保持二叉树的特性不变。
  4. 查找节点：在二叉树中查找一个指定的节点并返回。
  5. 遍历二叉树：包括前序遍历、中序遍历和后序遍历等。
  6. 计算二叉树的深度：递归计算二叉树的深度。
  7. 计算二叉树的节点个数：递归计算二叉树的节点个数。
  8. 判断二叉树是否平衡：检查左右子树高度差是否超过1，如果都满足则为平衡二叉树。
  9. 获取二叉树中最大或最小值：在二叉搜索树中，最大值位于右下角，最小值位于左下角。
5.5.1 建立二叉树

在C++中建立二叉树可以使用递归或非递归方式，下面分别给出两种实现方式：

​ 1.递归方式

​ 递归方式是最简单直观的方法，每次递归调用时构造一个新节点，将其值赋为当前处理的值，然后将左右子节点指针分别指向左右子树。由于二叉树的结构是递归定义的，因此递归方式非常适合描述二叉树。

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    if (preorder.empty() || inorder.empty()) return NULL; // 边界条件
    int root_val = preorder[0]; // 前序遍历的第一个元素是根节点
    auto root_pos = find(inorder.begin(), inorder.end(), root_val); // 在中序遍历中查找根节点位置
    int left_size = root_pos - inorder.begin(); // 左子树节点数
    vector<int> left_pre(preorder.begin() + 1, preorder.begin() + 1 + left_size); // 左子树前序遍历
    vector<int> left_in(inorder.begin(), root_pos); // 左子树中序遍历
    vector<int> right_pre(preorder.begin() + 1 + left_size, preorder.end()); // 右子树前序遍历
    vector<int> right_in(root_pos + 1, inorder.end()); // 右子树中序遍历
    TreeNode* root = new TreeNode(root_val); // 构造当前节点
    root->left = buildTree(left_pre, left_in); // 递归构造左子树
    root->right = buildTree(right_pre, right_in); // 递归构造右子树
    return root;
}

​ 2.非递归方式

​ 非递归方式使用栈来实现，依次读入前序遍历数组中的元素并创建节点，同时将其压入栈中。如果当前节点的值等于中序遍历数组中的元素，则弹出栈顶元素并向右转向下一个节点；否则继续插入左子节点。

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
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    if (preorder.empty() || inorder.empty()) return NULL; // 边界条件
    stack<TreeNode*> stk;
    TreeNode* root = new TreeNode(preorder[0]); // 前序遍历的第一个元素是根节点
    stk.push(root);
    for (int i = 1, j = 0; i < preorder.size(); ++i) {
        TreeNode* node = stk.top();
        if (node->val != inorder[j]) { // 如果当前节点的值不等于中序遍历的下一个元素，则插入左子节点
            node->left = new TreeNode(preorder[i]);
            stk.push(node->left); // 将新节点压入栈中
        } else {
            while (!stk.empty() && stk.top()->val == inorder[j]) { // 如果当前节点的值等于中序遍历的下一个元素，则弹出栈顶元素并向右转向下一个节点
                node = stk.top();
                stk.pop();
                ++j;
            }
            node->right = new TreeNode(preorder[i]); // 插入右子节点
            stk.push(node->right); // 将新节点压入栈中
        }
    }
    return root;
}

​ 以上是建立二叉树的两种实现方式，可以根据需要选择合适的方法。

5.5.2 在二叉树中插入节点

​ 在二叉树中插入节点的基本思路是从根节点开始搜索，找到一个空闲位置并插入新节点。这里给出递归和非递归两种实现方式：

​ 1.递归方式

​ 递归方式比较简单明了，每次递归时判断当前节点是否为空，如果为空则创建新节点并返回；否则根据比较结果决定进入左子树或右子树进行递归操作。

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void insert(TreeNode*& root, int val) { // 注意要传入指向指针的引用
    if (root == NULL) root = new TreeNode(val); // 如果当前节点为空，则创建新节点并返回
    else if (val < root->val) insert(root->left, val); // 如果待插入节点值小于当前节点值，则递归插入左子树
    else insert(root->right, val); // 否则递归插入右子树
}

​ 2.非递归方式

​ 非递归方式使用循环来实现，按照前序遍历的顺序搜索二叉树，如果当前节点为空，则将新节点插入到该位置。

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void insert(TreeNode*& root, int val) {
    TreeNode** p = &root;
    while (*p != NULL) { // 按照前序遍历的顺序搜索二叉树
        if (val < (*p)->val) p = &((*p)->left); // 如果待插入节点值小于当前节点值，则进入左子树
        else p = &((*p)->right); // 否则进入右子树
    }
    *p = new TreeNode(val); // 如果当前节点为空，则将新节点插入到该位置
}

​ 以上是二叉树插入节点的两种实现方式，可以根据需要选择合适的方法。

5.5.3 二叉树删除节点

二叉树删除节点的实现方式比插入节点要复杂，因为删除节点后需要保证二叉树的特性不变。这里给出一种使用递归的实现方式：

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
class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* deleteNode(TreeNode* root, int key) {
    if (root == NULL) return NULL; // 边界条件
    if (key < root->val) root->left = deleteNode(root->left, key); // 如果待删除节点在左子树中，则递归进入左子树
    else if (key > root->val) root->right = deleteNode(root->right, key); // 如果待删除节点在右子树中，则递归进入右子树
    else { // 找到了待删除节点
        if (root->left == NULL) { // 如果待删除节点没有左子树，则用右子树代替它
            TreeNode* temp = root->right;
            delete root;
            root = temp;
        } else if (root->right == NULL) { // 如果待删除节点没有右子树，则用左子树代替它
            TreeNode* temp = root->left;
            delete root;
            root = temp;
        } else { // 如果待删除节点既有左子树又有右子树，则找到其右子树中最小的节点
            TreeNode* p = root->right;
            while (p->left != NULL) p = p->left;
            root->val = p->val; // 将右子树中最小的节点值赋给待删除节点
            root->right = deleteNode(root->right, p->val); // 递归删除右子树中最小的节点
        }
    }
    return root;
}

​ 如果待删除节点只有一个子节点，则用其子节点代替它；如果既有左子树又有右子树，则可以用右子树中最小的节点代替它，也可以用左子树中最大的节点代替它。以上实现方式使用后者，因为这样更容易满足二叉树的特性不变。

5.5.4 二叉树中查找节点

​ 在二叉树中查找节点通常使用递归的方式实现，遍历根节点、左子树和右子树，直到找到指定的节点或者遍历完整个二叉树。

​ 下面是一个用递归方式查找节点的示例代码：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* findNode(TreeNode* root, int val) {
    if (root == NULL || root->val == val) return root; // 边界条件：如果当前节点为空或等于目标值，则返回该节点
    if (val < root->val) return findNode(root->left, val); // 如果目标值小于当前节点值，则递归进入左子树查找
    else return findNode(root->right, val); // 否则递归进入右子树查找
}

​ 该函数返回一个指向目标节点的指针，如果找不到目标节点则返回 NULL。

5.5.5 二叉树的遍历

​ 二叉树的遍历有四种方法，分别为前序遍历、中序遍历、后序遍历和层次遍历。其中前序、中序和后序遍历都是深度优先搜索（DFS）算法，而层次遍历是广度优先搜索（BFS）算法。

下面给出这四种遍历方式在C++中的代码实现：

​ 1.前序遍历

​ 前序遍历的顺序是先访问根节点，再访问左子树，最后访问右子树。

递归实现：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void preorderTraversal(TreeNode* root, vector<int>& res) {
    if (root == NULL) return; // 边界条件
    res.push_back(root->val); // 访问当前节点
    preorderTraversal(root->left, res); // 递归访问左子树
    preorderTraversal(root->right, res); // 递归访问右子树
}

非递归实现：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> stk;
    while (!stk.empty() || root != NULL) {
        while (root != NULL) { // 沿着左子树一直访问到最左端的节点
            res.push_back(root->val); // 访问当前节点
            stk.push(root);
            root = root->left;
        }
        root = stk.top();
        stk.pop();
        root = root->right; // 访问右子树
    }
    return res;
}

​ 2.中序遍历

中序遍历的顺序是先访问左子树，再访问根节点，最后访问右子树。

递归实现：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void inorderTraversal(TreeNode* root, vector<int>& res) {
    if (root == NULL) return; // 边界条件
    inorderTraversal(root->left, res); // 递归访问左子树
    res.push_back(root->val); // 访问当前节点
    inorderTraversal(root->right, res); // 递归访问右子树
}

非递归实现：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> stk;
    while (!stk.empty() || root != NULL) {
        while (root != NULL) { // 沿着左子树一直访问到最左端的节点
            stk.push(root);
            root = root->left;
        }
        root = stk.top();
        stk.pop();
        res.push_back(root->val); // 访问当前节点
        root = root->right; // 访问右子树
    }
    return res;
}

​ 3.后序遍历

​ 后序遍历的顺序是先访问左子树，再访问右子树，最后访问根节点。

递归实现：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void postorderTraversal(TreeNode* root, vector<int>& res) {
    if (root == NULL) return; // 边界条件
    postorderTraversal(root->left, res); // 递归访问左子树
    postorderTraversal(root->right, res); // 递归访问右子树
    res.push_back(root->val); //    
    res.push_back(root->val); // 访问当前节点
}

非递归实现：

Text Only
 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
复制代码class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> stk;
    TreeNode* prev = NULL; // 用于记录上一个访问过的节点
    while (!stk.empty() || root != NULL) {
        while (root != NULL) { // 沿着左子树一直访问到最左端的节点
            stk.push(root);
            root = root->left;
        }
        root = stk.top();
        if (root->right == NULL || root->right == prev) { // 如果当前节点没有右子树或右子树已经被访问过
            stk.pop();
            res.push_back(root->val); // 访问当前节点
            prev = root;
            root = NULL;
        } else { // 否则访问右子树
            root = root->right;
        }
    }
    return res;
}

​ 4.层次遍历

​ 层次遍历的顺序是按照从上到下、从左到右依次访问每个节点。

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

vector<int> levelOrder(TreeNode* root) {
    vector<int> res;
    queue<TreeNode*> q;
    if (root != NULL) q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        res.push_back(node->val); // 访问当前节点
        if (node->left != NULL) q.push(node->left); // 将左子节点加入队列
        if (node->right != NULL) q.push(node->right); // 将右子节点加入队列
    }
    return res;
}

​ 以上是四种遍历方式的实现代码，可以根据需要选择合适的方法。

5.5.6 计算二叉树的深度

​ 计算二叉树的深度可以使用递归或非递归方式实现。其中递归的方法比较简单，只需要分别计算左子树和右子树的深度，然后取它们的最大值再加1即可。

下面是一个使用递归方式计算二叉树深度的示例代码：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

int maxDepth(TreeNode* root) {
    if (root == NULL) return 0; // 空节点的深度为0
    int leftDepth = maxDepth(root->left); // 计算左子树深度
    int rightDepth = maxDepth(root->right); // 计算右子树深度
    return max(leftDepth, rightDepth) + 1; // 左右子树深度的最大值加1即为当前节点所在的深度
}

​ 如果不使用递归，则可以使用广度优先搜索（BFS）算法，以层次遍历的方式依次访问每一层节点，并在访问完每一层节点后将深度加1，直到遍历完整个二叉树。

下面是一个使用非递归方式计算二叉树深度的示例代码：

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
class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

int maxDepth(TreeNode* root) {
    if (root == NULL) return 0; // 边界条件
    queue<TreeNode*> q;
    q.push(root);
    int depth = 0;
    while (!q.empty()) {
        int n = q.size(); // 当前层节点个数
        for (int i = 0; i < n; i++) {
            TreeNode* node = q.front();
            q.pop();
            if (node->left != NULL) q.push(node->left); // 将左子节点加入队列
            if (node->right != NULL) q.push(node->right); // 将右子节点加入队列
        }
        depth++; // 遍历完一层节点，深度加1
    }
    return depth;
}

以上是两种计算二叉树深度的实现方式，可以根据需要选择合适的方法。

5.5.7 计算二叉树的节点个数

​ 计算二叉树的节点个数可以使用递归或非递归方式实现。其中递归的方法比较简单，只需要分别计算左子树和右子树的节点个数，然后加上当前节点即可。

​ 下面是一个使用递归方式计算二叉树节点个数的示例代码：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

int countNodes(TreeNode* root) {
    if (root == NULL) return 0; // 空节点的节点个数为0
    int leftCount = countNodes(root->left); // 计算左子树节点个数
    int rightCount = countNodes(root->right); // 计算右子树节点个数
    return leftCount + rightCount + 1; // 左右子树节点个数之和再加上当前节点即为整棵二叉树的节点个数
}

​ 如果不使用递归，则可以使用广度优先搜索（BFS）算法，以层次遍历的方式依次访问每一个节点，并统计节点个数，直到遍历完整个二叉树。

​ 下面是一个使用非递归方式计算二叉树节点个数的示例代码：

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
class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

int countNodes(TreeNode* root) {
    if (root == NULL) return 0; // 边界条件
    queue<TreeNode*> q;
    q.push(root);
    int count = 0;
    while (!q.empty()) {
        int n = q.size(); // 当前层节点个数
        for (int i = 0; i < n; i++) {
            TreeNode* node = q.front();
            q.pop();
            count++; // 统计节点个数
            if (node->left != NULL) q.push(node->left); // 将左子节点加入队列
            if (node->right != NULL) q.push(node->right); // 将右子节点加入队列
        }
    }
    return count;
}

​ 以上是两种计算二叉树节点个数的实现方式，可以根据需要选择合适的方法。

5.5.8 判断二叉树是否平衡

​ 判断二叉树是否平衡可以使用递归的方式实现。一个二叉树是平衡二叉树，当且仅当左子树和右子树的高度差不超过1，并且左右子树都是平衡二叉树。

下面是一个使用递归方式判断二叉树是否平衡的示例代码：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

int getHeight(TreeNode* root) {
    if (root == NULL) return 0; // 空节点的高度为0
    int leftHeight = getHeight(root->left); // 计算左子树高度
    int rightHeight = getHeight(root->right); // 计算右子树高度
    return max(leftHeight, rightHeight) + 1; // 左右子树高度的最大值加1即为当前节点所在的高度
}

bool isBalanced(TreeNode* root) {
    if (root == NULL) return true; // 空节点是平衡二叉树
    int leftHeight = getHeight(root->left); // 计算左子树高度
    int rightHeight = getHeight(root->right); // 计算右子树高度
    if (abs(leftHeight - rightHeight) > 1) return false; // 左右子树高度差超过1，不是平衡二叉树
    return isBalanced(root->left) && isBalanced(root->right); // 递归判断左右子树是否都是平衡二叉树
}

​ 以上是使用递归方式判断二叉树是否平衡的实现代码，可以根据需要进行调整。

5.5.9 获取二叉树中最大或最小值

​ 获取二叉树中最大或最小值可以使用递归或非递归方式实现。其中递归的方法比较简单，只需要分别获取左子树和右子树的最大或最小值，并与当前节点的值进行比较，选择最大或最小值即可。

​ 下面是一个使用递归方式获取二叉树中最大和最小值的示例代码：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

int getMax(TreeNode* root) {
    if (root == NULL) return INT_MIN; // 空节点返回无穷小
    int leftMax = getMax(root->left); // 获取左子树最大值
    int rightMax = getMax(root->right); // 获取右子树最大值
    return max(root->val, max(leftMax, rightMax)); // 当前节点、左子树最大值、右子树最大值三者中的最大值即为整棵二叉树中的最大值
}

int getMin(TreeNode* root) {
    if (root == NULL) return INT_MAX; // 空节点返回无穷大
    int leftMin = getMin(root->left); // 获取左子树最小值
    int rightMin = getMin(root->right); // 获取右子树最小值
    return min(root->val, min(leftMin, rightMin)); // 当前节点、左子树最小值、右子树最小值三者中的最小值即为整棵二叉树中的最小值
}

​ 如果不使用递归，则可以使用深度优先搜索（DFS）算法，以前序遍历的方式依次访问每个节点，并记录当前最大或最小值。

​ 下面是一个使用非递归方式获取二叉树中最大和最小值的示例代码：

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
class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

int getMax(TreeNode* root) {
    if (root == NULL) return INT_MIN; // 边界条件
    stack<TreeNode*> stk;
    stk.push(root);
    int maxVal = INT_MIN;
    while (!stk.empty()) {
        TreeNode* node = stk.top();
        stk.pop();
        maxVal = max(maxVal, node->val); // 更新最大值
        if (node->left != NULL) stk.push(node->left); // 将左子节点加入栈
        if (node->right != NULL) stk.push(node->right); // 将右子节点加入栈
    }
    return maxVal;
}

int getMin(TreeNode* root) {
    if (root == NULL) return INT_MAX; // 边界条件
    stack<TreeNode*> stk;
    stk.push(root);
    int minVal = INT_MAX;
    while (!stk.empty()) {
        TreeNode* node = stk.top();
        stk.pop();
        minVal = min(minVal, node->val); // 更新最小值
        if (node->left != NULL) stk.push(node->left); // 将左子节点加入栈
        if (node->right != NULL) stk.push(node->right); // 将右子节点加入栈
    }
    return minVal;
}

​ 以上是两种获取二叉树中最大或最小值的实现方式，可以根据需要选择合适的方法。

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用