二叉排序树 插入 数据结构与算法（二）:线性表、栈、树(二叉树，AVL树)、图(3)

} else if (e.compareTo(current.element) > 0) {

parent = current;

current = current.right;

} else {

return false;

}

}

// 插入

if (e.compareTo(parent.element) < 0) {

parent.left = createNewNode(e);

} else {

parent.right = createNewNode(e);

}

}

return true;

}

// 创建新的节点

protected TreeNode<E> createNewNode(E e) {

return new TreeNode(e);

}

}

// 二叉树的节点

class TreeNode<E extends Comparable<E>> {

E element;

TreeNode<E> left;

TreeNode<E> right;

public TreeNode(E e) {

element = e;

}

}

上面的代码15主要展示了一个自己实现的简单的二叉查找树，其中包括了几个常见的操作，当然更多的操作还是需要大家自己去完成。因为在二叉查找树中删除节点的操作比较复杂，所以下面我详细介绍一下这里。

二叉查找树中删除节点分析

要在二叉查找树中删除一个元素，首先需要定位包含该元素的节点，以及它的父节点。假设current指向二叉查找树中包含该元素的节点，而parent指向current节点的父节点，current节点可能是parent节点的左孩子，也可能是右孩子。这里需要考虑两种情况：

current节点没有左孩子，那么只需要将patent节点和current节点的右孩子相连。

current节点有一个左孩子，假设rightMost指向包含current节点的左子树中最大元素的节点，而parentOfRightMost指向rightMost节点的父节点。那么先使用rightMost节点中的元素替换current节点中的元素，将parentOfRightMost节点和rightMost节点的左孩子相连，然后删除rightMost节点。

// 二叉搜索树删除节点

public boolean delete(E e) {

TreeNode<E> parent = null;

TreeNode<E> current = root;

// 找到要删除的节点的位置

while (current != null) {

if (e.compareTo(current.element) < 0) {

parent = current;

current = current.left;

} else if (e.compareTo(current.element) > 0) {

parent = current;

current = current.right;

} else {

break;

}

}

// 没找到要删除的节点

if (current == null) {

return false;

}

// 考虑第一种情况

if (current.left == null) {

if (parent == null) {

root = current.right;

} else {

if (e.compareTo(parent.element) < 0) {

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-60790-3.html