前序遍历 （根 -> 左 -> 右）

核心思想：先处理根节点，再处理子树
类比：就像拆快递时，先拆最外层的箱子（根），再一层层拆内部的小盒子（子树）。

复制一棵树

• 为什么用前序：复制时必须先创建根节点，再递归复制左、右子树。
• 如果先复制子树，根节点还没创建，整个结构就乱了。
• 例子：

typedef struct BtNode
{
    /* data */
    BtElemtype data;
    struct BtNode *lchild, *rchild; 
    BtNode(BtElemtype x): data(x), lchild(nullptr), rchild(nullptr){}
}BtNode,*Btree;

Btree copy_tree(Btree root){
    if(!root) return nullptr;
    BtNode *new_root = new BtNode(root->data);      // 1. 先复制根节点
    new_root->lchild = copy_tree(root->lchild);     // 2. 复制左子树
    new_root->rchild = copy_tree(root->rchild);     // 3. 复制右子树
    return new_root;
}

---

序列化与反序列化

生成线性结构（如字符串）以存储或传输二叉树，反序列化时通过根节点快速重建。

序列化

1. 递归遍历：按照根 → 左 → 右的顺序访问节点。
2. 处理空节点：遇到空节点时，用特殊符号（如 #）表示。
3. 分隔符：用逗号（,）或其他符号分隔节点值，避免歧义。

示例

假设二叉树如下

       1
      / \
     2   3
        / \
       4   5

序列化后的字符串为：”1,2,#,#,3,4,#,#,5,#,#”

详细过程

• 根节点 1 → 写入 1
• 左子树 2：
  • 2 的左子树为空 → 写入 #
  • 2 的右子树为空 → 写入 #
• 右子树 3：
  • 3 的左子树 4 → 4 的左右子树为空 → 写入 4,#,#
  • 3 的右子树 5 → 5 的左右子树为空 → 写入 5,#,#

代码如下：

// 二叉树序列化 
std::string serialize(Btree T){
    if(!T) return "#";

    // T->data 为 字符类型
    // return std::string(1,T->data) + ',' + serialize(T->lchild) + ',' + serialize(T->rchild); 

    // T->data 为 数值类型
    return std::to_string(T->data) + "," + serialize(T->lchild) + "," + serialize(T->rchild);

    // T->data 为字符串类型
    // return T->data + "," + serialize(T->lchild) + "," + serialize(T->rchild);
}

反序列化

核心思想：按前序顺序逐个读取节点值，递归重建树。

具体步骤

• 分割字符串：将序列化后的字符串按分隔符（如逗号）拆分成列表。
• 递归构建：
  • 取出列表第一个元素作为根节点。
  • 剩余元素递归构建左子树。
  • 继续递归构建右子树。
• 终止条件：遇到 # 表示空节点，直接返回。

示例

以序列化字符串 "1,2,#,#,3,4,#,#,5,#,#" 为例：

1. 分割为列表：["1", "2", "#", "#", "3", "4", "#", "#", "5", "#", "#"]
2. 递归过程：
   • 根节点 1 → 创建节点 1
   • 构建左子树：
     • 根节点 2 → 创建节点 2
     • 左子树：# → 返回空
     • 右子树：# → 返回空
   • 构建右子树：
     • 根节点 3 → 创建节点 3
     • 左子树 4 → 创建节点 4
       • 左子树：# → 空
       • 右子树：# → 空
     • 右子树 5 → 创建节点 5
       • 左子树：# → 空
       • 右子树：# → 空

最终还原的树结构与原树一致。

代码如下：

#include<iostream>
#include<string>
#include<vector>
#include<regex>

// 分割为列表
std::vector<std::string> split(const std::string str, const std::string delimiter){
    std::vector<std::string> tokens;

    // 分隔符
    std::regex reg(delimiter);

    // C++ 11 字符串分割  regex_token_iterator , 指定 -1 作为参数来获取分隔符之间的内容
    std::sregex_token_iterator pos(str.begin(), str.end(), reg, -1);

    // std::sregex_token_iterator end; 默认构造函数会生成一个特殊的“尾后迭代器” (“无效”)
    decltype(pos) end;

    for(; pos != end; pos++) tokens.push_back(pos->str());
    
    return tokens;

} 

// 前序递归建树
void build_tree(std::vector<std::string> &tokens, Btree &T){
    if(!tokens.empty()){
        // 取第一个元素，若为#, 则返回null
        std::string node = tokens.front();

        // 删除头元素，因为需要对 tokens 删除操作，所以参数为引用传递
        tokens.erase(tokens.begin());

        if(node == "#")  T = nullptr;
        // 否则创建根节点及左右子树
        else
        {  
            T = new BtNode(std::stoi(node));
            // 创建左子树
            build_tree(tokens, T->lchild);
            // 创建右子树
            build_tree(tokens, T->rchild);
        }
    }
}

// 反序列化
void deserialize(std::string TreeStr, Btree &T){
    // 分割为列表
   std::string delimiter = ",";

   std::vector<std::string> tokens = split(TreeStr, delimiter);

   // 前序递归建树
   build_tree(tokens, T);
}

//测试
int main(){
    std::string treeStr = "1,2,#,#,3,4,#,#,5,#,#";

    Btree root;
    deserialize(treeStr, root);
    std::cout << root->rchild->rchild->data;
  
    return 0;
}
/*
输出结果：
5
*/

---

表达式的前缀表示（波兰式）

---

目录结构展示

类似 ls -R 命令，先显示当前目录再递归子目录。

比如：

/home/
  → Documents/
    → file1.txt
  → Downloads/
    → movie.mp4

模拟文件目录系统

---

UI渲染

先渲染父组件，再处理子组件，确保父级布局影响子级。

---

中序遍历（左 – 根 – 右）

核心思想：先处理左子树，再处理根，最后右子树
类比：看书时先看目录左边章节（左），再看当前章节（根），最后看右边章节（右）。

二叉搜索树（BST）的有序输出

• BST特性：左子节点 < 根 < 右子节点。
• 中序遍历会按“左→根→右”顺序访问，结果就是升序排列。
• 应用场景：数据库索引的有序遍历、手机通讯录按名字排序。

---

修复BST错误节点

• 问题：BST中有两个节点被错误交换，导致中序遍历结果无序。
• 修复方法：通过中序遍历找到不符合升序的位置，交换这两个节点。

---

表达式树的中缀表达式

---

语法分析

在编译器中按顺序解析操作符优先级。

---

后序遍历 （左 – 右 – 根）

核心思想：先处理子树，再处理根节点
类比：搬家公司拆家具时，先拆零件（子树），最后拆主框架（根）。

释放二叉树的内存

• 为什么用后序：必须先删除子节点，再删除父节点。
• 如果先删父节点，子节点就变成“孤儿”，导致内存泄漏。
• 例子：

void DestoryTree(Btree &T){
    if(T){
        DestoryTree(T->lchild);    // 1.释放左子树
        DestoryTree(T->rchild);    // 2.释放右子树
        delete T;                  // 3.释放根节点
        T = nullptr;
    }
}

---

计算目录总大小

• 统计子目录大小：先计算所有子目录的大小，再汇总到当前目录。
• 比如：

/home/ (总大小 = Documents + Downloads)
  → Documents/ (大小 = 100MB)
  → Downloads/ (大小 = 200MB)

---

表达式树的后缀表示

---

依赖处理

如编译顺序，先编译依赖项再处理上层模块。

---

层次遍历（按层遍历，BFS）

核心思想：逐层处理节点，从上到下、从左到右
类比：公司开会时，CEO先讲话（第一层），然后是部门经理（第二层），最后是员工（第三层）。

最短路径问题

• 无权图的最短路径：层次遍历保证第一次到达目标节点时，路径步数最少。
• 例子：迷宫问题中，按层遍历可以找到出口的最短路径。

---

判断是否为完全二叉树

• 完全二叉树定义：所有层除了最后一层外都是满的，最后一层节点靠左。
• 层次遍历时，如果遇到空节点后还有非空节点，就不是完全二叉树。

---

社交网络的好友推荐

• 一度好友 → 二度好友 → 三度好友：按层次遍历扩展人际关系。
• 比如：微信中“朋友的朋友”推荐。

---

并行处理

同一层节点可并发处理，提升效率。

---

总结

遍历方式	核心顺序	典型场景	一句话理解
前序遍历	根 → 左 → 右	复制树、前缀表达式、UI渲染	先干正事，再处理细节
中序遍历	左 → 根 → 右	BST有序输出、中缀表达式	先整理左边，再处理自己
后序遍历	左 → 右 → 根	释放内存、后缀表达式、依赖处理	先搞定小弟，再处理老大
层次遍历	按层遍历（BFS）	最短路径、社交推荐、结构验证	一层一层来，不跳步不越级