gpt4 book ai didi

java - 创建二叉搜索树

转载 作者:行者123 更新时间:2023-12-01 05:14:12 24 4
gpt4 key购买 nike

好的,所以我目前正在尝试创建一个二叉搜索树,每个节点都包含对某个对象的引用,以及对其左子节点的引用和对其右子节点的引用(总共 3 个变量)。左子级必须始终小于其父级,右子级必须始终大于其父级。我必须创建两个方法:一个方法( contains())来检查元素是否在树中,一个 add() 方法将元素添加到树中的适当位置。

这是 BinarySearchTree 类:

public class BinarySearchTree extends BinaryTree {

public BinarySearchTree(TreeNode t){
super(t);
}

public boolean contains (Comparable obj){
if (this.myRoot != null){
return containshelper(obj, this.myRoot);
}
return false;

}

public static boolean containshelper(Comparable comp, TreeNode t){
boolean flag = true;
int x = comp.compareTo(t.myItem);
if (x < 0 && t.myLeft != null){
containshelper(comp,t.myLeft);
}
if (x > 0 && t.myRight != null){
containshelper(comp,t.myRight);
}
if (x == 0){
return true;
}
return false;
}


public void add(Comparable key) {
if (!this.contains(key)){
if (this.myRoot != null){
add(myRoot, key);
}
System.out.print("Getting Here ");
}
else {
System.out.print("Tree already contains item");
}
}

private static TreeNode add(TreeNode t, Comparable key) {

if (((Comparable) t.myItem).compareTo(key) < 0 && t.myLeft != null){
add(t.myLeft,key);

}
if(((Comparable) t.myItem).compareTo(key) > 0 && t.myRight != null ) {
add(t.myRight,key);

}
if (((Comparable) t.myItem).compareTo(key) < 0 && t.myLeft == null){
TreeNode q = new TreeNode(key);
t.myLeft = q;

}
if (((Comparable) t.myItem).compareTo(key) > 0 && t.myRight == null ){
TreeNode w = new TreeNode(key);
t.myRight = w;

}
return t;
}
}

这是 TreeNode 类(包含在 BinaryTree 中):

    public static class TreeNode {

public Object myItem;
public TreeNode myLeft;
public TreeNode myRight;
public int size;

public TreeNode (Object obj) {
size = size(this);
myItem = obj;
myLeft = myRight = null;
}
public int size(TreeNode t) {
return(sizehelper(t));
}
private int sizehelper(TreeNode node) {
if (node == null){
return(0);
}
else {
return(size(node.myLeft) + 1 + size(node.myRight));
}
}


public TreeNode (Object obj, TreeNode left, TreeNode right) {
myItem = obj;
myLeft = left;
myRight = right;
}
}
}

我很确定我的 contains() 方法有效,但我一生都无法弄清楚为什么 add() 不起作用。任何帮助将不胜感激。

最佳答案

您在 containsHelper 中存在一些错误

public static boolean containshelper(Comparable comp, TreeNode t){

// TreeNode.myItem should be declared of type `Comparable` instead of `Object`
int x = comp.compareTo(t.myItem);
if (x < 0 && t.myLeft != null){
return containshelper(comp,t.myLeft); // where does result of this call go? We must return the result !!
}
if (x > 0 && t.myRight != null){
return containshelper(comp,t.myRight); // this too ?
}
if (x == 0){
return true;
}
return false;
}

这里也有同样的错误:

private static TreeNode add(TreeNode t, Comparable key) {

if (t.myItem.compareTo(key) < 0 && t.myLeft != null){
t = add(t.myLeft,key); // where does returned result go?
}
else if (t.myItem.compareTo(key) > 0 && t.myRight != null ) {
t = add(t.myRight,key);
}
else if (t.myItem.compareTo(key) < 0 && t.myLeft == null){
TreeNode q = new TreeNode(key);
t.myLeft = q;
}
else if (t.myItem.compareTo(key) > 0 && t.myRight == null ){
TreeNode w = new TreeNode(key);
t.myRight = w;
}
return t;
}

您应该声明 Comparable 类型的 TreeNode.myItem,以强制每个想要适合您的二分搜索的类提供 compareTo 方法。这比将对象转换为 Comparable 更好,因为该对象可能未实现 Comparable,然后会导致运行时错误

关于java - 创建二叉搜索树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11553944/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com