[infostudents] Re: Info II Uebung 10

  • From: "Jonas Gehring" <jonas.gehring@xxxxxxxxxxxx>
  • To: infostudents@xxxxxxxxxxxxx
  • Date: Thu, 5 Jul 2007 10:06:39 +0200

Hi Matthias,

Stimmt, du hast recht. Naja jetzt isses auch zu spät :(
Danke trotzdem.

- Jonas


2007/7/5, Matthias Frorath <Takatoo@xxxxxx>:

 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");
 }
}





Other related posts: