二叉树

Binary Tree

二叉树的类型总结

1. 二叉树（Binary Tree）
   • 一个根节点，每个节点最多有两个子节点。
2. 满二叉树（Full Binary Tree）
   • 每个节点要么有 0 个子节点（叶子节点），要么有 2 个子节点。
3. 完全二叉树（Complete Binary Tree）
   • 除了最后一层，所有层的节点都必须被填满，最后一层的节点从左到右排列，不能有空缺。
4. 完美二叉树（Perfect Binary Tree）
   • 一种特殊的满二叉树，所有叶子节点在同一层，所有内部节点都有两个子节点。
5. 平衡二叉树（Balanced Binary Tree）
   • 任意节点的左右子树高度差不超过 1。
6. 二叉搜索树（Binary Search Tree, BST）
   • 一种特殊的二叉树，左子树的所有节点值小于根节点，右子树的所有节点值大于根节点。
7. 平衡二叉搜索树（Balanced BST）
   • 既是二叉搜索树，又满足平衡二叉树的特性，如 AVL 树、红黑树。
8. 退化二叉树 / 病态二叉树（Degenerate Binary Tree / Pathological Tree）
   • 每个节点只有一个子节点，导致树退化成类似链表的结构，查找效率变差。
9. 无限完全二叉树（Infinite Complete Binary Tree）
   • 具有无限层级的完全二叉树，其中第 ddd 层有 2d2^d2d 个节点。

DFS&BFS