Я работаю над домашним заданием для своего класса и пытаюсь преобразовать сбалансированное двоичное дерево в кучу, используя код, предоставленный профессором.
Его основными инструкциями было создание метода с именем rebuildTree,и этот метод будет принимать только что добавленный узел и менять родительский узел на новый, если новый узел больше родительского.
У меня есть тестовый метод rebuildTree, который пока работает наполовину, когда я делаюSysout для проверки моих значений, но не похоже, что родитель и потомок меняются на те, кем я хочу, чтобы они были.
/* This is the BalancedBTree class that the professor provided */
import java.util.Queue;
import java.util.LinkedList;
public class BalancedBTree {
private Node firstNode = null;
private Node currentParent = null;
public void addNode(int n) {
if(firstNode == null) {
firstNode = new Node(n);
currentParent = firstNode;
} else {
createNextNode(n);
}
}
public void createNextNode(int n) {
Node nextNode = new Node(n);
if(currentParent.getLeftNode() == null) {
nextNode.setParentNode(currentParent);
currentParent.setLeftNode(nextNode);
rebuildTree(nextNode,currentParent);
} else {
currentParent.setRightNode(nextNode);;
nextNode.setParentNode(currentParent);
rebuildTree(nextNode,currentParent);
}
}
/* --This is my rebuildTree method that I am trying to implement-- */
public void rebuildTree(final Node compareNode, final Node currentParent) {
Node nextNode = compareNode;
Node tempNode = currentParent;
int nxtNode = nextNode.getPayload();
int currParent = currentParent.getPayload();
if(nextNode.getParentNode() != null){
if(nxtNode > currParent){
currentParent.setParentNode(nextNode);
System.out.println(currentParent.getParentNode().getPayload());
nextNode.setLeftNode(currentParent);
System.out.println(nextNode.getLeftNode().getPayload());
}
} else {
System.out.println("false");
}
}
public void updateCurrentParent() {
if(currentParent == firstNode)
currentParent = currentParent.getLeftNode();
else {
// This code works only when called from a right child
// While you are a right child, move up a parent
while(currentParent.getParentNode().getRightNode() == currentParent) {
currentParent = currentParent.getParentNode();
// Check for first node which has no parent
if(currentParent.getParentNode() == null)
currentParent = currentParent.getLeftNode();
}
// Once you are a left hand child, move over to the right hand child.
currentParent = currentParent.getParentNode().getRightNode();
// Go down left hand side until left hanbd side is null
while(currentParent.getLeftNode() != null) {
currentParent = currentParent.getLeftNode();
}
// The currentParent pointer has now been updated
}
}
public void printBalancedBTree() {
Queue<Node> leftQ = new LinkedList<>();
Queue<Node> rightQ = new LinkedList<>();
if(firstNode != null)
leftQ.offer(firstNode);
while(!leftQ.isEmpty() || !rightQ.isEmpty()) {
if(!leftQ.isEmpty()) {
printLeftQ(leftQ,rightQ);
}
System.out.println();
if(!rightQ.isEmpty()) {
printRightQ(leftQ,rightQ);
}
System.out.println();
break;
}
}
public void printLeftQ(Queue<Node> leftQ, Queue<Node> rightQ) {
Node printNode = null;
while(!leftQ.isEmpty()) {
printNode = leftQ.poll();
System.out.print(printNode.getPayload() + "\t");
if(printNode.getLeftNode() != null)
rightQ.offer(printNode.getLeftNode());
if(printNode.getRightNode() != null)
rightQ.offer(printNode.getRightNode());
}
}
public void printRightQ(Queue<Node> leftQ, Queue<Node> rightQ) {
Node printNode = null;
while(!rightQ.isEmpty()) {
printNode = rightQ.poll();
System.out.print(printNode.getPayload() + "\t");
if(printNode.getLeftNode() != null)
leftQ.offer(printNode.getLeftNode());
if(printNode.getRightNode() != null)
leftQ.offer(printNode.getRightNode());
}
}
}
/*This is the main method that I am testing with*/
public class TestBalancedBTree
{
public static void main(String[] args)
{
BalancedBTree bbt = new BalancedBTree();
bbt.addNode(5);
bbt.addNode(10);
bbt.printBalancedBTree();
}
}
/* Adding Node Class */
public class Node {
private int payload;
private Node parentNode = null;
private Node leftNode = null;
private Node rightNode = null;
public Node(int n) {
payload = n;
}
public int getPayload() {
return payload;
}
public void setPayload(int payload){
this.payload = payload;
}
public Node getParentNode() {
return parentNode;
}
public void setParentNode(Node parentNode) {
this.parentNode = parentNode;
}
public Node getLeftNode() {
return leftNode;
}
public void setLeftNode(Node leftNode) {
this.leftNode = leftNode;
}
public Node getRightNode() {
return rightNode;
}
public void setRightNode(Node rightNode) {
this.rightNode = rightNode;
}
}
Мой вывод, когда я выполняю свой метод rebuildTree, предоставляет мне:
10 5
Но тогда метод printBalancedTree показывает: 5 10
Я не уверен, где я ошибаюсь, но любая помощь очень ценится.