Hi Jonas,bei der Aufgabe 2b, wo man den Baum zeichnen muss, fehlt 1 kleiner Parent-Pfeil von der 15 zur 13.
Sonst: echt schöne Lösung. :) Matthias Jonas Gehring schrieb:
Hi Liste, Hier mal unsere Lösung. Steht allerdings nur mein Name drauf weil wir ja getrennt abgeben müssen. - Jonas, Denis ------------------------------------------------------------------------ /* * Tree structure using sibling nodes * written by Jonas Gehring - 2321622 */ class ChildSiblingNode { int key; ChildSiblingNode parent; ChildSiblingNode child; ChildSiblingNode left; ChildSiblingNode right; /* * Creates a new node with a given key */ public ChildSiblingNode(int key) { this.key = key; parent = child = null; left = right = this; } /* * Adds a node with a given key as a child to this node * and returns it. * Runs in O(1) because it only needs to set a few * references. */ public ChildSiblingNode addChild(int key) { ChildSiblingNode t = new ChildSiblingNode(key); t.parent = this; if (child == null) // Add new single child { child = t; } else // Insert into child list {ChildSiblingNode s = child.left; child.left = t;child.left.right = child; child.left.left = s; s.right = child.left; } return t; } /* * Removes this node with all childs from is parent and * from the list of its siblings. * Runs in O(1). */ public void cut() { if (left == this) // No other childs at this level { parent.child = null; } else { left.right = right; right.left = left; parent.child = right; } } }------------------------------------------------------------------------/* * Tree structure using sibling nodes - testing program * written by Jonas Gehring - 2321622 */ class CSNTest { // Program entry point public static void main(String[] args) { ChildSiblingNode root = new ChildSiblingNode(2); ChildSiblingNode csn13 = root.addChild(13); root.addChild(45); ChildSiblingNode csn8 = root.addChild(8); ChildSiblingNode csn15 = csn13.addChild(15); csn15.addChild(16); csn15.addChild(31); csn15.addChild(29); csn8.addChild(36); ChildSiblingNode csn21 = csn8.addChild(21); csn21.addChild(26); System.out.println("Tree generated"); } }