gpt4 book ai didi

java - 二叉搜索树实例化

转载 作者:塔克拉玛干 更新时间:2023-11-02 08:37:13 32 4
gpt4 key购买 nike

我已经使用树接口(interface)和递归创建了二叉搜索树(我知道使用节点类我可以实现相同的功能)提供了添加和检查元素是否在二叉搜索树中的方法。

我面临的问题是实例化和显示 BST 的元素。

这是我的代码

树界面:

package bst;

public interface Tree<D extends Comparable>{

public boolean isempty();
public int cardinality();
public boolean member(D elt);
public NonEmptyBst<D> add(D elt);

}

EmptyBst 类:

 package bst;

public class EmptyBst<D extends Comparable> implements Tree<D>{
public EmptyBst(){
D data=null;
}

@Override
public boolean isempty() {
// TODO Auto-generated method stub
return true;
}

@Override
public int cardinality() {
// TODO Auto-generated method stub
return 0;
}

@Override
public boolean member(D elt) {
// TODO Auto-generated method stub
return false;
}

@Override
public NonEmptyBst<D>add(D elt) {
// TODO Auto-generated method stub
return new NonEmptyBst<D>(elt);
}

}

NonEmptyBst 类

 package bst;

public class NonEmptyBst<D extends Comparable> implements Tree<D> {
D data;
D root;
Tree<D> left;
Tree <D>right;

public NonEmptyBst(D elt){
data=elt;
root=elt;
left=new EmptyBst<D>();
right=new EmptyBst<D>();

}
NonEmptyBst(){
D dataThis=this.data;
}
public NonEmptyBst(D elt,Tree<D>leftTree,Tree<D>rightTree){
data=elt;
left=leftTree;
right=rightTree;
}
@Override
public boolean isempty() {
// TODO Auto-generated method stub
return false;
}
@Override
public int cardinality() {
// TODO Auto-generated method stub
return 1+left.cardinality()+right.cardinality();
}



public boolean member(D elt) {
if (data == elt) {
return true;
} else {
if (elt.compareTo(data) < 0) {
return left.member(elt);
} else {
return right.member(elt);
}
}
}

public NonEmptyBst<D> add(D elt) {
if (data == elt) {
return this;
} else {
if (elt.compareTo(data) < 0) {
return new NonEmptyBst(data, left.add(elt), right);
} else {
return new NonEmptyBst(data, left, right.add(elt));
}
}
}
}

BinarySearchTree 类

package bst;
import bst.Tree;
import bst.EmptyBst;
import bst.NonEmptyBst;

public class BinarySearchTree {
public static void main(String[] args) {
// TODO Auto-generated method stub
NonEmptyBst abcd=new NonEmptyBst( "abc");
NonEmptyBst ab=new NonEmptyBst(67);

abcd.add("cry me a river");
abcd.add("geeehfvmfvf");
abcd.add("I'm Sexy and i know it");
abcd.add("zzzzsd");
abcd.add("zzzzsd");
abcd.add("zzzfdsf");
abcd.add("zzfedfrsd");
abcd.add("tgrgdzsd");
abcd.add("gtrgrtgtrgtrzzzzsd");
abcd.add("zzzzsd");
abcd.add("zdddzzzsd");
abcd.add("zzzzsd");
abcd.add("zzzzsd");

}
}

**我如何访问所有节点的数据然后将它们打印出来?我面临的特殊问题是在获取异常时即 ClassCastException当我访问“叶节点”时,即使我初始化了 new NonEmptyBst<D>在我的NonEmptyBst<D>(D elt) constructor我最终有一个空指针异常

  Exception in thread "main" java.lang.NullPointerException 
at java.lang.String.compareTo(Unknown Source)
at java.lang.String.compareTo(Unknown Source)
at bst.NonEmptyBst.add(NonEmptyBst.java:51)
at bst.NonEmptyBst.add(NonEmptyBst.java:54)
at bst.BinarySearchTree.main(BinarySearchTree.java:11)

最佳答案

我不太确定是否需要 EmptyBst 除非您尝试遵循空对象的设计模式。

具体来说,如果 data == null && left == null && right == null,则可以轻松检查“空”树。此外,这里不需要 data,因为它是一个局部变量,从未被引用过。

public EmptyBst(){
D data=null;
}

D dataD root 有区别吗?

我认为您需要调整您的 add 方法来捕获递归的结果。

public NonEmptyBst<D> add(D elt) {
if (data == elt) {
return this;
} else {
if (elt.compareTo(data) < 0) {
this.left = this.left.add(elt);
} else {
this.right = this.right.add(elt);
}
}

return this;
}

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

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