data structures - whats wrong with my implementation of Tree in java -

data structures - whats wrong with my implementation of Tree in java -

im trying implement tree holds list of children of given node. when seek output size in main method returns 1. can see if theres wrong createnode method? , before gets angry, i'm including of code can see i'm trying :)

public class linkedtree<e> implements tree<e> { protected treeposition<e> root; // reference root protected int size; // number of nodes public linkedtree() { root = null; // start empty tree size = 0; } /** returns number of nodes in tree. */ public int size() { homecoming size; } /** returns whether tree empty. */ public boolean isempty() { homecoming (size == 0); } /** returns whether node internal. */ public boolean isinternal(position<e> v) throws invalidpositionexception { homecoming !isexternal(v); } /** returns whether node external. */ public boolean isexternal(position<e> v) throws invalidpositionexception { treeposition<e> vv = checkposition(v); // auxiliary method homecoming (vv.getchildren() == null) || vv.getchildren().isempty(); } /** returns whether node root. */ public boolean isroot(position<e> v) throws invalidpositionexception { checkposition(v); homecoming (v == root()); } /** returns root of tree. */ public position<e> root() throws emptytreeexception { if (root == null) throw new emptytreeexception("the tree empty"); homecoming root; } /** returns parent of node. */ public position<e> parent(position<e> v) throws invalidpositionexception, boundaryviolationexception { treeposition<e> vv = checkposition(v); position<e> parentpos = vv.getparent(); if (parentpos == null) throw new boundaryviolationexception("no parent"); homecoming parentpos; } /** returns iterable collection of children of node. */ public iterable<position<e>> children(position<e> v) throws invalidpositionexception { treeposition<e> vv = checkposition(v); if (isexternal(v)) throw new invalidpositionexception( "external nodes have no children"); homecoming vv.getchildren(); } /** returns iterable collection of tree nodes. */ public iterable<position<e>> positions() { positionlist<position<e>> positions = new nodepositionlist<position<e>>(); if (size != 0) preorderpositions(root(), positions); // assign positions in // preorder homecoming positions; } /** returns iterator of elements stored @ nodes */ public iterator<e> iterator() { iterable<position<e>> positions = positions(); positionlist<e> elements = new nodepositionlist<e>(); (position<e> pos : positions) elements.addlast(pos.element()); homecoming elements.iterator(); // iterator of elements } /** replaces element @ node. */ public e replace(position<e> v, e o) throws invalidpositionexception { treeposition<e> vv = checkposition(v); e temp = v.element(); vv.setelement(o); homecoming temp; } /** adds root node empty tree */ public position<e> addroot(e e) throws nonemptytreeexception { if (!isempty()) throw new nonemptytreeexception("tree has root"); size = 1; root = createnode(e, null, null); homecoming root; } /** swap elements @ 2 nodes */ public void swapelements(position<e> v, position<e> w) throws invalidpositionexception { treeposition<e> vv = checkposition(v); treeposition<e> ww = checkposition(w); e temp = w.element(); ww.setelement(v.element()); vv.setelement(temp); } /** if v tree node, cast treeposition, else throw exception */ protected treeposition<e> checkposition(position<e> v) throws invalidpositionexception { if (v == null || !(v instanceof treeposition)) throw new invalidpositionexception("the position invalid"); homecoming (treeposition<e>) v; } /** creates new tree node */ protected treeposition<e> createnode(e element, treeposition<e> parent, positionlist<position<e>> children) { homecoming new treenode<e>(element, parent, children); } /** * creates list storing the nodes in subtree of node, ordered * according preorder traversal of subtree. */ protected void preorderpositions(position<e> v, positionlist<position<e>> pos) throws invalidpositionexception { pos.addlast(v); (position<e> w : children(v)) preorderpositions(w, pos); // recurse on each kid } public iterator<e> iteratoro() { homecoming null; } public boolean islnternal(position<e> v) throws invalidpositionexception { homecoming false; } public static void main(string[] args) { linkedtree<character> t = new linkedtree(); // add together root t.addroot('a'); // add together children of root t.createnode('b', (treenode) (t.root()), new nodepositionlist()); treeposition c = t.createnode('c', (treenode) (t.root()), new nodepositionlist()); t.createnode('d', (treenode) (t.root()), new nodepositionlist()); // add together children of node c t.createnode('e', c, new nodepositionlist()); treeposition f = t.createnode('f', c, new nodepositionlist()); t.createnode('g', c, new nodepositionlist()); // add together childrn of node f t.createnode('h', f, new nodepositionlist()); t.createnode('i', f, new nodepositionlist()); // print out tree system.out.println("size = " + t.size()); } }

simple. value of size not set adequately. there 2 places size ever accessed write.

line 4: protected int size; // number of nodes line 8: size = 0; line 12: public int size() { line 13: homecoming size; line 18: homecoming (size == 0); line 69: if (size != 0) line 97: size = 1; line 173: system.out.println("size = " + t.size());

and size() method:

/** returns number of nodes in tree. */ public int size() { homecoming size; }

main problem seems size redundant. however, prevents parsing whole tree determine element count, can considered cache.

as experienced right now, general problem caches , other redundant info is, need track them , maintain them date. placing assert statements strategically can help task.

java data-structures tree linked-list