java - 泛型二叉搜索树的 remove 方法导致堆栈溢出问题
问题描述
我遇到了这个关于为通用类型二叉搜索树实现删除方法的实验室问题。
我已经实现了一个通用类型的二叉搜索树。
我学习了二叉搜索树删除算法,我尝试处理父节点有“0个孩子”、“1个孩子”或“2个孩子”的3种情况。
我实现了删除节点的代码,但一直导致堆栈溢出问题,并且我找不到我的代码哪里出了问题。
任何帮助将不胜感激。
public class BinarySearchTree<T extends Comparable<T>> {
private Node<T> _root; //Root node
public class Node<T extends Comparable<T>> {
public T get_value() {return _value;}
public void set_value(T _value) {this._value = _value;}
public Node<T> get_left() {return _left;}
public void set_left(Node<T> _left) {this._left = _left;}
public Node<T> get_right() {return _right;}
public void set_right(Node<T> _right) {this._right = _right;}
public Node<T> get_parent() {return _parent;}
public void set_parent(Node<T> _parent) {this._parent = _parent;}
T _value; // Node value
Node<T> _left; // Left child
Node<T> _right; // Right child
Node<T> _parent; // Parent node
public Node(T key, Node<T> parent, Node<T> left, Node<T> right) {
_value = key;
_left = left;
_right = right;
_parent = parent;
}
}
// Remove a node from the BST
private Node<T> remove(BinarySearchTree<T> bst, Node<T> z) {
Node<T> delNode = null;
if(bst._root == null){
delNode = null;
}
else{
Node<T> current = bst._root;
// find the position to delete
while(current!=null){
int compare = z.get_value().compareTo(current.get_value());
if(compare < 0){
current = current.get_left();
}
if(compare > 0){
current = current.get_right();
}
else{
// if node has two child,replace it with right minimum value
if (current._left!=null && current._right!=null){
delNode = current;
Node<T> successor = minimumKey(current.get_right());
current.set_value(successor.get_value());
remove(successor._value);
}
if (current._left!=null){
delNode = current;
remove(current._value);
current._left.set_parent(current._parent);
}
if (current._right!=null){
delNode = current;
remove(current._value);
current._right.set_parent(current._parent);
}
else{
delNode = current;
remove(current._value);
}
}
}
}
return delNode;
}
// remove a node value
public void remove(T key) {
Node<T> z, node;
if ((z = find(_root, key)) != null)
if ( (node = remove(this, z)) != null)
node = null;
}
public Node<T> minimumKey(Node<T> current) {
while (current._left != null) {
current = current._left;
}
return current;
}
}
解决方案
你的条件有问题。他们应该是:
if(compare < 0) {
current = current.get_left();
} else if(compare > 0) {
current = current.get_right();
} else {
...
就像现在一样, if compare < 0
is true
,您同时执行current = current.get_left();
和else
子句。
不过,我不确定这是您remove
方法的唯一问题。
推荐阅读
- php - Laravel 8 - 未找到基表或视图:1146 表“laravel8.brand”不存在
- go - 如何在 go 中的 map 中获取 for 循环中的所有数据?
- c# - 从 dotnet (Python.NET) 取消 python 函数
- javascript - 使用网格模板自动调整最后一行以占据整列
- flutter - 如何在 SafeArea 中包装 showModalBottomSheet?- 颤振
- c - C 由于预增导致的错误输出
- reactjs - 网络错误 axios 试图从 API 获取数据
- mysql - 如何使这个基本的 MySQL SELECT 查询在 10 亿行上更快?
- ios - 在 swiftUI 中集成重复代码,比如继承之类的
- javascript - Wouter 防止未找到页面显示