n_arry to binary trees problem
Hi All:
I am using java for some data structure work. I am not
sure if I am having language isssues (ie memory,
data structure problems, or both. Help...
The code for my problem is posted below:
I am trying to build a program that translates a n_arry to a binary
tree. The basic idea is that right node is used for sibling nodes from
the n_arry tree, and the left node is used to store dependent nodes.
This is a model of what I am after.
root
A
A1B
A2
C
C1
C2
C3
When I display the treee, I get a different rerust. A2 is repeated twice,
and both C2, and C3 are repeated twice. The results are given as follows:
root * A * A1 * A2 * B * C1 * C2 * C3 * C2 * C3 *
Why am I getting duplicates?
This is the code. It is simple. There is a driver class (main method), a node
class, and a tree class. The tree classes other then the constructor has two
methods. One inserts nodes into the tree, and the other displays the tree
data. There are some printlines that I have commented out. I was using
them for debugging.
class Tree {
Node root;
Tree() {root = new Node("root");}
public void insertNode(String parent, Node newnode, Node pointer) {
if(parent.equals(pointer.name)) {
if(pointer.sub == null) {
newnode.name + " insert 1, ");
pointer.sub = newnode;
newnode.name + " insert 2");
} else {
pointer = pointer.sub;
newnode.name + " insert 3, ");
while(pointer.sibling != null)
pointer = pointer.sibling;
newnode.name + " insert 4, ");
pointer.sibling = newnode;
newnode.name + " insert 5, ");
}
newnode.name + " insert 6");
return;
}
if(pointer.sub != null) {
pointer = pointer.sub;
insertNode(parent,newnode,pointer);
}
if(pointer.sibling != null) {
pointer = pointer.sibling;
insertNode(parent,newnode,pointer);
}
}
public void displayTree(Node pointer){
System.out.print("\n" + pointer.name);
if(pointer.sub != null) {
pointer = pointer.sub;
displayTree(pointer);
}
if(pointer.sibling != null) {
pointer = pointer.sibling;
displayTree(pointer);
}
}
}
class Node {
String name;
Node sub;
Node sibling;
Node(String name) {
this.name = name;
sub = null;
sibling = null;
}
}
public class TestTree2 {
public static void main(String[] args) {
Node node, pointer;
Tree tree = new Tree();
node = new Node("A");
System.out.println(tree.root.name + " from main method");
pointer = tree.root;
tree.insertNode("root", node, pointer);
node = new Node("B");
pointer = tree.root;
tree.insertNode("root", node, pointer);
node = new Node("C");
pointer = tree.root;
tree.insertNode("root", node, pointer);
node = new Node("A1");
pointer = tree.root;
tree.insertNode("A", node, pointer);
node = new Node("A2");
pointer = tree.root;
tree.insertNode("A", node, pointer);
node = new Node("C1");
pointer = tree.root;
tree.insertNode("C", node, pointer);
node = new Node("C2");
pointer = tree.root;
tree.insertNode("C",node, pointer);
node = new Node("C3");
pointer = tree.root;
tree.insertNode("C",node, pointer);
pointer = tree.root;
tree.displayTree(pointer);
}
}
/*
S:\A2_115\TestTree>java TestTree2
root from main method
root
A
A1
A2
A2
B
C
C1
C2
C3
C2
C3
*/
