[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);
                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: