C++ 怎么实现二叉树 C++节点定义与前中后序遍历【数据结构】_技术教程

C++二叉树节点应定义为struct，含int val及初始化为nullptr的left、right指针，并提供无参、单参、三参构造函数；前序/中序/后序递归遍历均需先判空，仅处理顺序不同；非递归遍历用stack模拟，中序需持续向左入栈再弹出转向右；建树时禁用局部变量地址，须用new或智能指针确保生命周期安全。

怎么定义 C++ 二叉树节点（带构造函数和 nullptr 安全）

直接用 struct 最简洁，关键是要默认初始化指针为 nullptr，避免野指针；同时加一个带参构造函数，方便快速创建节点。

val 存数据，类型按需改（比如 int 或 string）
left 和 right 必须初始化为 nullptr，否则递归遍历时可能崩溃
不写析构函数也没问题——除非你用了 new 分配子节点且需要手动释放（一般推荐栈上创建或智能指针）

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

前序/中序/后序遍历的递归写法（统一模板，只差顺序）

三者结构完全一致：都是“访问当前 → 递归左 → 递归右”，区别只在打印/处理 root->val 的位置。记住口诀：“前根左右、中左根右、后左右根”。

前序：处理 root → traverse(root->left) → traverse(root->right)
中序：递归左 → 处理 root → 递归右（BST 中序即升序）
后序：递归左 → 递归右 → 处理 root（适合删树、求高度等依赖子树结果的场景）
所有递归函数必须判空：if (!root) return;，否则访问 nullptr->val 直接段错误

void preorder(TreeNode* root) {
    if (!root) return;
    cout << root->val << " ";      // 前序：根最先
    preorder(root->left);
    preorder(root->right);
}

非递归遍历怎么写（用 stack 模拟调用栈）

递归本质是系统用栈保存现场，自己模拟时核心是「什么时候 push、什么时候 pop、什么时候记录结果」。前序最简单，中序次之，后序最难——别硬记，用「标记法」统一处理。

前序非递归：先压右再压左（因为栈是后进先出，要保证左先被处理）
中序非递归：一路向左入栈，到底后弹出并转向右子树
后序推荐「标记法」：每个节点压栈两次，第一次带 false 标记（表示未处理子树），第二次带 true（可输出）。遇到 true 才记录值
注意：非递归代码里 stack 不够，得用 stack> 或自定义结构体

// 中序非递归示例
void inorder_iterative(TreeNode* root) {
    stack st;
    TreeNode* cur = root;
    while (cur || !st.empty()) {
        while (cur) {
            st.push(cur);
            cur = cur->left;  // 一直压左
        }
        cur = st.top(); st.pop();
        cout << cur->val << " ";  // 此时左子树已完，访问根
        cur = cur->right;         // 转向右
    }
}

为什么建树时容易崩？常见空指针陷阱

新手常在构建测试树时崩溃，根本原因不是遍历逻辑错，而是节点指针没连对，或者连了局部变量地址。

立即学习“C++免费学习笔记（深入）”；

别这样写：TreeNode node(1); TreeNode* root = &node; —— node 是栈变量，函数返回后地址失效
正确方式：用 new（记得 delete）或更推荐用智能指针 unique_ptr
手动连子节点时，漏写 root->left = ... 或写成 root->left->left = ...（中间为 nullptr 时解引用必崩）
调试技巧：遍历前加一句 assert(root != nullptr);，或用 if (!root) { cout