Hi~ o(*￣▽￣*)ブ， everyone， 上周的链表学习的难度还好吧，如果觉得有些地方太敷衍了，可以反馈的，需要批评才能进步，anyway，之前因为一些心事吧，更新速度是周更，之后会改进的，链表的一些高难操作不着急学习，因为本身学习不是一蹴而就的，不能因为看了我一篇blog就可以说是精通链表了，一些高难的习题我会专门写一篇讲解的，如果有不理解的地方直接在评论区发言即可，我是云狗！很高兴再教你一节课

---

叠甲：本文可能存在一些不严谨甚至不正确的话，深入研究C++的学者请谨慎辨别！本文主要面向刚学完C++语法不知道下一步该怎么走的人群

让我们认识树的 What Why How

（如果你之前就接触过数据结构的话，可以直接跳过这里）

学完链表你会发现链表在处理一些连续数据或者插入一些数据的时候变得很好用，虽然不如array数组，vector数组拥有那种快速高效的查找的能力，但是山人自有妙计，先不急~，前几天在三角洲长弓西谷卖命的时候，发现一节节的车厢用链表是很好实现的（如下）：

#include <iostream>
using namespace std;

class items
{
private:
    string color;
    unsigned int value;
public:
    items();
    ~items();
};

items::items()
{
    color = "golden";
    value = 50000;
}
items::~items(){}

class train
{
private:
    int container_num;
    items golden_cup;
    
public:
    train* next;
    train(int num);
    ~train();
    void detail();

};

train::train(int num):container_num(num=3)
{

}

train::~train()
{
}

void train::detail()
{
    cout<<"there are "<< container_num <<"containers in the train"<<endl;
    cout<<"predict there is only one golden cup"<<endl;
}

void test()
{
    train car1(0);
    train car2(3);
    train car3(0);
    car1.next = &car2;
    car2.next = &car3;
    
    cout<<"虽然很草率但是我们的确用链表模拟了一辆列车"<<endl;
}

但是随着赛季任务，在溪谷经常有一些为了自己的任务指标来这里搞破坏的，这些搞破坏的主要是因为自己无法和那些深度玩家或者天赋玩家抗衡而出此下策，至此我们发现，虽然这是一款游戏但是它分明的分成了若干的群体，玩家这个概念下会有众多的分支，轻度玩家、深度玩家、重度玩家、天赋玩家、临时观光客……

But 一个链表似乎无法实现元素的分类，即使这种元素的分类事实上很常见，比如家谱之类的。我们发现主要的矛盾就是链表是线性的，一个指针似乎根本不够用，那么我们多加几个不就得了，恭喜你！发现了树，我们会逐渐认识到树的强大与高效性，我们最常用的树便是二叉树，至于原因简单来讲就是二叉树具有很多便于逻辑推导的性质，以及和二进制高度匹配。

让我们种一棵树

#include <iostream>
#include <queue>  // 用于层序遍历
#include <stack>  // 用于迭代遍历
using namespace std;

// 二叉树节点
struct TreeNode {
    int val;
    TreeNode* left;  // 左子节点
    TreeNode* right; // 右子节点
    // 构造函数
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 二叉树操作
class BinaryTree {
private:
    TreeNode* root;

    // 辅助函数：递归销毁树（析构用）
    void destroy(TreeNode* node) {
        if (node == nullptr) return;
        destroy(node->left);   // 先销毁左子树
        destroy(node->right);  // 再销毁右子树
        delete node;           // 最后销毁当前节点
    }

public:
    BinaryTree() : root(nullptr) {}

    ~BinaryTree() {
        destroy(root);  // 析构时释放所有节点
        root = nullptr;
    }

};

这便是一棵树的最基础的状态了，但是很显然这棵树没什么用……

我们先进一步了解一下树，之后再来给它一些函数使其变成强大的编程工具

树的分类

• 二叉树：每个节点最多有 2 个子节点（左子树、右子树），是最常用的树结构。
   
• 二叉搜索树（BST）：左子树所有节点值 < 根节点值 < 右子树所有节点值（便于快速查找）
   
• 平衡树：左右子树高度差不超过 1（如 AVL 树、红黑树，避免 BST 退化为链表）
   
• 完全二叉树：除最后一层外，每层节点全满，最后一层节点靠左排列（适合数组存储，如堆）
   
• 满二叉树：所有叶子节点在同一层，且非叶子节点都有 2 个子节点。

当然树其实比上述列举的多得多，例如字典树，B+树，败者树，博弈树等等……

树的术语

（这里要特别注意叶子节点不只是最下面一层的节点，根据描述应该顺着分支直到找到一个无子节点的子节点无论它的深度和高度是什么，例如下图的5也是叶子结点）

（虽然叫树，但其实理解成根和根上的瘤可能会更贴切一点，（-_-ll））

• 节点（Node）：包含数据（data）和指向子节点的指针（或引用）
• 根节点（Root）：树的起点，没有父节点（如树干的根基）
• 父节点 / 子节点：若节点 A 指向节点 B，则 A 是 B 的父节点，B 是 A 的子节点（子节点间互称兄弟节点）
• 叶子节点（Leaf）：没有子节点的节点（如树的末端）
• 深度（Depth）：从根节点到当前节点的边数（根节点深度为 0）
• 高度（Height）：从当前节点到最深叶子节点的边数（叶子节点高度为 0）
• 树的高度：根节点的高度

到这里结合图例我们结合 分治的定义 可以得到一个结论，树的结构以及一些性质十分契合递归的调用（因为可以拆分成多个子问题），这也是为什么树的一些操作和算法会频繁使用递归的原因。

树的基本操作

1.插入（BST规则：比较之下，小数放左边，大数放右边）

    //辅助函数
    TreeNode* insertBTS(TreeNode* node, int val){
        if(node == nullptr){
            return new TreeNode(val);
        }

        if(val < node->val){
            insertBTS(node->left,val);
        }else{
            insertBTS(node->right,val);
        }
        return node;
    }

    void Insert(TreeNode* node,int val){
        root = insertBTS(root,val);
    }

2.树的遍历***

树的遍历有五种，以下四种都很重要且经典，年年考，年年不能错 ，其中BFS的迭代法涉及到了第五种遍历，即层序遍历，层序遍历简单来讲就是从上到下，不断从左到右，依次遍历（标号），在树的一些术语中的图例的标号就是层序遍历，（但是由于BFS的递归代码有点复杂，所以给出了另一种迭代代码）

这四种分别是 深度优先遍历（DFS），广度优先遍历（BFS）以及它们的迭代和递归版本

这四种遍历中又有前序遍历，中序遍历，后序遍历三种子模式

这三种子模式的记忆方式很简单，前、中、后分别对应着根节点访问的优先级

DFS（迭代）

void inorderIterative() {
    cout << "中序遍历（迭代）: ";
    stack<TreeNode*> st;
    TreeNode* curr = root;

    // 思路：左链入栈 → 弹出访问 → 转向右子树
    while (curr != nullptr || !st.empty()) {
        // 左子树全部入栈
        while (curr != nullptr) {
            st.push(curr);
            curr = curr->left;
        }
        // 弹出栈顶（最左节点）并访问
        curr = st.top();
        st.pop();
        cout << curr->val << " ";
        // 转向右子树
        curr = curr->right;
    }
    cout << endl;
}

DFS（递归）

// 前序遍历（递归）
void preorder(TreeNode* node) {
    if (node == nullptr) return;
    cout << node->val << " ";  
    preorder(node->left);      
    preorder(node->right);    
}

// 中序遍历（递归）
void inorder(TreeNode* node) {
    if (node == nullptr) return;
    inorder(node->left);      
    cout << node->val << " ";  
    inorder(node->right);      
}

// 后序遍历（递归）
void postorder(TreeNode* node) {
    if (node == nullptr) return;
    postorder(node->left);     
    postorder(node->right);    
    cout << node->val << " ";  
}

// 对外接口
void preorderTraversal() {
    cout << "前序遍历: ";
    preorder(root);
    cout << endl;
}
void inorderTraversal() {
    cout << "中序遍历: ";
    inorder(root);
    cout << endl;
}
void postorderTraversal() {
    cout << "后序遍历: ";
    postorder(root);
    cout << endl;
}

BFS（迭代）

void inorderIterative() {
    cout << "中序遍历（迭代）: ";
    stack<TreeNode*> st;
    TreeNode* curr = root;

    // 思路：左链入栈 → 弹出访问 → 转向右子树
    while (curr != nullptr || !st.empty()) {
        // 左子树全部入栈
        while (curr != nullptr) {
            st.push(curr);
            curr = curr->left;
        }
        // 弹出栈顶（最左节点）并访问
        curr = st.top();
        st.pop();
        cout << curr->val << " ";
        // 转向右子树
        curr = curr->right;
    }
    cout << endl;
}

BFS（另一种迭代）

这里要是没太看懂的话，可以自己模拟一遍，这里涉及到了一种特殊的遍历的方式，层序遍历

void levelOrder() {
    cout << "层序遍历: ";
    if (root == nullptr) return;

    queue<TreeNode*> q;
    q.push(root);  // 根节点入队

    while (!q.empty()) {
        int levelSize = q.size();  // 当前层的节点数
        // 遍历当前层所有节点
        for (int i = 0; i < levelSize; ++i) {
            TreeNode* curr = q.front();
            q.pop();
            cout << curr->val << " ";  // 访问当前节点

            // 左子节点入队
            if (curr->left != nullptr) q.push(curr->left);
            // 右子节点入队
            if (curr->right != nullptr) q.push(curr->right);
        }
    }
    cout << endl;
}

3.查找

这个其实和插入的操作十分相似

TreeNode* searchBST(TreeNode* node, int target) {
    if (node == nullptr || node->val == target) {
        return node;  // 找到或为空
    }
    if (target < node->val) {
        return searchBST(node->left, target);  // 左子树查找
    } else {
        return searchBST(node->right, target); // 右子树查找
    }
}

// 对外接口
bool find(int target) {
    return searchBST(root, target) != nullptr;
}

4.删除（最复杂的一集）

首先实现操作的前提是能够正确处理各种状态

1.对于叶子节点，直接删掉就好

2.如果节点A只有一个子节点，把A节点的父节点的指针直接指向A节点的子节点,然后删掉A

3.对于节点A有两个子节点，那右子树的最小节点复制到当前节点并且删除该最小节点

// 在BinaryTree类中添加：
// 找到以node为根的BST中的最小节点（最左节点）
TreeNode* findMin(TreeNode* node) {
    while (node->left != nullptr) {
        node = node->left;
    }
    return node;
}

// 删除BST中的节点
TreeNode* deleteBST(TreeNode* node, int val) {
    if (node == nullptr) return nullptr;  // 未找到节点

    if (val < node->val) {
        node->left = deleteBST(node->left, val);  // 左子树删除
    } else if (val > node->val) {
        node->right = deleteBST(node->right, val); // 右子树删除
    } else {
        // 找到目标节点，分3种情况
        // 1. 叶子节点或只有一个子节点
        if (node->left == nullptr) {
            TreeNode* temp = node->right;
            delete node;
            return temp;
        } else if (node->right == nullptr) {
            TreeNode* temp = node->left;
            delete node;
            return temp;
        }

        // 2. 有两个子节点：找右子树最小节点替代
        TreeNode* temp = findMin(node->right);
        node->val = temp->val;  // 复制值
        // 删除替代节点
        node->right = deleteBST(node->right, temp->val);
    }
    return node;
}

// 对外接口
void remove(int val) {
    root = deleteBST(root, val);
}

树的核心算法（Part1）

鉴于大家今天已经学习了不少了，所以我们不会上立刻很高难度的算法，先来一个最最简单的开开胃

获得树的深度

int getHeight(TreeNode* node) {
    if (node == nullptr) return -1;  // 空节点高度为-1（叶子节点高度为0）
    int leftHeight = getHeight(node->left);
    int rightHeight = getHeight(node->right);
    return max(leftHeight, rightHeight) + 1;
}

---

好啦，辛苦了，对于深入树这个数据结构不要一口气学完，不然很容易头疼，倒不如趁热打铁，先把今天学的知识先好好实现一次，事已至此，现在我给予你一处篝火，烤烤棉花糖，听听歌吧~

Bye！ **恭喜获得10k蛤符币 :P **