[infostudents] Re: Info II Uebung 10
- From: "Jonas Gehring" <jonas.gehring@xxxxxxxxxxxx>
- To: infostudents@xxxxxxxxxxxxx
- Date: Thu, 5 Jul 2007 01:39:33 +0200
Hi,
Ja, jetzt wo ihr es erwähnt... das passt dann auch mit der Definition
der Höhe in 1c) zusammen.
Argh.
- Jonas
2007/7/5, Justus Bisser <justus@xxxxxxxxxxxx>:
Hallo Jendrik,
Ich kann Deine Meinung nut bestätigen
Gruß
Justus
Jendrik Seipp schrieb:
> 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);
>> 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:
