我试着做一个二叉搜索树(bst)来从menuitem类中找到对象,在那里可以找到菜名。但是,出了点问题,我不知道怎么了?
我的目标:
menuitem search(string name)–遍历树并返回对menuitem的引用,其中的搜索键(name)与参数匹配。如果未找到,则返回null。
这是我的bst课程:
public class BST {
private BSTNode root;
public BST() {
root = null;
}
public void insert(MenuItem mi) {
if (root == null)
root = new BSTNode(mi, null, null);
else
insert(root, mi);
}
private void insert(BSTNode cur, MenuItem mi) {
if (mi.compareTo(cur.getData()) < 0)
if (cur.getLeft() != null)
insert(cur.getLeft(), mi);
else
cur.setLeft(new BSTNode(mi, null, null));
else if (mi.compareTo(cur.getData()) > 0)
if (cur.getRight() != null)
insert(cur.getRight(), mi);
else
cur.setRight(new BSTNode(mi, null, null));
else
//If item is same then just add quantity in existing node
cur.getData().setQuantity(cur.getData().getQuantity() + mi.getQuantity());
}
public void preorder() {
printPreOrder(root);
}
private void printPreOrder(BSTNode root) {
if(root != null) {
System.out.print(root.getData());
printPreOrder(root.getLeft());
printPreOrder(root.getRight());
}
}
public void postorder() {
printPost(root);
}
private void printPost(BSTNode root) {
if(root != null) {
printPost(root.getLeft());
printPost(root.getRight());
System.out.println(root.getData());
}
}
public void inorder() {
printInorder(root);
}
private void printInorder(BSTNode root) {
if(root != null) {
printInorder(root.getLeft());
System.out.println(root.getData());
printInorder(root.getRight());
}
}
public int size(){
return size(root);
}
private int size(BSTNode cur){
if (cur==null)
return 0;
return 1 + size(cur.getLeft()) + size(cur.getRight());
}
public int depth(BSTNode root) {
if (root == null)
return 0;
else {
int leftDepth = depth(root.getLeft());
int rightDepth = depth(root.getRight());
if (leftDepth > rightDepth)
return (leftDepth + 1);
else
return (rightDepth + 1);
}
}
public MenuItem search(String name) {
if(root == null)
return null;
else
return search(name,root);
}
private MenuItem search(String name, BSTNode root) {
if(name == root.getData()) {
return root;
}
if ( name.compareTo(BSTNode.getData()) < 0 ){
if(BSTNode.getLeft() == null){
System.out.println("Item not found.");
return null;
}else{
return search(name, BSTNode.getLeft());
}
}else{
if (BSTNode.getRight() == null ){
System.out.println("Item not found.");
return null;
}else{
return search(name, BSTNode.getRight());
}
}
}
public double getTotalBeforeTax() {
return 0;
}
public double getTax(double taxrate) {
return getTotalBeforeTax()*taxrate;
}
public double getTip(double tipPercent){
return getTotalBeforeTax()*tipPercent;
}
public String toString() {
return null;
}
}
1条答案
按热度按时间icomxhvb1#
在下面的函数中,引用的是类名(bstnode),而不是示例名(root)。