一.树
1.树的定义
在计算机科学中，树是一种用于表示层次结构的抽象数据类型和非线性数据结构。树由一组节点（Nodes）和节点之间的关系（通常通过边表示）组成。
2.特性
树是一种递归的数据结构：树可以定义为包含子树的树。
树是连通无环图：树是无环图（Acyclic Graph），且在树中任意两个节点之间只有唯一一条路径。
3.树的组成
1. 节点（Node）：树的基本单位，包含数据或值。
2. 根节点（Root Node）：树的顶端节点，是树的唯一入口点。根节点没有父节点。
3. 子节点（Child Node）：直接连接到某个节点下方的节点称为该节点的子节点。
4. 父节点（Parent Node）：直接连接到某个节点上方的节点称为该节点的父节点。
5. 叶子节点（Leaf Node）：没有子节点的节点。
6. 内部节点（Internal Node）：至少有一个子节点的节点。
7. 边（Edge）：连接两个节点的线，表示节点之间的关系。
4.树的重要概念
1. 度(Degree): 节点的度为该节点含有子树的个数(或者称为直接子节点的数量)。
树的度为该棵树中， 所有节点度的最大值。
2. 层数(Levels): 从根节点开始计数，根节点所在的层数可设为 0 或者 1， 然后每层递增。
树的层数为该树的最大层数。
3. 深度(Depth): 如果根节点的深度定义为 0， 则节点的深度是从根节点到该节点所经过的边数。如果根节点的深度定义为 1， 则节点的深度是根节点到这个节点的最长路径上的节点数(包含该节点)。节点的深度即为节点的层数。
4. 高度(Height): 如果该节点最远叶子节点高度定义为 0， 则节点的高度是从该节点到叶子节点的最长路径的边数。如果该节点最远叶子节点高度定义为 1， 则节点的高度是该节点到最远叶子节点的最长路径上的节点数(包含该节点)。树的高度是根节点的高度。
注: 深度和高度主要看初始值的定义是 0 还是 1， 有些教材定义为 0， 有些定义为 1。深度通常是从上往下计算，而高度则是从下往上计算。
5.二叉树
二叉树是一种树形数据结构，其中每个节点最多有两个子节点，分别为左子节点和右子节点。
注: 本文主要以普通二叉树为主
二.几种特殊的二叉树
1.满二叉树(完美二叉树)
国内教程定义：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。
国际定义：其中每个节点要么有两个子节点，要么没有子节点。
国际定义的完美二叉树即为国内定义的满二叉树。
1.1 满二叉树的性质
1. 平衡性：满二叉树是完全平衡的，因为所有叶节点都在同一层。
2. 层次结构：每层的节点数是前一层节点数的两倍。
3. 子树：每个节点的左右子树都是满二叉树。
1.2 满二叉树的特性
设满二叉树的层数为 i（从根节点算起，层数从 1 开始）
1. 节点数: 满二叉树的节点总数为 2^i-1
2. 叶节点数: 满二叉树的所有叶节点都在同一层，且数量为 2^(i-1)
3. 每层节点数: 第 i 层的节点数为 2^(i−1)
4. 非叶节点数: 满二叉树中非叶节点的数量为 2^(i-1)-1
5. 度为2的节点数: 满二叉树中每个非叶节点都有两个子节点，因此数量为 2^(i-1)-1
6. 树的高度: 如果满二叉树的节点总数为 n，则树的高度为 log2(n+1)
2.完全二叉树
完全二叉树是一种二叉树，其中每一层除了最后一层外，其余层的所有节点都是满的，并且最后一层的所有节点尽可能地靠左排列。
2.1 完全二叉树的性质
1. 满二叉树的子集：所有满二叉树都是完全二叉树，但不是所有完全二叉树都是满二叉树。
2. 存储效率：完全二叉树适合使用数组进行存储，因为其节点编号有规律，可以直接计算节点的子节点和父节点的索引。
3. 子树特性：完全二叉树的每个节点的子树也是完全二叉树。
2.2 完全二叉树的特性
设完全二叉树的层数为 i（从根节点算起，层数从 1 开始）
1. 节点的排列：从根节点开始，节点依次从左到右、从上到下排列。除了最后一层，其余层的所有节点都必须有两个子节点。
2. 节点数与层数的关系：层数为 i 的完全二叉树，其节点总数 n 满足：2^(i-1) <= n <= 2^i-1
3. 节点索引：在完全二叉树中，节点可以按层次顺序编号，根节点编号为1，任意节点编号为 i， 则:
a.左子节点编号为 2i
b.右子节点编号为 2i+1
c.父节点编号为 ⌊i/2⌋
4. 层数与节点数的关系: 对于完全二叉树，若节点总数为 n，则树的层数 i 为 ⌊log2n⌋+1。
注: ⌊n⌋表示不大于n的最大整数，即向下取整。
3.二叉搜索树
二叉搜索树（BST，Binary Search Tree），也称二叉排序树或二叉查找树。
3.1 二叉搜索树的性质
1. 非空左子树的所有键值小于其根结点的键值
2. 非空右子树的所有键值大于其根结点的键值
3. 左右子树均为二叉搜索树；
4. 树中没有键值相等的结点。
3.2 二叉搜索树的特性
1. 排序特性：二叉搜索树中的节点按中序遍历（In-order Traversal）得到的序列是有序的（从小到大）。
2. 时间复杂度：查找、插入和删除操作的平均时间复杂度为 O(logn)，其中 n 是节点数。
在最坏情况下（例如，当树退化为链表时），时间复杂度为 O(n)。
3. 动态性：可以动态地进行插入和删除操作，保持树的性质。
为了克服普通二叉搜索树可能退化为链表的问题，引入了平衡二叉搜索树，如AVL树和红黑树。这些树通过额外的平衡条件和旋转操作来保持树的高度接近 O(logn)，从而提高操作效率。
4.平衡二叉树
平衡二叉树是一种二叉树，它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
平衡二叉树通过保持子树高度的平衡，确保了基本操作（如插入、删除、查找）的时间复杂度为 O(logn)。
平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。
三.二叉树的遍历
二叉树的遍历是指按照一定的顺序访问二叉树中所有节点的过程。常见的遍历方法有四种：前序遍历、中序遍历、后序遍历和层序遍历。
其中，前序遍历、中序遍历、后序遍历为深度优先遍历，层序遍历为广度优先遍历。
我们建立一个如下二叉树:
/**
* 树的节点类
* @author HY
* @date 2024/6/26
*/
class TreeNode {
/**
* 节点值
*/
int value;
/**
* 左节点
*/
TreeNode left;
/**
* 右节点
*/
TreeNode right;
/**
* 构造函数，用于创建内部节点
* @param value
*/
TreeNode(int value) {
this.value = value;
}
@Override
public String toString() {
return String.valueOf(value);
}
}构建树结构:
public static void main(String[] args) {
// 建立根节点
TreeNode root = new TreeNode(1);
TreeNode node2 = new TreeNode(2);
TreeNode node3 = new TreeNode(3);
root.left = node2;
root.right = node3;
TreeNode node4 = new TreeNode(4);
TreeNode node5 = new TreeNode(5);
node2.left = node4;
node2.right = node5;
TreeNode node6 = new TreeNode(6);
TreeNode node7 = new TreeNode(7);
node3.left = node6;
node3.right = node7;
}1.深度优先遍历
深度优先遍历从根节点开始，尽可能深地访问树或图的子节点，直到不能再深入为止，然后回溯到上一层节点，继续遍历未访问的节点。
深度优先可以使用递归或栈来实现。
注: 下图中，实线箭头指向的节点为遍历到的节点
1.1 前序遍历
以"根左右"的顺序访问每一个节点：根节点 -> 左子树的节点 -> 右子树的节点。
所以如上规则，依次遍历的节点为 1、2、4、5、3、6、7
a.递归方式
/**
* 前序遍历(递归)
* @param node
*/
public static void preorderTraversal(TreeNode node) {
if (node != null) {
System.out.print(node); // 访问根节点
// 递归访问左子树
preorderTraversal(node.left);
// 递归访问右子树
preorderTraversal(node.right);
}
}b.非递归方式
/**
* 前序遍历(非递归)
* @param root
*/
public static void preorderTraversal(TreeNode root) {
if (root == null) {
return;
}
// 建立一个栈(先进后出)
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
// 访问栈顶节点
System.out.print(node);
if (node.right != null) {
// 先将右子节点压入栈
stack.push(node.right);
}
if (node.left != null) {
// 再将左子节点压入栈
stack.push(node.left);
}
}
}1.2 中序遍历
以"左根右"的顺序访问每一个节点：左子树的节点 -> 根节点 -> 右子树的节点。
所以如上规则，依次遍历的节点为 4、2、5、1、6、3、7
a.递归方式
/**
* 中序遍历(递归)
* @param node
*/
public static void inorderRecursionTraversal(TreeNode node) {
if (node != null) {
// 递归访问左子树
inorderRecursionTraversal(node.left);
// 访问根节点
System.out.print(node.value + " ");
// 递归访问右子树
inorderRecursionTraversal(node.right);
}
}b.非递归方式
/**
* 中序遍历(非递归)
* @param node
*/
public static void inorderNonRecursionTraversal(TreeNode node) {
Stack<TreeNode> stack = new Stack<>();
TreeNode current = node;
while (current != null || !stack.isEmpty()) {
// 如果当前节点不为 null, 则一直把左子树装进栈中
// 从 while 循环退出后, 这一支的左子树已经全部放入栈里了
while (current != null) {
// 将当前节点压入栈
stack.push(current);
// 移动到左子树
current = current.left;
}
// 从栈中弹出栈顶的节点
current = stack.pop();
// 打印该节点
System.out.print(current.value + " ");
// 移动到右子树
current = current.right;
}
}1.3 后序遍历
以"左右根"的顺序访问每一个节点：左子树的节点 -> 右子树的节点 -> 根节点。
所以如上规则，依次遍历的节点为 4、5、2、6、7、3、1
a.递归方式
* 后序遍历(递归)
* @param node
*/
public static void postorderRecursionTraversal(TreeNode node) {
if (node != null) {
// 递归访问左子树
postorderRecursionTraversal(node.left);
// 递归访问右子树
postorderRecursionTraversal(node.right);
// 访问根节点
System.out.print(node.value + " ");
}
}b.非递归方式
/**
* 后序遍历(非递归)
* @param node
*/
public static void postorderRecursionTraversal(TreeNode node) {
// 初始化一个栈用于存储节点
Stack<TreeNode> stack = new Stack<>();
// 记录上一个访问过的节点
TreeNode lastVisited = null;
// 当前节点从传入的节点开始
TreeNode current = node;
// 当前节点不为空或栈不为空时循环
while (current != null || !stack.isEmpty()) {
// 不断深入左子树
while (current != null) {
// 将当前节点压入栈
stack.push(current);
// 进入左子树
current = current.left;
}
// 获取栈顶节点但不弹出
current = stack.peek();
// 如果右子树为空或右子树已经被访问过
if (current.right == null || current.right == lastVisited) {
// 访问根节点
System.out.print(current.value + " ");
// 将栈顶节点弹出
stack.pop();
// 更新上一个访问过的节点
lastVisited = current;
// 重置当前节点为空
current = null;
} else {
// 进入右子树
current = current.right;
}
}
}2. 广度优先遍历
广度优先（BFS）遍历按层次逐层遍历树或图，从根节点开始，依次访问每一层的所有节点，然后再进入下一层。
2.1 层序遍历
/**
* 层序遍历(非递归)
* @param root
*/
public static void levelOrderTraversal(TreeNode root) {
if (root == null) {
return;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
// 访问当前节点
System.out.print(node.value + " ");
if (node.left != null) {
// 将左子节点加入队列
queue.add(node.left);
}
if (node.right != null) {
// 将右子节点加入队列
queue.add(node.right);
}
}
}四.普通二叉树的增删改
1. 插入
普通二叉树（不是二叉搜索树）的层序插入方法:
特点:
1. 层序遍历：使用队列进行层序遍历，逐层查找空位插入新节点。
确保尽量平衡地插入节点，使得树的高度尽可能小。
2. 找到第一个空闲位置：在遍历过程中，当找到第一个空闲位置（即某节点的左子节点或右子节点为空）时，立即插入新节点。
3. 保证树的完全性：这种插入方法尽量使树保持完全二叉树的特性，即除最后一层外，每层都是满的，并且最后一层的节点尽可能向左对齐。
优点:
1. 简单易懂：该方法的逻辑简单，容易实现。使用队列进行层序遍历，代码清晰直观。
2. 平衡性好：由于尽量保持树的完全性，插入后的树高度较小，接近平衡。
3. 适用于普通二叉树：适用于没有特定性质要求的普通二叉树，而不是二叉搜索树或其他自平衡树。
缺点:
1. 效率问题：在大规模数据插入时，每次插入都需要进行层序遍历，可能会导致较高的时间复杂度，尤其是在树的节点数较多时。
2. 不适用于二叉搜索树（BST）：这种插入方法没有考虑节点值的大小关系，因此不适用于需要保持排序性质的二叉搜索树。在BST中，插入节点需要根据值的大小来选择合适的子树插入，以保持树的有序性。
3. 可能的空间浪费：使用队列进行层序遍历，需要额外的空间存储节点，空间复杂度为 O(n)，其中 n 是树的节点数。
这种插入方式适用于普通二叉树的场景，特别是在需要保持树的完全性时。但在需要特定性质的树（如二叉搜索树、自平衡树）中，这种插入方法并不适用。
/**
* 二叉树的插入
* @param root
* @param value
*/
public static void insert(TreeNode root, int value) {
// 检查根节点是否为空，如果为空，直接创建新节点作为根节点
if (root == null) {
root = new TreeNode(value);
return;
}
// 创建一个队列来进行层序遍历
Queue<TreeNode> queue = new LinkedList<>();
// 将根节点加入队列
queue.add(root);
// 当队列不为空时，继续遍历
while (!queue.isEmpty()) {
// 从队列中取出一个节点
TreeNode node = queue.poll();
// 检查左子节点是否为空，如果为空，插入新节点
if (node.left == null) {
node.left = new TreeNode(value);
return;
} else {
// 如果左子节点不为空，将左子节点加入队列
queue.add(node.left);
}
// 检查右子节点是否为空，如果为空，插入新节点
if (node.right == null) {
node.right = new TreeNode(value);
return;
} else {
// 如果右子节点不为空，将右子节点加入队列
queue.add(node.right);
}
}
}此外还有递归插入、 深度优先插入、随机插入等，并不常见，这里不再演示。
2. 删除
1. 找到要删除的节点：我们使用层序遍历（或其他方法）找到了要删除的节点 target 和树的最后一个节点 last。
2. 替换节点值：我们将要删除节点 target 的值替换为最后一个节点 last 的值。这样做的目的是为了维持树的结构完整性，同时实际上我们要删除的节点变成了最后一个节点的值。
3. 删除最后一个节点：为了真正从树中删除节点，我们需要删除最后一个节点 last。
/**
* 删除节点
* @param root
* @param value
* @return
*/
public static TreeNode delete(TreeNode root, int value) {
// 如果树为空，直接返回null
if (root == null) {
return null;
}
// 如果树只有一个节点，检查该节点是否为要删除的节点
if (root.left == null && root.right == null) {
if (root.value == value) {
// 如果是要删除的节点，返回null
return null;
} else {
// 如果不是要删除的节点，返回原树
return root;
}
}
// 使用队列进行层序遍历
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
// 用于记录要删除的节点
TreeNode target = null;
// 用于记录最后一个节点（最右下的节点）
TreeNode last = null;
// 用于记录最后一个节点的父节点
TreeNode lastParent = null;
// 使用层序遍历找到要删除的节点和最后一个节点
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
// 如果当前节点是要删除的节点，记录下来
if (node.value == value) {
target = node;
}
// 记录最后一个节点和其父节点
if (node.left != null) {
queue.add(node.left);
lastParent = node;
last = node.left;
}
if (node.right != null) {
queue.add(node.right);
lastParent = node;
last = node.right;
}
}
// 如果找到了要删除的节点
if (target != null) {
// 用最后一个节点的值替换要删除的节点的值
target.value = last.value;
// 删除最后一个节点(确保从树中删除一个节点, 所以不能简单的将 last 设置为null)
if (lastParent.right == last) {
lastParent.right = null;
} else {
lastParent.left = null;
}
}
// 返回更新后的树的根节点
return root;
}这里的删除操作是将其父节点 lastParent 的相应子节点引用（left 或 right）设置为 null。这样做确保了树结构的完整性，同时也确保了删除操作的正确性。
注: 因为是简单的普通二叉树，所以可能存在相同键值的节点，这时候会只删除最后一个遍历到的该键值的点。该删除意义不大，因为树形结构在父子关系中，往往需要存在某种联系，比如父子关系、大小等。
3.修改键值
在普通二叉树中，修改节点通常指的是更新节点的值或者结构，而不像删除那样涉及到节点的重新连接。修改节点可以根据需要更新节点的值，但通常不涉及更改节点的位置或者树的结构。
3.1 删除首次遍历到的节点
对于没有重复键值的节点来说，此种方式效率更高
/**
* 修改节点值的方法
* @param root
* @param oldValue
* @param newValue
*/
public static void modify(TreeNode root, int oldValue, int newValue) {
// 查找要修改的节点
TreeNode node = findNode(root, oldValue);
// 如果找到要修改的节点
if (node != null) {
// 更新节点的值为新值
node.value = newValue;
}
}
/**
* 查找节点的方法(深度优先搜索, 近似于前序遍历, 先比较根结点再比较左子树和右子树)
* @param node
* @param value
* @return
*/
private static TreeNode findNode(TreeNode node, int value) {
// 如果节点为空，直接返回null
if (node == null) {
return null;
}
System.out.println(node.value);
// 如果节点的值等于要查找的值，返回该节点
if (node.value == value) {
return node;
}
// 否则递归地在左子树中查找
TreeNode leftResult = findNode(node.left, value);
// 如果在左子树中找到了节点，返回该节点(上一层返回的 node 节点)
if (leftResult != null) {
return leftResult;
}
// 否则递归地在右子树中查找
return findNode(node.right, value);
}注: 因为是简单的普通二叉树，所以可能存在相同键值的节点，这时候会只修改遍历到的第一个该键值的点。
3.2 修改所有该值的节点
/**
* 修改所有具有相同键值的节点为新值
* @param root
* @param oldValue
* @param newValue
*/
public static void modifyAll(TreeNode root, int oldValue, int newValue) {
// 递归地进行修改操作
recursiveModify(root, oldValue, newValue);
}
/**
* 递归查找并修改节点值
* @param node
* @param oldValue
* @param newValue
*/
private static void recursiveModify(TreeNode node, int oldValue, int newValue) {
// 如果节点为空，返回
if (node == null) {
return;
}
// 如果当前节点的值等于旧值，修改为新值
if (node.value == oldValue) {
node.value = newValue;
}
// 递归地向左子树查找并修改
recursiveModify(node.left, oldValue, newValue);
// 递归地向右子树查找并修改
recursiveModify(node.right, oldValue, newValue);
}五.二叉树的翻转
二叉树的翻转（或镜像）是一种将二叉树的左子树和右子树交换的位置进行递归操作的方法。
/**
* 翻转二叉树的方法
* @param root
*/
public static void invert(TreeNode root) {
// 如果节点为空，直接返回
if (root == null) {
return;
}
// 递归翻转左子树和右子树
invert(root.left);
invert(root.right);
// 交换当前节点的左子节点和右子节点
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
}六.二叉树的旋转
二叉树的旋转主要包括左旋和右旋两种方式，这两种操作是镜像且互为逆操作。
1.左旋
左旋转：左旋通常以根的右子节点为支点，将根的右子树提升到更高层级，而该右子节点变为新的根节点，老根节点变为新根节点的左子树，新根节点的左子树则成为老根节点的右子树。这种操作不会改变中序遍历的结果，因为左子树的位置没有变化，只是右子树的结构发生了调整。
/**
* 左旋操作
* @param root
* @return
*/
public static TreeNode leftRotate(TreeNode root) {
// 获取右子节点作为新根节点
TreeNode newRoot = root.right;
// 将新根节点的左子树移为老根节点的右子树
root.right = newRoot.left;
// 将老根节点变为新根节点的左子树
newRoot.left = root;
// 返回新的根节点
return newRoot;
}2.右旋
右旋转：与左旋转相反，右旋转以左子节点为支点，将根的左子树提升到更高层级，而该左子结点变为新的根节点，老根节点变为新根节点的右子树，新根节点的右子树变为老根节点的左子树。同样地，这种操作也不会改变中序遍历的结果。
/**
* 右旋操作
* @param root
* @return
*/
public static TreeNode rightRotate(TreeNode root) {
// 获取左子节点作为新根节点
TreeNode x = root.left;
// 将新根节点的右子树移为老根节点的左子树
root.left = x.right;
// 将老根节点变为新根节点的右子树
x.right = root;
// 返回新的根节点
return x;
}在实际应用中，二叉树的旋转常用于调整树的局部平衡性，特别是在平衡二叉树（如AVL树）中，当插入新节点导致树失去平衡时，通过旋转操作可以快速恢复树的平衡状态。这些操作对于维护二叉搜索树的性质至关重要，因为它们确保了树的中序遍历结果仍然有序。
扫一扫
293
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
