Problem with building tree bottom up
- by Esmond
Hi,
I have problems building a binary tree from the bottom up.
THe input of the tree would be internal nodes of the trees with the children of this node being the leaves of the eventual tree.
So initially if the tree is empty the root would be the first internal node.
Afterwards, The next internal node to be added would be the new root(NR), with the old root(OR) being one of the child of NR. And so on.
The problem i have is that whenever i add a NR, the children of the OR seems to be lost when i do a inOrder traversal. This is proven to be the case when i do a getSize() call which returns the same number of nodes before and after addNode(Tree,Node)
Any help with resolving this problem is appreciated
edited with the inclusion of node class code.
both tree and node classes have the addChild methods because i'm not very sure where to put them for it to be appropriated. any comments on this would be appreciated too.
The code is as follows:
import java.util.*;
public class Tree {
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);
}
}
}
public class 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;
}
}
}
