### 一、二叉树节点定义
```cpp
struct TreeNode {
    int val;               // 节点存储的值
    TreeNode *left;        // 左子节点指针
    TreeNode *right;       // 右子节点指针
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}  // 构造函数
};

二、二叉树遍历实现

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

递归版：

void preorder(TreeNode* root) {
    if (!root) return;
    cout << root->val << " ";  // 访问根节点
    preorder(root->left);      // 遍历左子树
    preorder(root->right);     // 遍历右子树
}

非递归版（用栈）：

void preorderNonRecursive(TreeNode* root) {
    if (!root) return;
    stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()) {
        TreeNode* node = st.top();
        st.pop();
        cout << node->val << " ";
        if (node->right) st.push(node->right);  // 先右后左，栈特性保证左先访问
        if (node->left) st.push(node->left);
    }
}

2. 中序遍历（左->根->右）

递归版：

void inorder(TreeNode* root) {
    if (!root) return;
    inorder(root->left);       // 遍历左子树
    cout << root->val << " ";  // 访问根节点
    inorder(root->right);      // 遍历右子树
}

非递归版（用栈）：

void inorderNonRecursive(TreeNode* root) {
    if (!root) return;
    stack<TreeNode*> 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;  // 转向右子树
    }
}

3. 后序遍历（左->右->根）

递归版：

void postorder(TreeNode* root) {
    if (!root) return;
    postorder(root->left);     // 遍历左子树
    postorder(root->right);    // 遍历右子树
    cout << root->val << " ";  // 访问根节点
}

非递归版（用栈+标记）：

void postorderNonRecursive(TreeNode* root) {
    if (!root) return;
    stack<pair<TreeNode*, bool>> st;  // 第二个值标记是否访问过
    st.push({root, false});
    while (!st.empty()) {
        auto [node, visited] = st.top();
        st.pop();
        if (visited) {
            cout << node->val << " ";
        } else {
            st.push({node, true});    // 标记为待访问
            if (node->right) st.push({node->right, false});
            if (node->left) st.push({node->left, false});
        }
    }
}

三、二叉树构建（前序+中序）

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    if (preorder.empty()) return nullptr;
    
    // 根节点为前序首元素
    int rootVal = preorder[0];
    TreeNode* root = new TreeNode(rootVal);
    
    // 找中序中根节点位置
    int rootIdx = 0;
    while (inorder[rootIdx] != rootVal) rootIdx++;
    
    // 分割左右子树序列
    vector<int> leftIn(inorder.begin(), inorder.begin() + rootIdx);
    vector<int> rightIn(inorder.begin() + rootIdx + 1, inorder.end());
    
    vector<int> leftPre(preorder.begin() + 1, preorder.begin() + 1 + leftIn.size());
    vector<int> rightPre(preorder.begin() + 1 + leftIn.size(), preorder.end());
    
    // 递归构建
    root->left = buildTree(leftPre, leftIn);
    root->right = buildTree(rightPre, rightIn);
    
    return root;
}

四、常用操作函数

1. 计算树深度

int getDepth(TreeNode* root) {
    if (!root) return 0;
    return max(getDepth(root->left), getDepth(root->right)) + 1;
}

2. 统计节点总数

int getNodeCount(TreeNode* root) {
    if (!root) return 0;
    return getNodeCount(root->left) + getNodeCount(root->right) + 1;
}

3. 判断两棵树是否相同

bool isSameTree(TreeNode* p, TreeNode* q) {
    if (!p && !q) return true;    // 都为空
    if (!p || !q) return false;   // 一个为空
    // 值相等且左右子树相同
    return (p->val == q->val) && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

二叉树理论学习笔记教程

一、二叉树的基本概念

• 定义：二叉树是一种树形数据结构，每个节点最多有两个子节点，分别称为左子节点和右子节点
• 特点：
  • 每个节点的度（子节点数量）≤2
  • 子节点有明确的左右之分，顺序不可随意调换
  • 可以是空树（没有任何节点）

二、二叉树的基本形态

1. 空二叉树：无任何节点
2. 单节点二叉树：只有根节点，无左右子节点
3. 只有左子树：根节点仅含左子节点
4. 只有右子树：根节点仅含右子节点
5. 完全二叉树：根节点同时含左右子节点

三、特殊二叉树类型

1. 满二叉树

   • 定义：所有叶子节点都在同一层，且非叶子节点都有两个子节点
   • 性质：第k层有2^(k-1)个节点，深度为h的满二叉树总节点数为2^h - 1

2. 完全二叉树

   • 定义：除最后一层外，其余层都是满的；最后一层的节点从左到右依次排列，不允许有空缺
   • 特点：适合数组存储，父节点与子节点索引关系明确

3. 二叉搜索树（BST）

   • 特性：左子树所有节点值＜根节点值；右子树所有节点值＞根节点值
   • 优势：支持高效的查找、插入和删除操作，平均时间复杂度为O(logn)

4. 平衡二叉树（AVL树）

   • 定义：左右两个子树的高度差的绝对值不超过1，且左右两个子树都是平衡二叉树
   • 作用：解决二叉搜索树在极端情况下退化为链表的问题

四、二叉树的性质

1. 第i层最多有2^(i-1)个节点（i≥1）
2. 深度为k的二叉树最多有2^k - 1个节点（k≥1）
3. 对于任意一棵二叉树，若叶子节点数为n₀，度为2的节点数为n₂，则n₀ = n₂ + 1
4. 具有n个节点的完全二叉树的深度为⌊log₂n⌋ + 1
5. 对于完全二叉树中第i个节点：
   • 左子节点为2i（若存在）
   • 右子节点为2i+1（若存在）
   • 父节点为⌊i/2⌋（若存在）

五、二叉树的存储结构

1. 顺序存储

   • 实现：使用数组存储节点，按层次顺序存放
   • 适用场景：完全二叉树或满二叉树（空间利用率高）
   • 优缺点：访问父/子节点高效，但对非完全二叉树空间浪费大

2. 链式存储

   • 节点结构：

     struct Node {
         数据域;
         Node* left;  // 左子节点指针
         Node* right; // 右子节点指针
     };
     

   • 适用场景：所有类型的二叉树
   • 优缺点：空间利用率高，插入删除灵活，但访问父节点需要额外指针或遍历

六、二叉树的遍历方式

1. 深度优先遍历（DFS）

   • 前序遍历：根节点 → 左子树 → 右子树
   • 中序遍历：左子树 → 根节点 → 右子树（对BST遍历可得到有序序列）
   • 后序遍历：左子树 → 右子树 → 根节点

2. 广度优先遍历（BFS）

   • 层次遍历：按层次从左到右依次访问各节点
   • 实现方式：通常使用队列辅助完成

3. 遍历示例（以如下二叉树为例）

        1
       / \
      2   3
     / \
    4   5
   

   • 前序遍历：1 → 2 → 4 → 5 → 3
   • 中序遍历：4 → 2 → 5 → 1 → 3
   • 后序遍历：4 → 5 → 2 → 3 → 1
   • 层次遍历：1 → 2 → 3 → 4 → 5

七、二叉树的基本操作

1. 创建二叉树：按特定规则构建二叉树结构
2. 插入节点：在指定位置添加新节点
3. 删除节点：移除指定节点并调整树结构
4. 查找节点：根据值查找对应节点
5. 计算深度：获取二叉树的最大层次数
6. 计算节点数：统计总节点数或叶子节点数
7. 判断是否为空：检查二叉树是否不含任何节点

八、应用场景

• 表达式解析（如语法树）
• 数据库索引（B+树基于二叉搜索树扩展）
• Huffman编码（用于数据压缩）
• 决策树（人工智能领域）
• 路由算法（网络领域）

九、学习要点

1. 掌握不同遍历方式的递归与非递归实现
2. 理解二叉搜索树的查找、插入、删除原理
3. 学会分析二叉树的时间复杂度和空间复杂度
4. 能够根据遍历序列还原二叉树（如前序+中序、后序+中序）
5. 了解平衡二叉树的旋转操作（LL、LR、RR、RL）