У меня проблемы с построением двоичного дерева снизу вверх.
Входные данные дерева будут внутренними узлами деревьев, а потомками этого узла будут листья конечного дерева.
Итак, изначально, если дерево пустое, корень будет первым внутренним узлом.
Впоследствии следующим внутренним узлом, который будет добавлен, будет новый корень (NR), причем старый корень (OR) является одним из дочерних элементов NR. И так далее.
Проблема, с которой я столкнулся, заключается в том, что всякий раз, когда я добавляю NR, дочерние элементы OR, похоже, теряются, когда я выполняю обход inOrder. Доказано, что это тот случай, когда я выполняю вызов getSize (), который возвращает одинаковое количество узлов до и после addNode (Tree, Node)
Любая помощь в решении этой проблемы приветствуется
отредактировано с включением кода класса узла.
и классы дерева, и классы узлов имеют методы addChild, потому что я не очень уверен, где их разместить, чтобы они были присвоены. Любые комментарии по этому вопросу также будут оценены.
Код выглядит следующим образом:
import java.util.*;</p>
<p>public class Tree {</p>
<pre><code>Node root;
int size;
public Tree() {
root = null;
}
public Tree(Node root) {
this.root = root;
}
public static void setChild(Node parent, Node child, double weight) throws ItemNotFoundException {
if (parent.child1 != null && parent.child2 != null) {
throw new ItemNotFoundException("This Node already has 2 children");
} else if (parent.child1 != null) {
parent.child2 = child;
child.parent = parent;
parent.c2Weight = weight;
} else {
parent.child1 = child;
child.parent = parent;
parent.c1Weight = weight;
}
}
public static void setChild1(Node parent, Node child) {
parent.child1 = child;
child.parent = parent;
}
public static void setChild2(Node parent, Node child) {
parent.child2 = child;
child.parent = parent;
}
public static Tree addNode(Tree tree, Node node) throws ItemNotFoundException {
Tree tree1;
if (tree.root == null) {
tree.root = node;
} else if (tree.root.getSeq().equals(node.getChild1().getSeq()) ||
tree.root.getSeq().equals(node.getChild2().getSeq())) {
Node oldRoot = tree.root;
oldRoot.setParent(node);
tree.root = node;
} else { //form a disjoint tree and merge the 2 trees
tree1 = new Tree(node);
tree = mergeTree(tree, tree1);
}
System.out.print("addNode2 = ");
if(tree.root != null ) {
Tree.inOrder(tree.root);
}
System.out.println();
return tree;
}
public static Tree mergeTree(Tree tree, Tree tree1) {
String root = "root";
Node node = new Node(root);
tree.root.setParent(node);
tree1.root.setParent(node);
tree.root = node;
return tree;
}
public static int getSize(Node root) {
if (root != null) {
return 1 + getSize(root.child1) + getSize(root.child2);
} else {
return 0;
}
}
public static boolean isEmpty(Tree Tree) {
return Tree.root == null;
}
public static void inOrder(Node root) {
if (root != null) {
inOrder(root.child1);
System.out.print(root.sequence + " ");
inOrder(root.child2);
}
}
}
открытый класс Node {
Node child1;
Node child2;
Node parent;
double c1Weight;
double c2Weight;
String sequence;
boolean isInternal;
public Node(String seq) {
sequence = seq;
child1 = null;
c1Weight = 0;
child2 = null;
c2Weight = 0;
parent = null;
isInternal = false;
}
public boolean hasChild() {
if (this.child1 == null && this.child2 == null) {
this.isInternal = false;
return isInternal;
} else {
this.isInternal = true;
return isInternal;
}
}
public String getSeq() throws ItemNotFoundException {
if (this.sequence == null) {
throw new ItemNotFoundException("No such node");
} else {
return this.sequence;
}
}
public void setChild(Node child, double weight) throws ItemNotFoundException {
if (this.child1 != null && this.child2 != null) {
throw new ItemNotFoundException("This Node already has 2 children");
} else if (this.child1 != null) {
this.child2 = child;
this.c2Weight = weight;
} else {
this.child1 = child;
this.c1Weight = weight;
}
}
public static void setChild1(Node parent, Node child) {
parent.child1 = child;
child.parent = parent;
}
public static void setChild2(Node parent, Node child) {
parent.child2 = child;
child.parent = parent;
}
public void setParent(Node parent){
this.parent = parent;
}
public Node getParent() throws ItemNotFoundException {
if (this.parent == null) {
throw new ItemNotFoundException("This Node has no parent");
} else {
return this.parent;
}
}
public Node getChild1() throws ItemNotFoundException {
if (this.child1 == null) {
throw new ItemNotFoundException("There is no child1");
} else {
return this.child1;
}
}
public Node getChild2() throws ItemNotFoundException {
if (this.child2 == null) {
throw new ItemNotFoundException("There is no child2");
} else {
return this.child2;
}
}
}
</p>
<p>