StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I think, you need to store helpful information in nodes, so predicate can choose preceding node from pair of unconnected nodes. </p> <p>Here's my (may be not very clever or, even, working) attempt:</p> <pre><code>import java.util.ArrayList; import java.util.Collections; import java.util.List; /** * */ public class SortingTree { private static class Node implements Comparable<Node> { private final String data; private Node p, l, r; private int ordinal = 0; public Node(String data) { this.data = data; } public Node setLeft(Node n) { n.ordinal = ordinal + 1; if (ordinal == 0) n.ordinal = 2; else n.ordinal = ordinal + 2; n.p = this; return n; } public Node setRight(Node n) { if (ordinal == 0) n.ordinal = 1; else n.ordinal = ordinal + 4; n.p = this; return n; } public String toString() { return data; } public int compareTo(Node o) { // check if one of args is root if (p == null && o.p != null) return -1; if (p != null && o.p == null) return 1; if (p == null && o.p == null) return 0; // check if one of args is left subtree, while other is right if (ordinal % 2 == 0 && o.ordinal % 2 == 1) return -1; if (ordinal % 2 == 1 && o.ordinal % 2 == 0) return 1; // if ordinals are the same, first element is the one which parent have bigger ordinal if (ordinal == o.ordinal) { return o.p.ordinal - p.ordinal; } return ordinal - o.ordinal; } } public static void main(String[] args) { List<Node> nodes = new ArrayList<Node>(); Node root = new Node("root"); nodes.add(root); Node left = root.setLeft(new Node("A")); nodes.add(left); Node leftLeft = left.setLeft(new Node("C")); nodes.add(leftLeft); nodes.add(leftLeft.setLeft(new Node("D"))); nodes.add(left.setRight(new Node("E"))); Node right = root.setRight(new Node("B")); nodes.add(right); nodes.add(right.setLeft(new Node("F"))); nodes.add(right.setRight(new Node("G"))); Collections.sort(nodes); System.out.println(nodes); } } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload