Question

inorderDraw(): This function assigns x coordinates to nodes so that each node gets a distinct x-coordinate, and each node receives an x-coordinate between that of its two children.

Actions Actions

_____________________________________

package comp2402a4;

import java.util.Random;

public class GeometricTree extends BinaryTree {

   public GeometricTree() {
       super (new GeometricTreeNode());
   }
  
   /**
   * Set the x and y-coordinates of each node such that it is between the
   * x-coordinate of its two children, no two nodes have the same
   * x-coordinate, and each level of the tree is drawn on separate y-coordinates.
   */
   public void inorderDraw() {
       assignLevels();
       // TODO: use your code here instead
       Random rand = new Random();
       randomX(r, rand);
   }
  
  
   /**
   * Set the x- and y-coordinates of each node such that each node
   * has an x-coordinate as small as possible without overlapping
   * any other node at the same level and each level of the tree is
   * drawn on separate y-coordinates
   */
   public void leftistDraw() {
       assignLevels();
       // TODO: use your code here instead
       Random rand = new Random();
       randomX(r, rand);
   }
  
   /**
   * Set the x- and y-coordinate of each node such that the smaller
   * of a node's two subtrees is drawn directly below the node, and the
   * larger is drawn directly to the right, but far enough away that
   * it does not intersect with the smaller subtree.
   */
   public void balancedDraw() {
       assignLevels();
       // TODO: use your code here instead
       Random rand = new Random();
       randomX(r, rand);
   }
  
   /**This function randomly assign's x values to each node in the tree.
   It is for demonstration purposes only*/
   protected void randomX(GeometricTreeNode u, Random r) {
       if (u == null) return;
       u.position.x = r.nextInt(60);
       randomX(u.left, r);
       randomX(u.right, r);
   }
  
      
   /**This function sets the y values for all nodes in the tree according to their depth*/
   protected void assignLevels() {
       assignLevels(r, 0);
   }
  
   protected void assignLevels(GeometricTreeNode u, int i) {
       if (u == null) return;
       u.position.y = i;
       assignLevels(u.left, i+1);
       assignLevels(u.right, i+1);
   }
  
   public static void main(String[] args) {
       GeometricTree t = new GeometricTree();
       galtonWatsonTree(t, 100);
       System.out.println(t);
       t.inorderDraw();
       System.out.println(t);
   }
  
}

Answer 1

import java.awt.*;
import java.awt.event.*;
import javax.swing.JMenu;
import javax.swing.JMenuItem;
import javax.swing.JMenuBar;
import javax.swing.JPanel;
import javax.swing.JScrollPane;
import javax.swing.JFrame;

public class GeometricTreeDemo implements ActionListener, ItemListener {
    GeometricTree t;
    JPanel output;
    JScrollPane scrollPane;
    String newline = "\n";

    public GeometricTreeDemo() {
        t = new GeometricTree();
        GeometricTree.completeBinaryTree(t, 50);
        t.inorderDraw();
    }

    public JMenuBar createMenuBar() {
        JMenuBar menuBar;
        JMenu menu;
        JMenuItem menuItem;

        // Create the menu bar.
        menuBar = new JMenuBar();

        // Build the first menu.
        menu = new JMenu("Actions");
        menuBar.add(menu);

        // a group of JMenuItems
        menuItem = new JMenuItem("new galton-watson tree");
        menuItem.addActionListener(this);
        menu.add(menuItem);

        menuItem = new JMenuItem("new complete binary tree");
        menuItem.addActionListener(this);
        menu.add(menuItem);

        menu.addSeparator();

        menuItem = new JMenuItem("in-order layout");
        menuItem.addActionListener(this);
        menu.add(menuItem);

        menuItem = new JMenuItem("leftist layout");
        menuItem.addActionListener(this);
        menu.add(menuItem);

        menuItem = new JMenuItem("balanced layout");
        menuItem.addActionListener(this);
        menu.add(menuItem);

        menuBar.add(menu);

        return menuBar;
    }

    public Container createContentPane() {
        // Create the content-pane-to-be.
        JPanel contentPane = new JPanel(new BorderLayout());
        contentPane.setOpaque(true);

        // Create a scrolled text area.
        output = new JPanel() {
            private static final long serialVersionUID = 2196729896823372494L;
            public void paint(Graphics g) {
                if (t != null) recursivePaint(g, t.r);
            }
            protected void recursivePaint(Graphics g, GeometricTreeNode u) {
                final int r = 10, m = 20;
                if (u == null) return;
                g.fillOval(u.position.x * m, u.position.y * m, r, r);
                if (u.left != null) {
                    g.drawLine(u.position.x * m + r/2, u.position.y * m + r/2,
                            u.left.position.x * m + r/2, u.left.position.y *m + r/2);
                    recursivePaint(g, u.left);
                }
                if (u.right != null) {
                    g.drawLine(u.position.x * m + r/2, u.position.y * m + r/2,
                            u.right.position.x * m + r/2, u.right.position.y *m + r/2);
                    recursivePaint(g, u.right);
                }
            }
        };

        // Add the text area to the content pane.
        contentPane.add(output, BorderLayout.CENTER);

        return contentPane;
    }

    public void actionPerformed(ActionEvent e) {
        JMenuItem source = (JMenuItem) (e.getSource());
        String s = "Action event detected." + newline + "    Event source: "
                + source.getText();
        System.out.println(s);
        if (source.getText().equals("new galton-watson tree")) {
            t.clear();
            GeometricTree.galtonWatsonTree(t, 100);
            t.inorderDraw();
            output.repaint();
        } else    if (source.getText().equals("new complete binary tree")) {
            t.clear();
            GeometricTree.completeBinaryTree(t, 50);
            t.inorderDraw();
            output.repaint();
        } else if (source.getText().equals("in-order layout")) {
            t.inorderDraw();
            output.repaint();
        } else if (source.getText().equals("leftist layout")) {
            t.leftistDraw();
            output.repaint();
        } else if (source.getText().equals("balanced layout")) {
            t.balancedDraw();
            output.repaint();
        }

    }

    public void itemStateChanged(ItemEvent e) {
//       JMenuItem source = (JMenuItem) (e.getSource());
//       String s = "Item event detected."
//               + newline
//               + "    Event source: "
//               + source.getText()
//               + newline
//               + "    New state: "
//               + ((e.getStateChange() == ItemEvent.SELECTED) ? "selected"
//                       : "unselected");
//       System.out.println(s);
    }

    private static void createAndShowGUI() {
        // Create and set up the window.
        JFrame frame = new JFrame("MenuDemo");
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

        // Create and set up the content pane.
        GeometricTreeDemo demo = new GeometricTreeDemo();
        frame.setJMenuBar(demo.createMenuBar());
        frame.setContentPane(demo.createContentPane());

        // Display the window.
        frame.setSize(450, 260);
        frame.setVisible(true);
    }

    public static void main(String[] args) {
      
        javax.swing.SwingUtilities.invokeLater(new Runnable() {
            public void run() {
                createAndShowGUI();
            }
        });
    }
}
---------------------------------------------------------------------------------------
import java.util.Random;
import java.util.LinkedList;
import java.util.Queue;

public class GeometricTree extends BinaryTree<GeometricTreeNode> {

    public GeometricTree() {
        super (new GeometricTreeNode());
    }

    public void inorderDraw() {
        assignLevels();
        GeometricTreeNode u = r;
        GeometricTreeNode p;
        p = u;
        int count = 0;

        while(u != null){
            if(p == u.right){
                p = u;
                u = u.parent;
            }
            else if(u.left != null && p != u.left){
                p = u;
                u = u.left;
            }
            else if(u.right != null){
                u.position.x = count;
                count ++;
                p = u;
                u = u.right;
            }
            else{
                u.position.x = count;
                count ++;
                p = u;
                u = u.parent;
            }

        }
    }

    protected void randomX(GeometricTreeNode u, Random r) {
        if (u == null) return;
        u.position.x = r.nextInt(60);
        randomX(u.left, r);
        randomX(u.right, r);
    }

    /**
     * Draw each node so that it's x-coordinate is as small
     * as possible without intersecting any other node at the same level
     * the same as its parent's
     */
    public void leftistDraw() {
        assignLevels();
        GeometricTreeNode d = r;
        d.position.x = -1;

        Queue<GeometricTreeNode> q = new LinkedList<GeometricTreeNode>();
        q.add(r);

        while(!q.isEmpty()){
            GeometricTreeNode u = q.remove();

            if(d.position.y == u.position.y){
                u.position.x = d.position.x + 1;
                d = u;
            }

            else{
                u.position.x = 0;
                d = u;
            }

            if(u.left != nil){
                q.add(u.left);
            }

            if(u.right != nil){
                q.add(u.right);
            }
        }
    }

    public void balancedDraw() {
        calculateSizes(r);
        int x = 0;
        int y = 0;
        GeometricTreeNode current = firstNode();
        while(current != nil){
            current.size = currentSize(current);
            current = nextNode2(current);
        }
        current = r;
        do{
            while(current.left != nil || current.right != nil){
                if(current.left != nil && current.right != nil){
                    current = smallerChild(current);
                    y++;
                }
                else{
                    if(current.left != nil){
                        current = current.left;
                    }
                    else{
                        current = current.right;
                    }
                    x++;
                }
                setPosition(current, x, y);
            }
            do{
                current = current.parent;
            }while(current != nil && ((current.left == nil || current.right == nil) || largerChild(current).position.x > 0));
            if(current == nil){
                break;
            }
            y = current.position.y;
            current = largerChild(current);
            current.position.y = y;
            x++;
            current.position.x = x;
        }while(true);
    }

    private void calculateSizes(GeometricTreeNode u){
        if(u == null){
            return;
        }
        u.position.x = 0;
        calculateSizes(u.left);
        calculateSizes(u.right);
    }

    private void setPosition(GeometricTreeNode u, int x, int y){
        u.position.x = x;
        u.position.y = y;
    }

    private int currentSize(GeometricTreeNode u){
        if(u.left != nil && u.right != nil){
            return(u.left.size + u.right.size + 1);
        }

        if(u.left != nil){
            return(u.left.size + 1);
        }

        else if(u.right != nil){
            return(u.right.size + 1);
        }

        return 1;
    }

    private GeometricTreeNode nextNode2(GeometricTreeNode u){
        if(u.parent != nil && u.parent.left == u){
            u = u.parent;
            if(u.right != nil){
                u = u.right;
                while(u.left != nil || u.right != nil){
                    while(u.left != nil){
                        u = u.left;
                    }
                    if(u.right != nil){
                        u = u.right;
                    }
                }
            }
        }
        else{
            u = u.parent;
        }
        return u;
    }

    private GeometricTreeNode smallerChild(GeometricTreeNode u){
        if(u.left.size < u.right.size){
            return u.left;
        }
        else{
            return u.right;
        }
    }

    private GeometricTreeNode largerChild(GeometricTreeNode u){
        if(u.left.size < u.right.size){
            return u.right;
        }
        else{
            return u.left;
        }
    }

    protected void assignLevels() {
        assignLevels(r, 0);
    }

    protected void assignLevels(GeometricTreeNode u, int i) {
        if (u == null) return;
        u.position.y = i;
        assignLevels(u.left, i+1);
        assignLevels(u.right, i+1);
    }

    public static void main(String[] args) {
        GeometricTree t = new GeometricTree();
        galtonWatsonTree(t, 100);
        System.out.println(t);
        t.inorderDraw();
        System.out.println(t);
    }

}
-----------------------------------------------------------------------
import java.util.LinkedList;
import java.util.Queue;
import java.util.Random;

public class BinaryTree<Node extends BinaryTreeNode<Node>> {

    protected Node sampleNode;

    public Node r;

    protected Node nil;

    protected BinaryTree(Node nil) {
        sampleNode = nil;
        this.nil = null;
    }

    protected BinaryTree() { }

    @SuppressWarnings({"unchecked"})
    protected Node newNode() {
        try {
            Node u = (Node)sampleNode.getClass().newInstance();
            u.parent = u.left = u.right = nil;
            return u;
        } catch (Exception e) {
            return null;
        }
    }

    public int depth(Node u) {
        int d = 0;
        while (u != r) {
            u = u.parent;
            d++;
        }
        return d;
    }

    public int size() {
        return size(r);
    }

    protected int size(Node u) {
        if (u == nil)
            return 0;
        return 1 + size(u.left) + size(u.right);
    }

    public int height() {
        return height(r);
    }

    protected int height(Node u) {
        if (u == nil)
            return -1;
        return 1 + Math.max(height(u.left), height(u.right));
    }

    public boolean isEmpty() {
        return r == nil;
    }

    public void clear() {
        r = nil;
    }

    public void traverse(Node u) {
        if (u == nil) return;
        traverse(u.left);
        traverse(u.right);
    }

    public void traverse2() {
        Node u = r, prev = nil, next;
        while (u != nil) {
            if (prev == u.parent) {
                if (u.left != nil) next = u.left;
                else if (u.right != nil) next = u.right;
                else next = u.parent;
            } else if (prev == u.left) {
                if (u.right != nil) next = u.right;
                else next = u.parent;
            } else {
                next = u.parent;
            }
            prev = u;
            u = next;
        }
    }

    public int size2() {
        Node u = r, prev = nil, next;
        int n = 0;
        while (u != nil) {
            if (prev == u.parent) {
                n++;
                if (u.left != nil) next = u.left;
                else if (u.right != nil) next = u.right;
                else next = u.parent;
            } else if (prev == u.left) {
                if (u.right != nil) next = u.right;
                else next = u.parent;
            } else {
                next = u.parent;
            }
            prev = u;
            u = next;
        }
        return n;
    }

    public void bfTraverse() {
        Queue<Node> q = new LinkedList<Node>();
        q.add(r);
        while (!q.isEmpty()) {
            Node u = q.remove();
            if (u.left != nil) q.add(u.left);
            if (u.right != nil) q.add(u.right);
        }
    }

    protected Node firstNode() {
        Node w = r;
        if (w == nil) return nil;
        while (w.left != nil)
            w = w.left;
        return w;
    }

    protected Node nextNode(Node w) {
        if (w.right != nil) {
            w = w.right;
            while (w.left != nil)
                w = w.left;
        } else {
            while (w.parent != nil && w.parent.left != w)
                w = w.parent;
            w = w.parent;
        }
        return w;
    }

    public static <Node extends BinaryTreeNode<Node>> void completeBinaryTree(BinaryTree<Node> t, int n) {
        Queue<Node> q = new LinkedList<Node>();
        t.clear();
        if (n == 0)
            return;
        t.r = t.newNode();
        q.add(t.r);
        while (--n > 0) {
            Node u = q.remove();
            u.left = t.newNode();
            u.left.parent = u;
            q.add(u.left);
            if (--n > 0) {
                u.right = t.newNode();
                u.right.parent = u;
                q.add(u.right);
            }
        }
    }

    public static <Node extends BinaryTreeNode<Node>> void galtonWatsonFullTree(BinaryTree<Node> t, int n) {
        Random r = new Random();
        Queue<Node> q = new LinkedList<Node>();
        t.clear();
        t.r = t.newNode();
        q.add(t.r);
        double p = ((double)0.5 - ((double)1)/(n+n));
        while (!q.isEmpty()) {
            Node u = q.remove();
            if (r.nextDouble() < p) {
                u.left = t.newNode();
                u.left.parent = u;
                q.add(u.left);
                u.right = t.newNode();
                u.right.parent = u;
                q.add(u.right);
            }
        }
    }

    static <Node extends BinaryTreeNode<Node>> void galtonWatsonTree(BinaryTree<Node> t, int n) {
        Random r = new Random();
        Queue<Node> q = new LinkedList<Node>();
        t.clear();
        t.r = t.newNode();
        q.add(t.r);
        double p = ((double)0.5 - ((double)1)/(n+n));
        while (!q.isEmpty()) {
            Node u = q.remove();
            if (r.nextDouble() < p) {
                u.left = t.newNode();
                u.left.parent = u;
                q.add(u.left);
            } if (r.nextDouble() < p) {
                u.right = t.newNode();
                u.right.parent = u;
                q.add(u.right);
            }
        }
    }

}
------------------------------------------------------------------------------------------------------------------------
public class BinaryTreeNode<Node extends BinaryTreeNode<Node>> {
    public Node left;
    public Node right;
    public Node parent;
    public int size = 0;
}
-----------------------------------------------------------------------------------------------------------------------
public class GeometricTreeNode extends BinaryTreeNode<GeometricTreeNode> {
    public Point2D position;

    public GeometricTreeNode() {
        position = new Point2D();
    }

    public String toString() {
        return position.toString();
    }
}
---------------------------------------------------------------------------------------------------------------------
public class Point2D {
    public int x, y;

    public String toString() {
        return "(" + x + "," + y + ")";
    }
}

deaProjects/Geo Project import java.awt.* import java.awt.event.* import javax. swing. JMenu; inport javax.swing.JMenuItem; import javax.swing. JMenuBar: import javax.swing.JPanel; import javax. swing.JScrollPane; import javax. swing.JFrame idea BinaryTree Ο BinaryTreeNode G Geometric Tree MenuDemo GeometricTreeDemo GeometricTreeNode Point2D Actions İ' GeometricTree.imi illExternal Libraries public JMenuBar create enuBar() { 29 30 JMenuBar menuBar; JMenu menu; Run Main /Library/Java/JavaVirtualMachines/jdk-9.0.4.jdk/Contents/Home/bin/java "-javaagent:/Applications/Intelli IDEA CE.app/Contents/lib/idea_rt.jar-51634:/Applications/Intellid IDEA CE.app/Contents/bi compilation completed successfully in 28 632ms (a minute ego) 171:2 LF: UTF-8; 'b Q