二叉树（binary tree）
二叉树（Binary Tree）是一种常见的树状数据结构，它由一组节点组成，每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树具有以下特点：
- 每个节点最多有两个子节点，分别称为左子节点和右子节点。
- 左子树和右子树也是二叉树，它们的结构与父节点类似。
- 二叉树的顺序不固定，可以是任意形状。
两种特殊形式
二叉树还有两种特殊形式，一个叫作满二叉树 ，另一个叫作完全二叉树
满二叉树
如果该二叉树的所有叶子节点都在最后一层，并且结点总数= 2^n -1,n 为层数，则我们称为满二又树。简单点说，满二叉树的每一个分支都是满的。
完全二叉树
对一个有n个节点的二叉树，按层级顺序编号，则所有节点的编号为从1到n。如果这个树所有节点和同样深度的满二叉树的编号为从1到n的节点位置相同，则这个二叉树为完全二叉树。完全二叉树的条件没有满二叉树那么苛刻: 满二叉树要求所有分支都是满的;而完全二叉树只需保证最后一个节点之前的节点都齐全即可。
遍历二叉树
在计算机程序中，遍历本身是一个线性操作。所以遍历同样具有线性结构的数组或链表，是一件轻而易举的事情。反观二叉树，是典型的非线性数据结构，遍历时需要把非线性关联的点转化成一个线性的序列，以不同的方式来遍历，遍历出的序列顺序也不同。
遍历方式
深度优先和广度优先这两个概念不止局限于二叉树，它们更是一种抽象的算法思想，决定了访问某些复杂数据结构的顺序。在访问树、图，或其他一些复杂数据结构时，这两个概念常常被使用到。
1.深度优先遍历（Depth-First Search，DFS）
所谓深度优先，顾名思义，就是偏向于纵深，“一头扎到底”的访问方式。可能这种说法有些抽象，下面就通过二叉树的前序遍历、中序遍历、后序遍历 ，来看一看深度优先
2.广度优先遍历 (Breadth-First Search，BFS)
如果说深度优先遍历是在一个方向上“一头扎到底”，那么广度优先遍历则恰恰相反:先在各个方向上各走出1步，再在各个方向上走出第2步、第3步......一直到各个方向全部走完。听起来有些抽象，下面让我们通过二叉树的层序遍历
也是一种遍历或搜索树或图的算法。在广度优先遍历中，从根节点开始，按照层级顺序逐层访问节点，先访问当前层的所有节点，然后再访问下一层的节点。广度优先遍历可以使用队列来实现。
前序遍历
根节点 -> 左子树 -> 右子树。在前序遍历中，首先访问根节点，然后按照左子树和右子树的顺序递归地进行前序遍历。
// 前序遍历二叉树（根-左-右）
public static void preOrderTraversal(TreeNode node) {
if (node == null) {
return;
}
System.out.print(node.val + " ");
preOrderTraversal(node.left);
preOrderTraversal(node.right);
}
中序遍历
左子树 -> 根节点 -> 右子树。在中序遍历中，首先按照左子树的顺序递归地进行中序遍历，然后访问根节点，最后按照右子树的顺序递归地进行中序遍历。
// 中序遍历二叉树（左-根-右）
public static void inOrderTraversal(TreeNode node) {
if (node == null) {
return;
}
inOrderTraversal(node.left);
System.out.print(node.val + " ");
inOrderTraversal(node.right);
}
后序遍历
左子树 -> 右子树 -> 根节点。在后序遍历中，首先按照左子树和右子树的顺序递归地进行后序遍历，然后访问根节点。
// 后序遍历二叉树（左-右-根）
public static void postOrderTraversal(TreeNode node) {
if (node == null) {
return;
}
postOrderTraversal(node.left);
postOrderTraversal(node.right);
System.out.print(node.val + " ");
}
public static void main(String[] args) {
// 创建一个二叉树
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
// 前序遍历二叉树
System.out.println("前序遍历结果：");
preOrderTraversal(root);
// 中序遍历二叉树
System.out.println("\n中序遍历结果：");
inOrderTraversal(root);
// 后序遍历二叉树
System.out.println("\n后序遍历结果：");
postOrderTraversal(root);
}
层次遍历
是一种广度优先遍历的应用，它按照层级顺序逐层访问二叉树的节点。在层次遍历中，从根节点开始，先访问根节点，然后按照从左到右的顺序逐层访问每个节点的子节点，一层一层横向遍历各个节点，可以借助于队列实现。
public static void levelOrderTraversal(TreeNode root) {
if (root == null) {
return;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root); // 将根节点入队
while (!queue.isEmpty()) {
int levelSize = queue.size(); // 当前层级的节点数量
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll(); // 出队当前节点
System.out.print(node.val + " "); // 访问当前节点
if (node.left != null) {
queue.offer(node.left); // 左子节点入队
}
if (node.right != null) {
queue.offer(node.right); // 右子节点入队
}
}
System.out.println(); // 换行表示进入下一层级
}
}
存储结构
顺序结构存储
使用数组来表示二叉树的结构。按照层级顺序依次将二叉树节点存储到数组中，空缺位置用特定值（如null）表示。这种存储结构适用于完全二叉树，因为不是完全二叉树会有空间的浪费，可以通过数组下标计算节点之间的关系。
特点：
-
顺序二叉树通常只考虑完全二叉树
-
第n个元素的左子节点为
2* n +1 -
第n个元素的右子节点为
2* n + 2 -
第n个元素的