## [infostudents] Re: Info II Uebung 10

• From: Matthias Frorath <Takatoo@xxxxxx>
• To: infostudents@xxxxxxxxxxxxx
• Date: Thu, 05 Jul 2007 02:36:55 +0200

```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.
*/
{
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);
```