[infostudents] Info II Uebung 10

  • From: "Jonas Gehring" <jonas.gehring@xxxxxxxxxxxx>
  • To: infostudents@xxxxxxxxxxxxx
  • Date: Wed, 4 Jul 2007 21:32:25 +0200

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: