为什么我的二进制搜索树显示多于3个节点？

我的二进制搜索树不能管理多于3个节点或能够显示它们。我需要迭代地添加它们，并在作业中使用堆栈显示它们，但如果它具有多于3个元素，则无法显示BST。为什么我的二进制搜索树显示多于3个节点？

public boolean add(E b) { 

    //if tree is empty 
    if (root == null) { 
     root = new Node(); 
     root.setValue(b); 
     count++; 
     return true; 
    } //if val is already in tree 
    else if (b.compareTo(root.getValue()) == 0) { 
     return false; 
     //if left or right spot is free 
    } else { 
     while (root != null) { 
      compareResult = root.value.compareTo(b); 
      spot = root; 
      if (compareResult < 0) { 
       if (root.left != null) { 
        spot = spot.left; 
        count++; 
        return true; 
       } else { 
        Node n = new Node<>(); 
        n.setValue(b); 
        spot.left = n; 
        count++; 
        return true; 
       } 
      } else if (compareResult > 0) { 
       if (root.right != null) { 
        spot = spot.right; 
        count++; 
        return true; 
       } else { 
        Node n = new Node<>(); 
        n.setValue(b); 
        spot.right = n; 
        count++; 
        return true; 

       } 
      } else { 
       return false; 
      } 
     } 
    } 
    return false; 

} 

public void display() { 
    //needs to use an iterator 
    if (root == null) { 
     System.out.println("Error"); 
    } else { 
     Node CurrentNode; 
     CurrentNode = root; 
     while (!stack.isEmpty() || CurrentNode != null) { 
      if (CurrentNode != null) { 
       stack.push(CurrentNode); 
       CurrentNode = CurrentNode.right; 


      } 
      else { 
       Node m= stack.pop(); 
       System.out.println(m.value); 
       CurrentNode = m.left; 
      } 

     } 
    } 
} 

public int size() { 
    return count; 
} 

@Override 
public int compareTo(E t) { 
    return ordering.compare(root,t); 
} 

@Override 
public int compare(E t, E t1) { 
    return t.compareTo(t1); 
}

Node类看起来像这样

public class Node<E extends Comparable> { 

E value; 
Node<E> left; 
Node<E> right; 

//constructor 
public Node() { 
    value = null; 
    left = null; 
    right = null; 


} 

public void setValue(E t) { 
    value = t; 
} 

public void setLeft(Node<E> t) { 
    left = t; 

} 

public void setRight(Node<E> t) { 
    right = t; 
} 

public Node<E> getLeft() { 
    return left; 
} 

public Node<E> getRight() { 
     return right; 
} 

public E getValue() { 
    return value; 
}

来源

2016-09-18 HollyNeedsHelp

这不是一个完整的答案，因为我不会为你做你的功课。但基本上，你的'add'方法需要递归。事实上，它只会在节点的根节点，左侧子节点或右侧子节点添加事物。你的大部分逻辑都可以被删除，因为如果你插入的值不是__根值，你可以再次调用'add'来通过左边的节点。如果它的_greater大于_根值，那么可以再次调用'add'来通过右边的节点。您错过了这个递归步骤。 –

我将如何递归调用它？ BST中的大多数对象都是Node对象，因此我无法再次调用add。我只能在E上调用Add，然后我不知道如何结束程序。 – HollyNeedsHelp

你有几个选项。你可以把'add'方法放在'Node'类中。然后，'Tree'类中的'add'方法将检查是否存在'Node'，如果存在，则调用'Node'上的'add'。或者，你可以这样做，使得'Node'类内的'left'和'right'实际上是树，而不仅仅是节点。 –

我可以看到一对夫妇，你需要作出改变的。

在add方法} else {线后，你应该换接下来的三线周围，有

spot = root; 
    while (spot != null) { 
     compareResult = spot.value.compareTo(b);

因为spot是怎么回事，而你迭代循环跟踪其一路下跌的树。但是因为您目前使用root而不是spot，所以您始终将值与root节点进行比较，而不是降低节点。

此外，从spot = spot.left;和spot = spot.right;后取出count++;和return true;，因为在这些情况下，你还没有真正添加什么树，所以你需要通过循环继续进行。

来源

2016-09-18 02:26:32

为什么我的二进制搜索树显示多于3个节点？

回答

相关问题