[GESP202406 六级] 二叉树

二叉树是一种基本的数据结构，它由节点组成，每个节点最多有两个子节点，通常称为左孩子和右孩子。这种特殊的组织方式使得二叉树能够方便地进行搜索、插入和删除操作。在二叉树中，每个节点都有一个值，根节点是最上面的一个，而叶子节点是没有孩子的节点。

二叉树有几种常见的形态：
1. **满二叉树**：所有层级都尽可能填满，除了最后一层，最右边的节点可能不满。
2. **完全二叉树**：除最后一层外，其他层都是完全填充的，且最后一层的所有节点都在左边。
3. **平衡二叉树**：例如AVL树和红黑树，保持左右子树的高度差不超过1，保证查找效率。

二叉树的操作包括：
- **创建**：通过递归或迭代的方式添加新节点。
- **遍历**：前序遍历（根-左-右）、中序遍历（左-根-右）、后序遍历（左-右-根）和层次遍历（广度优先）。
- **查找**：从根节点开始比较，找到目标值所在的路径。
- **插入和删除**：需要考虑如何维护平衡，避免退化为链表。