前面的博文，我们详细介绍了链表，包括单向链表和双向链表及他们的增删改查，这一篇开始我们开始介绍二叉树。

文章目录

一、递归

在使用二叉树的过程中，我们将要高频的使用递归函数，所以这里我们首先来引入递归的概念和递归函数的定义及使用。

1.引入递归
明确递归的定义：递归是指在函数的定义中使用函数自身的方法。在递归过程中，函数会不断地调用自身来解决规模更小的子问题，直到达到某个终止条件，然后逐步返回结果。
 以计算阶乘为例，进一步加深学生对递归的理解。阶乘是一个经典的递归问题，其定义为：$n! = n\times(n - 1)!$，当 $n = 0$ 或 $n = 1$ 时，$n! = 1$。
- 展示阶乘的递归代码：

#include <iostream>

// 递归计算阶乘
int factorial(int n) {
    if (n == 0 || n == 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

int main() {
    int num = 5;
    std::cout << "Factorial of " << num << " is " << factorial(num) << std::endl;
    return 0;
}
2. 双向链表使用递归
回顾双向链表的基本概念，双向链表是一种线性数据结构，由节点组成。每个节点包含数据、指向前一个节点的指针（`prev`）和指向后一个节点的指针（`next`），允许在链表中进行双向遍历。
展示双向链表的代码实现：

#include <iostream>

// 定义双向链表节点结构
struct DListNode {
    int data;
    DListNode* prev;
    DListNode* next;
    DListNode(int val) : data(val), prev(nullptr), next(nullptr) {}
};

// 递归打印双向链表
void printDListRecursive(DListNode* node) {
    if (node == nullptr) {
        return;
    }
    std::cout << node->data << " ";
    printDListRecursive(node->next);
}

int main() {
    // 创建双向链表
    DListNode* head = new DListNode(1);
    DListNode* second = new DListNode(2);
    DListNode* third = new DListNode(3);

    head->next = second;
    second->prev = head;
    second->next = third;
    third->prev = second;

    // 递归打印双向链表
    std::cout << "Recursive print of doubly linked list: ";
    printDListRecursive(head);
    std::cout << std::endl;

    return 0;
}

 详细解释双向链表的节点结构以及递归打印函数的实现原理。强调递归终止条件（当节点为 `nullptr` 时停止递归）和递归调用过程（不断调用自身处理下一个节点），让学生体会递归在链表遍历中的应用。

二、二叉树的概念

1. 二叉树的概念
介绍二叉树的定义：二叉树是每个节点最多有两个子节点的树结构，分别称为左子节点和右子节点。强调二叉树是一种层级式数据结构，与双向链表这种线性数据结构有着本质的区别。线性数据结构中的元素是依次排列的，像双向链表，节点一个接着一个，只能沿着前后方向依次访问；而二叉树的节点通过分支形成了层级关系，可以更高效地表示和处理具有层次关系的数据，如文件系统、组织结构等。
再举例其他数据结构，如栈和队列。栈是一种后进先出（LIFO）的数据结构，类似于一摞盘子，最后放上去的盘子最先被拿走；队列是一种先进先出（FIFO）的数据结构，如同排队买票，先到的人先买到票。它们和二叉树、双向链表在结构和应用场景上都有所不同。
2.二叉树的节点结构
- 展示二叉树节点的 C++ 代码实现：

// 定义二叉树节点结构
struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

三、代码实现

1. 构建二叉树
讲解如何使用递归方法构建二叉树。递归构建二叉树的思路是，对于每个节点，先创建该节点，然后递归地创建其左子树和右子树，直到达到递归终止条件。
展示构建至少 5 个层级的二叉树的代码：

#include <iostream>

// 定义二叉树节点结构
struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

// 递归构建二叉树
TreeNode* buildTree(int level) {
    if (level > 5) {
        return nullptr;
    }
    TreeNode* node = new TreeNode(level);
    node->left = buildTree(level + 1);
    node->right = buildTree(level + 1);
    return node;
}

// 前序遍历二叉树
void preOrderTraversal(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    std::cout << root->data << " ";
    preOrderTraversal(root->left);
    preOrderTraversal(root->right);
}

// 中序遍历二叉树
void inOrderTraversal(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    inOrderTraversal(root->left);
    std::cout << root->data << " ";
    inOrderTraversal(root->right);
}

// 后序遍历二叉树
void postOrderTraversal(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    postOrderTraversal(root->left);
    postOrderTraversal(root->right);
    std::cout << root->data << " ";
}

int main() {
    // 构建二叉树
    TreeNode* root = buildTree(1);

    // 前序遍历二叉树
    std::cout << "Pre-order traversal: ";
    preOrderTraversal(root);
    std::cout << std::endl;

    // 中序遍历二叉树
    std::cout << "In-order traversal: ";
    inOrderTraversal(root);
    std::cout << std::endl;

    // 后序遍历二叉树
    std::cout << "Post-order traversal: ";
    postOrderTraversal(root);
    std::cout << std::endl;

    return 0;
}

详细解释代码中递归构建二叉树的过程，以及前序、中序、后序遍历的递归实现。强调递归终止条件的重要性，即当达到指定的层级（这里是 5 层）时，停止递归调用，返回 `nullptr`。对比双向链表和二叉树的构建过程，指出双向链表是依次创建节点并连接，而二叉树是通过递归在每个节点处向两个方向扩展。

四、三种遍历方式的区别及应用场景

1. 前序、中序、后序遍历的区别

三种遍历方式都是基于递归的思想，会从根节点开始逐步深入子树，但对根节点数据成员的访问顺序不同，具体如下：
前序遍历：按照“数 - 左 - 右”的顺序进行遍历。这里的“数”指的是访问当前节点的数据成员。也就是在递归过程中，先对当前节点的数据进行访问操作（比如打印），接着递归遍历其左子树，最后递归遍历其右子树。例如对于一个简单的二叉树，根节点为 A，左子节点为 B，右子节点为 C，前序遍历的结果就是 A - B - C。
中序遍历：遵循“左 - 数 - 右”的顺序。即先递归遍历当前节点的左子树，当左子树遍历完后，再访问当前节点的数据成员，最后递归遍历其右子树。对于上述例子，中序遍历的结果可能是 B - A - C（假设 B 没有子节点）。
后序遍历：采用“左 - 右 - 数”的顺序。先递归遍历当前节点的左子树，再递归遍历其右子树，最后才访问当前节点的数据成员。对于上述例子，后序遍历的结果是 B - C - A。

可以结合以下简单的代码逻辑差异来理解：

// 前序遍历
void preOrder(TreeNode* root) {
    if (root == nullptr) return;
    // 先访问根节点的数据
    std::cout << root->data << " "; 
    preOrder(root->left);
    preOrder(root->right);
}

// 中序遍历
void inOrder(TreeNode* root) {
    if (root == nullptr) return;
    inOrder(root->left);
    // 中间访问根节点的数据
    std::cout << root->data << " "; 
    inOrder(root->right);
}

// 后序遍历
void postOrder(TreeNode* root) {
    if (root == nullptr) return;
    postOrder(root->left);
    postOrder(root->right);
    // 最后访问根节点的数据
    std::cout << root->data << " "; 
}
2.应用场景

1、前序遍历
复制二叉树：在复制一棵二叉树时，前序遍历可以先复制根节点的数据，然后依次复制左子树和右子树，保证树的结构能够正确复制。因为前序遍历先处理根节点的数据，符合构建新树时从根开始的逻辑。
表达式树求值：在表达式树中，前序遍历可以方便地得到前缀表达式，用于某些特定的计算场景。前缀表达式在编译原理和计算器算法中有重要应用。
2、中序遍历
二叉搜索树：对于二叉搜索树（左子树节点值小于根节点，右子树节点值大于根节点），中序遍历可以得到一个有序的节点数据序列，方便进行数据的排序和查找。利用中序遍历的特性可以高效地对二叉搜索树中的数据进行从小到大的排序输出。
3、 后序遍历
内存释放：在释放二叉树的内存时，后序遍历可以先释放子节点的内存，最后释放根节点的内存，避免内存泄漏。因为先释放子节点可以确保子节点占用的资源先被回收，再释放根节点。
计算目录大小：在文件系统中，如果把目录结构看作二叉树，后序遍历可以先计算子目录的大小，再计算父目录的大小。先计算子目录能为父目录大小计算提供基础数据。

（1）、二叉搜索树的查找操作

  1. 结合二分法理解查找操作
    在二叉搜索树中查找一个特定的值时，二分法的思想体现得更为明显。我们知道二分法在有序数组中通过不断比较中间元素与目标值的大小，将搜索范围缩小一半。在二叉搜索树中，我们从根节点开始，将目标值与当前节点的值进行比较：
    如果目标值等于当前节点的值，那么查找成功。
    如果目标值小于当前节点的值，由于二叉搜索树的性质，我们可以确定目标值只可能存在于左子树中，于是我们进入左子树继续查找，这就如同二分法中缩小搜索范围到左半部分。
    如果目标值大于当前节点的值，那么目标值只可能存在于右子树中，我们进入右子树继续查找，类似二分法中缩小搜索范围到右半部分。

  2. 查找操作的代码实现

// 在二叉搜索树中查找值
bool search(TreeNode* root, int val) {
    if (root == nullptr) {
        return false;
    }
    if (root->data == val) {
        return true;
    } else if (val < root->data) {
        return search(root->left, val);
    } else {
        return search(root->right, val);
    }
}

// 在 main 函数中测试查找操作
int main() {
    TreeNode* root = nullptr;
    root = insert(root, 3);
    root = insert(root, 1);
    root = insert(root, 4);
    root = insert(root, 2);

    int target = 4;
    if (search(root, target)) {
        std::cout << target << " found in the binary search tree." << std::endl;
    } else {
        std::cout << target << " not found in the binary search tree." << std::endl;
    }

    return 0;
}
（2）、表达式树求值

表达式树的概念引入
在计算机科学中，我们经常需要对数学表达式进行计算，比如 (3 + 4) * 5。为了更方便地处理这些表达式，我们可以将其表示为二叉树的形式，这就是表达式树。在表达式树中，叶子节点通常是操作数（如数字 3、4、5），而非叶子节点是运算符（如 +、*）。下面我们详细讲解表达式树的构建和求值。
表达式树的构建
以表达式 (3 + 4) * 5 为例，我们可以构建如下的表达式树。根节点是运算符 ，其左子树的根节点是运算符 +，+ 的左子节点是操作数 3，右子节点是操作数 4， 的右子节点是操作数 5。通过这种方式，我们将一个复杂的表达式转化为了二叉树的结构，方便后续处理。

// 定义表达式树节点结构
struct ExprTreeNode {
    char data;
    ExprTreeNode*
继续
ExprTreeNode* left;
ExprTreeNode* right;
ExprTreeNode(char val) : data(val), left(nullptr), right(nullptr) {}
};
// 构建表达式树示例
ExprTreeNode* buildExprTree () {
ExprTreeNode* root = new ExprTreeNode ('*');
root->left = new ExprTreeNode ('+');
root->left->left = new ExprTreeNode ('3');
root->left->right = new ExprTreeNode ('4');
root->right = new ExprTreeNode ('5');
return root;
}
  1. 前序遍历在表达式树求值中的应用
    前序遍历表达式树可以得到前缀表达式，前缀表达式也称为波兰式。对于上述表达式树，前序遍历的结果是 * + 3 4 5。在计算前缀表达式的值时，我们可以使用栈来辅助计算。从右到左扫描前缀表达式，遇到操作数就压入栈中，遇到运算符就从栈中弹出两个操作数进行计算，并将结果压入栈中，直到扫描完整个表达式，栈中剩下的唯一元素就是表达式的值。
#include <iostream>
#include <stack>

// 定义表达式树节点结构
struct ExprTreeNode {
    char data;
    ExprTreeNode* left;
    ExprTreeNode* right;
    ExprTreeNode(char val) : data(val), left(nullptr), right(nullptr) {}
};

// 前序遍历表达式树
void preOrderExprTree(ExprTreeNode* root) {
    if (root == nullptr) {
        return;
    }
    std::cout << root->data << " ";
    preOrderExprTree(root->left);
    preOrderExprTree(root->right);
}

// 计算前缀表达式的值
int evaluatePrefix(const std::string& prefix) {
    std::stack<int> stack;
    for (int i = prefix.length() - 1; i >= 0; i--) {
        if (isdigit(prefix[i])) {
            stack.push(prefix[i] - '0');
        } else {
            int operand1 = stack.top();
            stack.pop();
            int operand2 = stack.top();
            stack.pop();
            switch (prefix[i]) {
                case '+':
                    stack.push(operand1 + operand2);
                    break;
                case '-':
                    stack.push(operand1 - operand2);
                    break;
                case '*':
                    stack.push(operand1 * operand2);
                    break;
                case '/':
                    stack.push(operand1 / operand2);
                    break;
            }
        }
    }
    return stack.top();
}

int main() {
    ExprTreeNode* root = buildExprTree();
    std::cout << "Prefix expression: ";
    preOrderExprTree(root);
    std::cout << std::endl;

    std::string prefix = "*+345";
    int result = evaluatePrefix(prefix);
    std::cout << "Result of the expression: " << result << std::endl;

    return 0;
}

五、游戏中的二叉树应用

  1. 场景划分与管理
    在大型 3D 游戏中，场景往往非常复杂，包含大量的物体。为了提高渲染效率，游戏开发者会使用二叉树（如四叉树、八叉树）对场景进行划分。以四叉树为例，它将游戏场景划分为四个子区域，每个子区域又可以继续划分为四个更小的子区域，形成树形结构。
    这样做的好处是，当进行渲染时，只需要遍历与当前摄像机视野相交的子区域，而不需要遍历整个场景，大大减少了渲染的工作量。
  2. AI 决策树
    在游戏的人工智能系统中，决策树是一种常用的技术。决策树可以看作是一棵二叉树，每个节点代表一个决策点，每个分支代表一个决策结果。
    例如，在一个角色扮演游戏中，怪物的 AI 可以使用决策树来决定下一步的行动。根节点可能是“玩家是否在攻击范围内”，如果是，则进入左子树，决定是反击还是躲避；如果不是，则进入右子树，决定是继续巡逻还是寻找资源。

总结

  1. 总结
    回顾二叉树的基本概念、递归思想和代码实现。
    详细对比双向链表和二叉树的区别，强调二叉树作为层级式数据结构与双向链表线性结构的不同，以及栈、队列等其他数据结构的特点。
    强调递归思想的核心要点，如终止条件的确定、问题的分解和子问题的求解。
    总结前序、中序、后序遍历的区别和各自适用场景，明确是根据对根节点数据成员的访问顺序来命名的。
    总结二叉树在游戏开发中的应用场景和作用。
# c++ # 数据结构 # 算法
Logo
乐奇 Rokid 开放社区

更多推荐

cover

TestStar | 接入 AIUI 测试 30 天后，别拿别人的数算自己的账

avatar 乐奇 Rokid 开放社区
cover

SQL 必知必会：手把手教你掌握 MySQL 开窗函数的 4 大核心场景（附代码）

avatar 乐奇 Rokid 开放社区
cover

用 AIUI 打造「免手出行助手」——一篇能跟着做完的智能体实战教程

avatar 乐奇 Rokid 开放社区