[infostudents] Re: Info 10 Blatt 10
- From: "Jonas Gehring" <jonas.gehring@xxxxxxxxxxxx>
- To: infostudents@xxxxxxxxxxxxx
- Date: Wed, 4 Jul 2007 17:45:29 +0200
Wieso machst du denn in ChildSiblingNode so viele Unterscheidungen
beim Einfügen? Ich denke die Liste ergibt sich von selbst, wenn du
einfach immer nur an einer Seite einfügst.
Als Anhang mal unsere Lösung
- Jonas
Am 04.07.07 schrieb Cornelius Amzar <cornelius.amzar@xxxxxx>:
Hier mal meine Lösung, für Anmerkungen wäre ich sehr dankbar.
--
Erstellt mit Operas revolutionärem E-Mail-Modul: http://www.opera.com/mail/
/*
* 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;
}
}
}
Other related posts:
