## [infostudents] Re: Info II Uebung 10

• From: Jendrik Seipp <Jendrik.Seipp@xxxxxxxxxxxxxxxxxxxx>
• To: infostudents@xxxxxxxxxxxxx
• Date: Thu, 05 Jul 2007 00:23:28 +0200

```Hi,

```
ich glaube deine Suchbäume der Höhe 3 haben Höhe 4. So steht's zumindest in den Folien:
```
-Tiefe eines Knotens k: #Kanten von der Wurzel des Baums bis k
(Abstand von k zur Wurzel)
•Höhe h(t) eines Baumes t: Maximale Tiefe eines Blattes von t.

```
Bei der zweiten Definition steht Blatt anstelle von Knoten. Bin mir aber auch nicht ganz sicher.
```
Gruß,
Jendrik

Jonas Gehring wrote:
```
```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);
ChildSiblingNode csn8 = root.addChild(8);
ChildSiblingNode csn15 = csn13.addChild(15);
```