在添加新节点时使用堆栈存储treap节点。为什么我会得到一个EmptyStackException？
在添加新节点时使用堆栈存储treap节点。为什么我会得到一个EmptyStackException？
提问于 2019-04-28 00:18:20
我正在用Java构建一个treap类。下面是我用来向treap添加新节点的函数。这个过程是:向下遍历到treap的底部(同时将路径中的每个节点添加到一个本地堆栈中)，首先只关心BST结构，然后，一旦到达底部，我就利用我构建的堆栈通过循环重新建立堆不变量。
这听起来应该可以工作，但我一直得到一个EmptyStackException。一旦调用私有的"reheap“函数，就会发生这种异常。
add函数对添加到树中的第一个节点有效，例如: testTree.add (4 ,19)；但在第二次添加节点时失败，如随后调用: testTree.add (2 ,31)；
这是完整的错误：
Exception in thread "main" java.util.EmptyStackException
at java.util.Stack.peek(Unknown Source)
at classes.Treap.reheap(Treap.java:137)
at classes.Treap.add(Treap.java:130)
at classes.Treap.main(Treap.java:220)130 --指的是对add函数137底部的reheap的调用--指的是私有reheap函数220的while循环--指的是我在main中添加新节点的尝试。
我试着改变reheap函数中的条件，但是没有用。
boolean add(E key, int priority) {
Stack<Node<E>> stack = new Stack<Node<E>>();
if(root == null) {
Node<E> newroot = new Node<E>(key, priority);
root = newroot;
stack.push(root);
return true;
}else {
Node<E> current = new Node<E>(root.data, root.priority); //placeholder, used for traversing
Node<E> added = new Node<E>(key, priority); //node to be added to the treap
if(this.find(key) == true){
return false;
}else {
if(current.right == null && current.left == null) {
stack.push(current);
if(key.compareTo(current.data) < 0)
current = current.left;
else
current = current.right;
}
else {
while(current.right != null || current.left != null) {
if(key.compareTo(current.data) < 0) {
stack.push(current);
current = current.left;
}
if(key.compareTo(current.data) > 0) {
stack.push(current);
current = current.right;
}
}
}
if(key.compareTo(stack.peek().data) < 0)
stack.peek().left = added;
else if(key.compareTo(stack.peek().data) > 0)
stack.peek().right = added;
if(!stack.isEmpty())
this.reheap(added, stack);
return true;
}
}
}
private boolean reheap(Node<E> added, Stack<Node<E>> stack) {
while(added.priority > stack.peek().priority && !stack.isEmpty()) {
if(stack.peek().right == added)
stack.peek().rotateLeft();
else
stack.peek().rotateRight();
stack.pop();
}
return true;
}在第二次调用( testTree.add (2 ,31)；)之后，我应该会得到一个带有结构的树( Node(2，null，Node(4 )。<--这当然是在重新堆积之后。
回答 1
Stack Overflow用户
回答已采纳
发布于 2019-04-28 01:06:04
在窥视堆栈之前，您需要进行空栈检查！
while(!stack.isEmpty() && added.priority > stack.peek().priority) {...}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/55882490
复制相关文章
相似问题