二叉树的核心技术与C++实现：存储、遍历与递归应用

一、二叉树基础概念与常见类型

1.1 二叉树核心概念

1.2 四种常见二叉树类型

类型1：满二叉树

类型2：完全二叉树

类型3：二叉搜索树（BST）

类型4：平衡二叉树（AVL）

类型5：退化二叉树

二、二叉树的存储方法

2.1 链式存储法（主流方法）

2.2 顺序存储法（数组实现）

2.3 极简存储法（隐式结构）

三、二叉树遍历与递归应用

3.1 三种基础遍历方式（递归实现）

前序遍历：根节点 -> 左子树 -> 右子树

中序遍历：左子树 -> 根节点 -> 右子树

后序遍历：左子树 -> 右子树 -> 根节点

3.2 递归应用实战

示例1：计算树的高度

示例2：查找节点是否存在

四、关键知识点总结

扩展学习路线：

二叉树是一种层次化的、高度组织性的数据结构。二叉树的形态使得它有天然的优势，在二叉树上做查询、插入、删除、修改、区间等操作极为高效，基于二叉树的算法也很容易实现高效率的计算。

一、二叉树基础概念与常见类型

1.1 二叉树核心概念

定义：每个节点最多有两个子节点的树结构
特性：

每个节点有0/1/2个子节点
左子树和右子树有严格顺序
空树是有效二叉树（递归算法基例）

重要术语：

根节点（Root）：最顶层的唯一节点
叶子节点（Leaf）：没有子节点的节点
深度（Depth）：根到当前节点的路径长度
高度（Height）：节点到最远叶子的路径长度

1.2 四种常见二叉树类型

类型1：满二叉树

定义：所有非叶子节点都有两个子节点，所有叶子在同一层
应用场景：完美平衡结构，用于最优搜索场景

// 满二叉树节点定义（每个节点必须有两个子节点或为叶子）
struct FullTreeNode {int val;FullTreeNode* left;  // 必须存在或为nullptrFullTreeNode* right; // 必须存在或为nullptrFullTreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

类型2：完全二叉树

定义：除最后一层外全满，最后一层节点左对齐
特性：适合数组存储，堆结构的基础

// 完全二叉树的数组实现（层次存储）
class CompleteBinaryTree {
private:vector<int> tree;  // 使用数组存储节点值
public:// 插入操作：按层序填充（自动计算父子关系）void insert(int val) {tree.push_back(val);}// 获取父节点索引公式：(i-1)/2 （i从0开始）int getParent(int childIndex) {return (childIndex - 1) / 2;}
};

类型3：二叉搜索树（BST）

定义：左子树所有节点值 < 根值 < 右子树所有节点值
优势：查找/插入/删除时间复杂度O(log n)

// BST基本操作实现
class BST {
private:struct Node {int val;Node *left, *right;Node(int v) : val(v), left(nullptr), right(nullptr) {}};Node* root = nullptr;public:// 插入操作（递归实现）Node* insert(Node* node, int val) {if (!node) return new Node(val);if (val < node->val) node->left = insert(node->left, val);elsenode->right = insert(node->right, val);return node;}
};

类型4：平衡二叉树（AVL）

定义：任意节点左右子树高度差绝对值≤1
平衡操作：通过旋转（左旋/右旋）维持平衡

// AVL树核心代码框架
class AVLTree {
private:struct Node {int val;int height; // 节点高度Node *left, *right;Node(int v) : val(v), height(1), left(nullptr), right(nullptr) {}};// 获取节点高度（处理空指针）int getHeight(Node* node) {return node ? node->height : 0;}// 右旋转操作（解决LL型不平衡）Node* rightRotate(Node* y) {Node* x = y->left;Node* T2 = x->right;x->right = y;y->left = T2;// 更新高度y->height = max(getHeight(y->left), getHeight(y->right)) + 1;x->height = max(getHeight(x->left), getHeight(x->right)) + 1;return x;}// 其他旋转操作类似（代码略）
};