二叉树的节点删除要分成三类：删除没有子节点的节点、删除只有一个子节点的节点、删除有两个子节点的节点。第一种和第二种很简单，第三种比较复杂。首先，先从第一种开始
在开始之前先要找到要删除的子节点，这就用到了查找
TreeNode current = root;
TreeNode parent = root;
boolean isLeftNode = true;
while (current.keyValue != Key) {
parent = current;
if (Key < current.keyValue) {
isLeftNode = true;
current = current.leftNode;
} else {
isLeftNode = false;
current = current.rightNode;
}
}
if (current == null) {
System.out.println("没有找到要删除的节点！");
return false;
}
删除没有子节点的节点： 删除没有子节点的节点只需要将被删除节点的父节点指向空即可。
看图：
图中显示要删除61这个节点，再看代码：
if (current.leftNode == null && current.rightNode == null) { //要删除的节点没有子节点
if (current == root) { // 根节点就删除整棵树
root = null;
} else if (isLeftNode) { // 如果是左节点，做节点指向空
parent.leftNode = null;
} else { // 如果是右节点，右节点指向空
parent.rightNode = null;
}
}
删除有一个子节点的节点：删除有一个子节点的节点，只需要将被删除节点的父节点指向删除节点的子节点即可
看图：
要删除84这个节点。代码：
if (current.leftNode == null) { //要删除的节点只有右节点
if (current == root) {
root = current.rightNode;
} else if (isLeftNode) {
parent.leftNode = current.rightNode;
} else {
parent.rightNode = current.rightNode;
}
} else if (current.rightNode == null) { //要删除的节点只有左节点
if (current == root) {
root = current.leftNode;
} else if (isLeftNode) {
parent.leftNode = current.leftNode;
} else {
parent.rightNode = current.leftNode;
}
}
删除有两个子节点的节点：删除有两个子节点的节点，到底谁来替代被删除的节点的位置呢？是左节点，还是右节点，代替以后这个子节点的子节点应该怎么安排？一系列的问题都出来了。。。简便的方法就是要找一个节点代替这个被删除的节点，这就要从二叉搜索树的定义来看。因为二叉搜索树是有序的，我们要找的节点在这棵树上，而且这个节点要比被删除的左节点大，比右节点小。先看看这个以被删除节点的右节点为根的子树的所有节点的值都要比被删除节点大，这是二叉搜索树定义的，但是要在这个集合中找到最小的一个，来代替被删除的节点，那就要在这棵子树上一直往左找。这个节点比被删除的节点的右节点小，且比左节点大，那这个节点就叫做被删除节点的后继节点，用这个节点来代替被删除节点。
来看一下代码：
private TreeNode findSuccessor(TreeNode delNode){
TreeNode parent = delNode;
TreeNode successor = delNode;
TreeNode current = delNode.rightNode;
while(current != null){
parent = successor;
successor = current;
current = current.leftNode;
}
//这段代码的作用是当后继节点不是被删除节点的右节点并且后继结点有右节点的情况下的时候做的操作
if(successor != delNode.rightNode){
parent.leftNode = successor.rightNode;
successor.rightNode = delNode.rightNode;
}
return successor;
}
找到了后继节点剩下的事情就简单了只需要将被删除节点替换为后继节点就可以了，这里的过程要注意各种指针的指向。
代码：
TreeNode successor = findSuccessor(current);
if(current == root){
root = successor;
}else if(isLeftNode){
parent.leftNode = successor;
}else{
parent.rightNode = successor;
}
successor.leftNode = current.leftNode;
--------------------------------------------------------------------------------------------------------------------------------------
下面给出整个树的代码：
package test;
/**
* @author 作者 MarcoSpring:
* @version 创建时间：2012-8-3 上午10:14:51 二叉搜索树
*/
public class Tree {
public TreeNode root;// 根节点
// 查找节点
public TreeNode search(int Key) {
TreeNode node = root;
// 首先定义一个节点让其指向根，在下面的循环中
// 只要节点值不等于要查找的节点值就进入循环如果没有找到则返回null
while (node.keyValue != Key) {
if (Key < node.keyValue) { // 如果要查找的值小于节点值则指向左节点
node = node.leftNode;
} else { // 否则指向右节点
node = node.rightNode;
}
if (node == null) { // 如果节点为空了则返回null
return null;
}
}
return node;
}
// 添加节点
public void insert(int Key) {
TreeNode node = new TreeNode(Key);
// 添加节点之前首先要找到要添加的位置，这样就要记住要添加节点的父节点
// 让父节点的左右指向要添加的节点
if (root == null) { // 如果根结点为空，则根节点指向新节点
root = node;
} else {
TreeNode currentNode = root;// 定义当前节点并指向根节点
TreeNode parentNode;
while (true) { // 寻找节点添加的位置
parentNode = currentNode;
if (Key < currentNode.keyValue) {
currentNode = currentNode.leftNode;
if (currentNode == null) { // 当找到空节点的时候，父节点的左节点指向新节点
parentNode.leftNode = node;
return;
}
} else {
currentNode = currentNode.rightNode;
if (currentNode == null) { // 当找到空节点的时候，父节点的右节点指向新节点
parentNode.rightNode = node;
return;
}
}
}
}
}
// 遍历树
public void display(TreeNode node) {
if (node != null) {
display(node.leftNode);
System.out.println(node.keyValue + ",");
display(node.rightNode);
}
}
// 最大值
public int max() {
TreeNode node = root;
TreeNode parent = null;
while (node != null) {
parent = node;
node = node.rightNode;
}
return parent.keyValue;
}
// 最小值
public int min() {
TreeNode node = root;
TreeNode parent = null;
while (node != null) {
parent = node;
node = node.leftNode;
}
return parent.keyValue;
}
// 删除节点分三种方式删除节点
// 1、删除没有子节点的节点，直接让该节点的父节点的左节点或右节点指向空
// 2、删除有一个子节点的节点，直接让该节点的父节点指向被删除节点的剩余节点
// 3、删除有三个节点的子节点，找到要删除节点的后继节点， 用该节点替代删除的节点
public boolean delete(int Key) {
// 首先查找节点，并记录该节点的父节点引用
TreeNode current = root;
TreeNode parent = root;
boolean isLeftNode = true;
while (current.keyValue != Key) {
parent = current;
if (Key < current.keyValue) {
isLeftNode = true;
current = current.leftNode;
} else {
isLeftNode = false;
current = current.rightNode;
}
}
if (current == null) {
System.out.println("没有找到要删除的节点！");
return false;
}
// 下面分三种情况删除节点
if (current.leftNode == null && current.rightNode == null) { //要删除的节点没有子节点
if (current == root) { // 根节点就删除整棵树
root = null;
} else if (isLeftNode) { // 如果是左节点，做节点指向空
parent.leftNode = null;
} else { // 如果是右节点，右节点指向空
parent.rightNode = null;
}
} else if (current.leftNode == null) { //要删除的节点只有右节点
if (current == root) {
root = current.rightNode;
} else if (isLeftNode) {
parent.leftNode = current.rightNode;
} else {
parent.rightNode = current.rightNode;
}
} else if (current.rightNode == null) { //要删除的节点只有左节点
if (current == root) {
root = current.leftNode;
} else if (isLeftNode) {
parent.leftNode = current.leftNode;
} else {
parent.rightNode = current.leftNode;
}
} else { //要删除的节点有两个节点
TreeNode successor = findSuccessor(current);
if(current == root){
root = successor;
}else if(isLeftNode){
parent.leftNode = successor;
}else{
parent.rightNode = successor;
}
successor.leftNode = current.leftNode;
}
return true;
}
private TreeNode findSuccessor(TreeNode delNode){
TreeNode parent = delNode;
TreeNode successor = delNode;
TreeNode current = delNode.rightNode;
while(current != null){
parent = successor;
successor = current;
current = current.leftNode;
}
if(successor != delNode.rightNode){
parent.leftNode = successor.rightNode;
successor.rightNode = delNode.rightNode;
}
return successor;
}
}
- 大小: 90.4 KB
- 大小: 80.8 KB
分享到：
相关推荐
二叉搜索树（BST）是一种常见的二叉树结构，它具有有序性质，使得在插入、删除和搜索操作上非常高效。本教程将向您展示如何使用Java编写代码来执行二叉搜索树的插入操作。我们将提供一个简单而清晰的示例，以帮助您...
JAVA构建二叉搜索树，前序遍历，中序遍历，后序遍历，插入删除节点...
下面小编就为大家分享一篇Java创建二叉搜索树,实现搜索,插入,删除的操作实例，具有很好的参考价值，希望对大家有所帮助
java实现二叉查找树的插入、删除、遍历、查询
二叉查找树的实现。包括树的平衡以及树节点的删除。以及树的广度优先遍历，深度优先遍历。
二叉搜索树的效率： 树的大部分操作需要从上至下一层层的查找树的节点，对于一棵满树，大约有一半的节点处于最底层（最底层节点数 = 其它层节点数的和 + 1），故节点操作大约有一半需要找到最底层节点，大约有四分...
主要介绍了Java删除二叉搜索树的任意元素的方法,结合实例形式详细分析了java这对二叉搜索树的遍历、查找、删除等相关操作技巧与使用注意事项,需要的朋友可以参考下
主要介绍了Java删除二叉搜索树最大元素和最小元素的方法,结合实例形式详细分析了java针对二叉搜索树的基本遍历、查找、判断、删除等相关操作技巧,需要的朋友可以参考下
本文主要介绍了Java实现二叉搜索树的查找、插入、删除、遍历等内容。具有很好的参考价值，下面跟着小编一起来看下吧
java使用jtree动态实现二叉树，包含二叉树的插入删除很查找
个平衡二叉搜索树的左倾红黑 (LLRB) 实现。 这是 Robert Sedgewick 在 [他的论文](() 和由 Robert Sedgewick 和 Kevin Wayne 撰写的书中介绍的 Java 代码的直接移植。经他们许可，被许可为 LGPL v3，并移植到Python...
实践周程序设计项目之一，比较简单，仅仅涉及到了二叉搜索树、二叉平衡树、平衡树的插入、删除、搜索等操作，最后用一个图形化界面进行展示。有需求者可自取。 阅读建议：有一定Java语言基础，了解package和类的...
Java实现的经典算法 介绍 该存储库包含 Java 中几种经典算法的演示实现。 目录 排序 哈希表 树和图 二叉搜索树（常规） 特里 ...描述：冒泡排序、选择排序、插入排序、快速排序、归并... 描述：常规二叉搜索树的演示实
在AVL树中插入或删除元素的过程与在常规二叉搜索树中相同。不同之处在于，您可能必须在插入或删除操作之后重新平衡树。节点的平衡因子是其右子树的高度减去左子树的高度。如果一个节点的平衡因子为- 1,0或1，则称该...
B树 B树是一种自平衡树数据... B树是二叉搜索树的概括，一个节点可以有两个以上的子节点。 与自平衡二进制搜索树不同，B树非常适合于读写相对较大的数据块（例如磁盘）的存储系统。 它通常在数据库和文件系统中使用。
24.后序遍历二叉搜索树。25.二叉树中和为某值的路径.26.复杂链表的复制27.二叉搜索树转换为双向链表.28.打印字符串中所有字符的排列29.数组中出现次数超过一半的数字.30.找出最小的K个数31.连续子数组的最大和.32.从...
描述： 实现红黑树、二叉搜索树相关算法：插入（红黑树涉及树的调整：左旋、右旋等），删除，搜索（指定Key值节点）。 另外，红黑树实现计算树黑高的算法。 1).插入测试，输入 8，11，17，15，6，1，22，25，27...
在二叉搜索树中搜索， 插入二叉搜索树， 最近二叉搜索树值， 最近二叉搜索树值 II , 二叉树中序遍历 二叉树先序遍历 二叉树后序遍历 二叉树级顺序遍历， 二叉树中所有节点距离 K , 第一个坏版本， 恢复二叉搜索树， ...
将排序数组转换为二叉搜索树 将排序列表转换为二叉搜索树 平衡二叉树 二叉树的最小深度 路径和 路径求和 II 将二叉树展平到链表 在每个节点中填充下一个右指针 II 二叉树最大路径和 根到叶数求和 按算法 动态规划