fork download
copy 
  1. import java.util.ArrayList;
  2. import java.util.LinkedList;
  3. import java.util.List;
  4. import java.util.Map.Entry;
  5. import java.util.Queue;
  6. import java.util.TreeMap;
  7.  
  8.  
  9. class Treverse {
  10.  
  11.     private static final class ColumnFind<U> {
  12.         private final int column;
  13.         private final Node<U> node;
  14.  
  15.         public ColumnFind(int column, Node<U> node) {
  16.             super();
  17.             this.column = column;
  18.             this.node = node;
  19.         }
  20.  
  21.  
  22.     }
  23.  
  24.     private static final class Node<T> {
  25.  
  26.         private Node<T> left, right;
  27.         private final T value;
  28.  
  29.         public Node(T value, Node<T> left, Node<T> right) {
  30.             super();
  31.             this.value = value;
  32.             this.left = left;
  33.             this.right = right;
  34.         }
  35.  
  36.         public Node<T> left() {
  37.             return left;
  38.         }
  39.  
  40.         public Node<T> right() {
  41.             return right;
  42.         }
  43.  
  44.         @Override
  45.         public String toString() {
  46.             return String.valueOf(value);
  47.         }
  48.     }
  49.  
  50.     public static final <N> void traverse(Node<N> root) {
  51.  
  52.         final TreeMap<Integer, List<Node<N>>> columnMap = new TreeMap<>();
  53.         final Queue<ColumnFind<N>> queue = new LinkedList<>();
  54.  
  55.         queueChild(0, root, queue);
  56.  
  57.         while (!queue.isEmpty()) {
  58.             ColumnFind<N> cf = queue.remove();
  59.             int column = cf.column;
  60.             Node<N> node = cf.node;
  61.             columnMap.computeIfAbsent(column, c -> new ArrayList<>()).add(node);
  62.             queueChild(column - 1, node.left(), queue);
  63.             queueChild(column + 1, node.right(), queue);
  64.         }
  65.  
  66.         for (Entry<Integer, List<Node<N>>> entry: columnMap.entrySet()) {
  67.             System.out.println("Column - " + entry.getKey() + " : " + entry.getValue());
  68.         }
  69.     }
  70.  
  71.     private static final <N> void queueChild(int column, Node<N> node, Queue<ColumnFind<N>> queue) {
  72.         if (node == null) {
  73.             return;
  74.         }
  75.         queue.add(new ColumnFind<>(column, node));
  76.     }
  77.  
  78.  
  79.     public static void main(String[] args) {
  80.         Node<Integer> five = new Node<>(5, null, null);
  81.         Node<Integer> four = new Node<>(4, null, five);
  82.         Node<Integer> three = new Node<>(3, null, null);
  83.         Node<Integer> two = new Node<>(2, null, four);
  84.         Node<Integer> one = new Node<>(1, two, three);
  85.         traverse(one);
  86.     }
  87.  
  88. }
  89.  
Success #stdin #stdout 0.17s 320448KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Column - -1 : [2]
Column - 0 : [1, 4]
Column - 1 : [3, 5]
https://ideone.com/p8RWmE
language:
Java (HotSpot 12)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!