二叉树操作全解析：从构建到删除-编程实验室

一、二叉树基础与节点定义

二叉树是计算机科学中最基本、最重要的数据结构之一，它是一种每个节点最多有两个子节点的树形结构。这两个子节点通常被称为左子节点和右子节点。二叉树在算法设计、数据库索引、文件系统等众多领域都有广泛应用。

二叉树节点的Java实现

在Java中，我们首先需要定义二叉树节点的基本结构。下面是节点类的实现：

// TreeNode.java - 二叉树节点定义 package com.qcby; public class TreeNode { public TreeNode lChild; // 左子节点引用 public TreeNode rChild; // 右子节点引用 public Integer data; // 节点存储的数据 // 构造函数，初始化节点数据 public TreeNode(Integer data){ this.data = data; } }

这个简洁的TreeNode类定义了三个核心属性：

data：存储节点的整数值
lChild：指向左子节点的引用
rChild：指向右子节点的引用

二、二叉搜索树的构建

二叉搜索树（Binary Search Tree, BST）是一种特殊的二叉树，它满足以下性质：

左子树中所有节点的值小于根节点的值
右子树中所有节点的值大于根节点的值
左右子树也都是二叉搜索树

下面是二叉搜索树的构建方法实现：

// BinaryTree.java - 二叉搜索树的创建方法 public void create(Integer value){ // 1.创建新节点 TreeNode newNode = new TreeNode(value); if(root==null){ root = newNode; return; } TreeNode curNode = root; while(true){ if(curNode.data < newNode.data){ if(curNode.rChild == null){ curNode.rChild = newNode; return; } curNode = curNode.rChild; }else{ if(curNode.lChild == null){ curNode.lChild = newNode; return; } curNode = curNode.lChild; } } }

插入算法解析：

创建新节点：根据传入的值创建新的TreeNode对象
检查空树：如果根节点为null，直接将新节点设为根节点
查找插入位置：
- 从根节点开始遍历
- 如果新节点值大于当前节点值，向右子树移动
- 如果新节点值小于等于当前节点值，向左子树移动
插入新节点：找到合适的位置（空位置）后，将新节点插入

时间复杂度分析：

平均情况：O(log n)，其中n是节点数
最坏情况：O(n)，当树退化成链表时

三、二叉树的遍历方法

遍历是访问二叉树中所有节点的过程，确保每个节点仅被访问一次。以下是四种基本遍历方法的实现：

1. 前序遍历（Pre-order Traversal）

访问顺序：根节点 → 左子树 → 右子树

// BinaryTree.java - 前序遍历实现 void beforeOrder(TreeNode root){ if(root == null){ return; } System.out.println(root.data); beforeOrder(root.lChild); beforeOrder(root.rChild); }

算法特点：

先访问根节点，再递归遍历左子树，最后递归遍历右子树
适用于需要先处理父节点再处理子节点的场景

应用场景：

复制二叉树结构
计算前缀表达式
序列化二叉树

2. 中序遍历（In-order Traversal）

访问顺序：左子树 → 根节点 → 右子树

// BinaryTree.java - 中序遍历实现 void inOrder(TreeNode root){ if(root == null){ return; } inOrder(root.lChild); System.out.println(root.data); inOrder(root.rChild); }

重要特性：对二叉搜索树进行中序遍历，会得到一个有序序列。

应用场景：

输出有序数据
验证二叉搜索树
表达式树的求值

3. 后序遍历（Post-order Traversal）

访问顺序：左子树 → 右子树 → 根节点

// BinaryTree.java - 后序遍历实现 void afterOrder(TreeNode root){ if(root == null){ return; } afterOrder(root.lChild); afterOrder(root.rChild); System.out.println(root.data); }

应用场景：

删除二叉树
计算后缀表达式
计算目录大小（文件系统）

4. 层序遍历（Level-order Traversal）

按层次从上到下，从左到右访问节点

// BinaryTree.java - 层序遍历实现 void levelOrder(TreeNode root){ // 1.创建队列 LinkedList<TreeNode> queue = new LinkedList<TreeNode>(); queue.add(root); while(!queue.isEmpty()){ root = queue.pop(); System.out.println(root.data); if(root.lChild != null){ queue.add(root.lChild); } if(root.rChild != null){ queue.add(root.rChild); } } }

算法解析：

使用队列作为辅助数据结构
将根节点入队
循环执行以下操作直到队列为空：
- 出队一个节点并访问
- 将其左子节点入队（如果存在）
- 将其右子节点入队（如果存在）

应用场景：

计算二叉树深度
查找最短路径
按层次打印二叉树

四、节点查找辅助方法

在实现删除操作前，我们需要一些辅助方法来查找目标节点及其父节点：

// BinaryTree.java - 查找目标节点 // 找到要删除的节点 TreeNode findTarget(TreeNode root,Integer target){ if(root == null){ return null; } //去找这个值 if(root.data == target){ return root; }else if(target < root.data){ //判断是否有左子树 if(root.lChild == null){ return null; } return findTarget(root.lChild,target); }else { //判断是否有右子树 if (root.rChild == null) { return null; } return findTarget(root.rChild, target); } } //去找要删除节点的父节点 TreeNode findParent(TreeNode root,Integer target){ if(root == null){ return null; } if((root.lChild!=null) && (root.lChild.data == target) || (root.rChild!=null) && (root.rChild.data == target)){ return root; }else { if(root.lChild!=null && target < root.data){ return findParent(root.lChild,target); }else if(root.rChild!=null && target > root.data){ return findParent(root.rChild,target); }else { return null; } } }

五、有序二叉树删除节点的三种情况

删除二叉搜索树中的节点是BST操作中最复杂的部分，需要根据被删除节点的子节点数量分为三种情况处理：

情况1：删除叶子节点（没有子节点）

操作：直接删除该节点，将其父节点的对应指针设为null

实现代码：

// 在delete方法中处理叶子节点的情况 if(targetNode.lChild == null && targetNode.rChild == null){ //叶子节点 //确定targetNode是parentNode的左子树还是右子树 if(parentNode.lChild != null && parentNode.lChild.data == target){ parentNode.lChild = null; }else if(parentNode.rChild != null && parentNode.rChild.data == target){ parentNode.rChild = null; } }

示例：在下图中删除节点1（叶子节点）

text

7 / \ 3 10 / \ / \ 1 5 9 11 / 0

情况2：删除只有一个子节点的节点

操作：用其子节点替换自身，保持BST性质

实现代码：

// 在delete方法中处理只有一个子节点的情况 else { //targetNode 只有一个子节点的节点 //确定targetNode是parentNode的左子树还是右子树 if(parentNode.lChild!=null && parentNode.lChild.data == target){ //确定targetNode是parentNode的左子树 if(targetNode.lChild != null){ //targetNode有左子结点 parentNode.lChild = targetNode.lChild; }else { //targetNode有右子结点 parentNode.lChild = targetNode.rChild; } }else if(parentNode.rChild!=null && parentNode.rChild.data == target){ //确定targetNode是parentNode的右子树 if(targetNode.lChild != null){ //targetNode有左子结点 parentNode.rChild = targetNode.lChild; }else { //targetNode有右子结点 parentNode.rChild = targetNode.rChild; } } }

示例：在下图中删除节点1（只有一个左子节点0）

text

7 / \ 3 10 / \ / \ 1 5 9 11 / 0

情况3：删除有两个子节点的节点

操作：

找到右子树中的最小节点（或左子树中的最大节点）
用这个最小（或最大）节点的值替换被删除节点的值
删除那个最小（或最大）节点（递归处理）

实现代码：

// 查找右子树最小节点的辅助方法 /** * 去找右子树的最小值 * @param node * @return */ public int findRightTreeMin(TreeNode node){ while (node.lChild !=null){ node = node.lChild; } int min = node.data; delete(root, min); return min; } // 在delete方法中处理有两个子节点的情况 else if(targetNode.lChild != null && targetNode.rChild != null){ //有两个子节点的节点 int min = findRightTreeMin(targetNode.rChild); targetNode.data = min; }

示例：在下图中删除节点3（有两个子节点1和5）

text

7 / \ 3 10 / \ / \ 1 5 9 11 / 0

六、完整的删除方法实现

下面是完整的删除方法实现，整合了所有三种情况的处理：

public void delete(TreeNode root,Integer target){ if(root == null){ return; } //2.万一要删的节点只有一个节点 if(root.lChild == null && root.rChild == null){ root = null; return; } //1.去找被删除的节点 TreeNode targetNode = findTarget(root,target); if(targetNode == null){ //找不到 return; } //3.找到父节点 TreeNode parentNode = findParent(root,target); //分情况进行删除 if(targetNode.lChild == null && targetNode.rChild == null){ //叶子节点 //确定targetNode是parentNode的左子树还是右子树 if(parentNode.lChild != null && parentNode.lChild.data == target){ parentNode.lChild = null; }else if(parentNode.rChild != null && parentNode.rChild.data == target){ parentNode.rChild = null; } }else if(targetNode.lChild != null && targetNode.rChild != null){ //有两个子节点的节点 int min = findRightTreeMin(targetNode.rChild); targetNode.data = min; }else { //targetNode 只有一个子节点的节点 //确定targetNode是parentNode的左子树还是右子树 if(parentNode.lChild!=null && parentNode.lChild.data == target){ //确定targetNode是parentNode的左子树 if(targetNode.lChild != null){ //targetNode有左子结点 parentNode.lChild = targetNode.lChild; }else { //targetNode有右子结点 parentNode.lChild = targetNode.rChild; } }else if(parentNode.rChild!=null && parentNode.rChild.data == target){ //确定targetNode是parentNode的右子树 if(targetNode.lChild != null){ //targetNode有左子结点 parentNode.rChild = targetNode.lChild; }else { //targetNode有右子结点 parentNode.rChild = targetNode.rChild; } } } }

七、测试示例

// Test.java - 测试类 package com.qcby; public class Test { public static void main(String[] args) { BinaryTree bt = new BinaryTree(); bt.create(7); bt.create(3); bt.create(10); bt.create(1); bt.create(5); bt.create(9); bt.create(11); bt.create(0); System.out.println("删除节点1前的层序遍历:"); bt.levelOrder(bt.root); bt.delete(bt.root, 1); System.out.println("\n删除节点1后的层序遍历:"); bt.levelOrder(bt.root); } }

测试结果分析：
原始树结构：

text