[infostudents] Re: Info II Uebung 10

  • From: Justus Bisser <justus@xxxxxxxxxxxx>
  • To: infostudents@xxxxxxxxxxxxx
  • Date: Thu, 05 Jul 2007 00:34:25 +0200

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: