目录
二叉树
理论基础
二叉树的分类
1. 满二叉树 (Full Binary Tree)
2. 完全二叉树 (Complete Binary Tree)
3. 平衡二叉树 (Balanced Binary Tree)
5. 二叉搜索树 (Binary Search Tree, BST)
二叉树的存储
1. 链式存储 (Linked Representation)
2. 顺序存储 (Sequential Representation)
遍历方式
深度优先搜索
DFS 的工作原理
基本步骤：
广度优先搜索
BFS 的工作原理
基本步骤：
二叉树的遍历
递归遍历
前序遍历
中序遍历
后序遍历
非递归遍历
前序遍历
中序遍历
后续遍历
层序遍历
二叉树
理论基础
二叉树的分类
1. 满二叉树 (Full Binary Tree)
- 定义：满二叉树是一种二叉树，除了叶子节点外，每个节点都有两个子节点，深度为
h的完美二叉树有2^h - 1个节点 - 特点：所有非叶子节点都有两个子节点，且所有叶子节点都在同一层。
2. 完全二叉树 (Complete Binary Tree)
- 定义：完全二叉树是一种二叉树，所有层都被完全填满，除了可能是最后一层，且最后一层的所有节点尽可能靠左。
- 特点：没有缺失的节点，除非是在最后一层的最右边。
3. 平衡二叉树 (Balanced Binary Tree)
- 定义：平衡二叉树是一种二叉树，其中每个节点的左子树和右子树的高度差不超过1，空树。
- 特点：平衡二叉树保证了二叉树的高度尽可能低，从而优化了查找、插入和删除操作的效率。
5. 二叉搜索树 (Binary Search Tree, BST)
- 定义：二叉搜索树是一种有序二叉树，其中每个节点的值大于其左子树中所有节点的值，小于其右子树中所有节点的值。
- 特点：在理想情况下（即树是平衡的），查找、插入、删除操作的时间复杂度为O(log n)。
二叉树的存储
二叉树的存储方式有多种，常见的主要有以下两种方法：链式存储和顺序存储。每种方法都有其适用场景和优缺点。
1. 链式存储 (Linked Representation)
链式存储是二叉树最常用的存储方式，特别适合用于动态变化的树结构。
特点：
- 每个节点用一个对象或结构体来表示，包含节点的值、左子节点指针、右子节点指针，和（有时）指向父节点的指针。
- 链式存储易于动态地添加或删除节点，不需要预先分配大量的连续内存。
节点结构
在典型的链式存储中，每个节点包含三个主要部分：
- 值/数据域：存储节点的数据。
- 左指针域：指向左子节点。
- 右指针域：指向右子节点。
class TreeNode {int value;TreeNode left;TreeNode right;TreeNode(int value) {this.value = value;this.left = null;this.right = null;}
}
2. 顺序存储 (Sequential Representation)
顺序存储是将二叉树节点按某种规则顺序存储在数组中的方式，通常适用于完全二叉树或满二叉树。
特点
- 二叉树的节点按照层次从上到下、从左到右存储在数组中。
- 数组的第一个位置（通常从索引0或1开始）存储根节点，其他节点按照其在二叉树中的位置依次存储。
节点位置关系
假设父节点在数组中的索引为i，则：
- 左子节点的索引：
2*i + 1（或2*i，如果数组从1开始） - 右子节点的索引：
2*i + 2（或2*i + 1，如果数组从1开始） - 父节点的索引：
(i-1)/2（对于索引从0开始的情况）
遍历方式
与图论中的深度优先搜索和广度优先搜索是一致的。
深度优先搜索
深度优先搜索（Depth-First Search，简称DFS）是一种遍历或搜索树或图数据结构的算法。它优先深入到树或图的一个分支的尽可能深的节点，然后再回溯并探索其他分支。这种策略使得DFS能够深入到数据结构的最深处，然后逐层返回，直到遍历所有节点。
前序遍历：中左右
中序遍历：左中右
后序遍历：左右中
DFS 的工作原理
DFS 使用栈结构来实现遍历的过程。栈可以通过显式使用栈数据结构来实现，也可以通过递归调用来隐式实现。
基本步骤：
- 访问当前节点。
- 标记该节点为已访问，以避免重复访问。
- 递归地访问该节点的未被访问的相邻节点，对于树结构来说，这意味着先访问左子树，然后访问右子树。
- 当节点的所有相邻节点都已被访问或没有未被访问的相邻节点时，回溯到前一个节点，然后继续访问其他未被访问的节点。
- 重复以上步骤，直到所有节点都被访问。
递归实现：
class TreeNode {int value;TreeNode left;TreeNode right;TreeNode(int value) {this.value = value;this.left = null;this.right = null;}
}public class DFS {public void depthFirstSearch(TreeNode node) {if (node == null) {return;}// 访问当前节点System.out.print(node.value + " ");// 递归地访问左子节点depthFirstSearch(node.left);// 递归地访问右子节点depthFirstSearch(node.right);}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);DFS dfs = new DFS();dfs.depthFirstSearch(root); // 输出: 1 2 4 5 3}
}
栈实现：
class TreeNode {int value;TreeNode left;TreeNode right;TreeNode(int value) {this.value = value;this.left = null;this.right = null;}
}public class DFS {public void depthFirstSearch(TreeNode node) {if (node == null) {return;}// 访问当前节点System.out.print(node.value + " ");// 递归地访问左子节点depthFirstSearch(node.left);// 递归地访问右子节点depthFirstSearch(node.right);}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);DFS dfs = new DFS();dfs.depthFirstSearch(root); // 输出: 1 2 4 5 3}
}
广度优先搜索
广度优先搜索（Breadth-First Search，简称 BFS）是一种遍历或搜索树或图数据结构的算法。与深度优先搜索（DFS）不同，BFS 从起始节点开始，首先访问其所有邻居节点，然后再逐层向下深入到下一级的节点。这种逐层访问的方式确保了在无权重图中，从起始节点到任意其他节点的最短路径可以通过 BFS 得到。
BFS 的工作原理
BFS 使用队列（Queue）数据结构来实现逐层遍历的过程。队列遵循先进先出（FIFO）的原则，确保先进入队列的节点先被处理。
基本步骤：
- 将起始节点加入队列，并标记为已访问。
- 从队列中取出一个节点，访问该节点，并将其所有未被访问的相邻节点加入队列。
- 标记这些相邻节点为已访问，以防止重复访问。
- 重复步骤 2 和 3，直到队列为空，表示所有节点都已被访问。
使用队列实现：
import java.util.LinkedList;
import java.util.Queue;class TreeNode {int value;TreeNode left;TreeNode right;TreeNode(int value) {this.value = value;this.left = null;this.right = null;}
}public class BFS {public void breadthFirstSearch(TreeNode root) {if (root == null) {return;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {TreeNode node = queue.poll();System.out.print(node.value + " ");// 将左子节点加入队列if (node.left != null) {queue.offer(node.left);}// 将右子节点加入队列if (node.right != null) {queue.offer(node.right);}}}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);BFS bfs = new BFS();bfs.breadthFirstSearch(root); // 输出: 1 2 3 4 5}
}
二叉树的遍历
递归遍历
1.确定递归函数的参数和返回值
2.确定终止条件
3.确定单层递归的逻辑
前序遍历
public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();preorder(root, result);return result;}public void preorder(TreeNode root, List<Integer> result) {if (root == null) {return;}result.add(root.val);preorder(root.left, result);preorder(root.right, result);}中序遍历
public List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();inorder(root, result);return result;}public void inorder(TreeNode root, List<Integer> result) {if (root == null) {return;}inorder(root.left, result);result.add(root.val);inorder(root.right, result);}后序遍历
public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();postorder(root, result);return result;}public void postorder(TreeNode root, List<Integer> result) {if (root == null) {return;}postorder(root.left, result);postorder(root.right, result);result.add(root.val);}非递归遍历
null在谁前就先访问谁，null后如果还要push就先访问push进去的，再访问null
前序遍历
前序遍历，访问的元素和要处理的元素一致
每次循环操纵栈中第一个节点
public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new LinkedList<>();Stack<TreeNode> st = new Stack<>();//放入第一个元素，放进栈中if (root != null) {st.push(root);}while (!st.empty()) {//储存栈中的第一个节点TreeNode node = st.peek();if (node != null) {//因为在后面还要压入一次中节点st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中if (node.right!=null) st.push(node.right); // 添加右节点（空节点不入栈）if (node.left!=null) st.push(node.left); // 添加左节点（空节点不入栈）st.push(node); // 添加中节点st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。} else { // 只有遇到空节点的时候，才将下一个节点放进结果集st.pop(); // 将空节点弹出node = st.peek(); // 重新取出栈中元素st.pop();result.add(node.val); // 加入到结果集}}return result;}中序遍历
先看节点的左孩子为空则弹出中间，右孩子也为空则继续弹出前一个节点
左孩子不为空，则继续用栈收集
左孩子为空，弹出中间，右孩子不为空，收集右孩子，再看右孩子的左孩子是否为空
public List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new LinkedList<>();Stack<TreeNode> st = new Stack<>();if (root != null) st.push(root);while (!st.empty()) {TreeNode node = st.peek();if (node != null) {st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中if (node.right!=null) st.push(node.right); // 添加右节点（空节点不入栈）st.push(node); // 添加中节点st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。if (node.left!=null) st.push(node.left); // 添加左节点（空节点不入栈）} else { // 只有遇到空节点的时候，才将下一个节点放进结果集st.pop(); // 将空节点弹出node = st.peek(); // 重新取出栈中元素st.pop();result.add(node.val); // 加入到结果集}}return result;}后续遍历
将左右交换，然后再将数组颠倒
public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new LinkedList<>();Stack<TreeNode> st = new Stack<>();if (root != null) st.push(root);while (!st.empty()) {TreeNode node = st.peek();if (node != null) {st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中st.push(node); // 添加中节点st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。if (node.right!=null) st.push(node.right); // 添加右节点（空节点不入栈）if (node.left!=null) st.push(node.left); // 添加左节点（空节点不入栈） } else { // 只有遇到空节点的时候，才将下一个节点放进结果集st.pop(); // 将空节点弹出node = st.peek(); // 重新取出栈中元素st.pop();result.add(node.val); // 加入到结果集}}return result;}层序遍历
每次循环，先得到一个队列的大小为size，然后得到左右孩子，每次弹出一个，直到弹出size个，
下次循环再得到size
// 102.二叉树的层序遍历
class Solution {public List<List<Integer>> resList = new ArrayList<List<Integer>>();public List<List<Integer>> levelOrder(TreeNode root) {//checkFun01(root,0);checkFun02(root);return resList;}//BFS--递归方式public void checkFun01(TreeNode node, Integer deep) {if (node == null) return;deep++;if (resList.size() < deep) {//当层级增加时，list的Item也增加，利用list的索引值进行层级界定List<Integer> item = new ArrayList<Integer>();resList.add(item);}resList.get(deep - 1).add(node.val);checkFun01(node.left, deep);checkFun01(node.right, deep);}//BFS--迭代方式--借助队列public void checkFun02(TreeNode node) {if (node == null) return;Queue<TreeNode> que = new LinkedList<TreeNode>();que.offer(node);while (!que.isEmpty()) {List<Integer> itemList = new ArrayList<Integer>();int len = que.size();while (len > 0) {TreeNode tmpNode = que.poll();itemList.add(tmpNode.val);if (tmpNode.left != null) que.offer(tmpNode.left);if (tmpNode.right != null) que.offer(tmpNode.right);len--;}resList.add(itemList);}}
}
