fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10. 	static public class Queue{
  11. 	public class QueueNode {
  12. 		Object key;
  13. 		QueueNode next;
  14.  
  15. 		QueueNode (Object K) {
  16. 			key = K;
  17. 			next = null;
  18. 		}
  19.  
  20. 		public QueueNode getNext () {
  21. 			return next;
  22. 		}
  23.  
  24. 		public Object getKey () {
  25. 			return key;
  26. 		}
  27. 	}
  28.  
  29. 	protected QueueNode front;
  30. 	QueueNode rear;
  31. 	int size;
  32. 	String name;
  33.  
  34. 	public Queue (String name) {
  35. 		front = null;
  36. 		rear = null;
  37. 		size = 0;
  38. 		this.name = name;
  39. 	}
  40.  
  41. 	public Queue () {
  42. 		front = null;
  43. 		rear = null;
  44. 		size = 0;
  45. 	}
  46.  
  47. 	public void enqueue (Object O) {
  48. 		QueueNode node = new QueueNode(O);
  49. 		if (isEmpty ()) {
  50. 			front = rear = node;
  51. 		}
  52. 		else {
  53. 			rear.next = node;
  54. 			rear = node;
  55. 		}
  56. 		size++;
  57. 	}
  58.  
  59. 	public Object dequeue () {
  60. 		Object node = null;
  61. 		if (isEmpty ()) {
  62. 			return null;
  63. 		}
  64. 		node = front.key;
  65. 		front = front.next;
  66. 		if (front == null)
  67. 			rear = null;
  68. 		size--;
  69. 		return node;
  70. 	}
  71.  
  72. 	public boolean isEmpty () {
  73. 		if (front == null) {
  74. 			return true;
  75. 		}
  76. 		return false;
  77. 	}
  78. 	}
  79. 	static class NaryTreeNode {
  80. 		char key;
  81. 		List<NaryTreeNode> childs;
  82. 		NaryTreeNode (char k) {
  83. 			this.key = k;
  84. 		}
  85. 	}
  86. 	NaryTreeNode root = null;
  87.  
  88. 	void add (char k, String childs) throws InterruptedException {
  89.  
  90. 		NaryTreeNode node = getNode (k);
  91. 		if (node == null) {
  92. 			node = new NaryTreeNode (k);
  93. 			node.key = k;
  94. 		}
  95.  
  96. 		node.childs = new ArrayList<NaryTreeNode> ();
  97.  
  98. 		for (int i = 0; i < childs.length(); i++) {
  99. 			node.childs.add(new NaryTreeNode(childs.charAt(i)));
  100. 		}
  101.  
  102. 		if (root == null) {
  103. 			root = node;
  104. 		}
  105. 	}
  106.  
  107. 	private NaryTreeNode getNode(char k) throws InterruptedException {
  108. 		Queue q = new Queue ();
  109. 		q.enqueue(root);
  110.  
  111. 		while (!q.isEmpty()) {
  112. 			NaryTreeNode node = (NaryTreeNode) q.dequeue();
  113.  
  114. 			Queue q2 = new Queue ();
  115. 			while (node != null) {
  116. 				if (node.key == k) {
  117. 					return node;
  118. 				}
  119. 				if (node.childs != null) {
  120. 					List<NaryTreeNode> childs = node.childs;
  121. 					Iterator<NaryTreeNode> iter = childs.iterator();
  122. 					while (iter.hasNext()) {
  123. 						NaryTreeNode child = iter.next();
  124. 						q2.enqueue(child);
  125. 					}
  126. 				}
  127. 				node = (NaryTreeNode) q.dequeue();
  128. 			}
  129. 			q = q2;
  130. 		}
  131. 		return null;
  132. 	}
  133.  
  134. 	private NaryTreeNode levelorder() throws InterruptedException {
  135. 		Queue q = new Queue ();
  136. 		q.enqueue(root);
  137.  
  138. 		while (!q.isEmpty()) {
  139. 			NaryTreeNode node = (NaryTreeNode) q.dequeue();
  140. 			System.out.println();
  141. 			Queue q2 = new Queue ();
  142. 			while (node != null) {
  143. 				System.out.print(node.key + ", ");
  144. 				if (node.childs != null) {
  145. 					List<NaryTreeNode> childs = node.childs;
  146. 					Iterator<NaryTreeNode> iter = childs.iterator();
  147. 					while (iter.hasNext()) {
  148. 						NaryTreeNode child = iter.next();
  149. 						q2.enqueue(child);
  150. 					}
  151. 				}
  152. 				node = (NaryTreeNode) q.dequeue();
  153. 			}
  154. 			q = q2;
  155. 		}
  156. 		return null;
  157. 	}
  158.  
  159. 	String serialize () throws InterruptedException {
  160. 		Queue q = new Queue ();
  161. 		q.enqueue(root);
  162. 		StringBuilder sb = new StringBuilder ();
  163.  
  164. 		while (!q.isEmpty()) {
  165. 			NaryTreeNode node = (NaryTreeNode) q.dequeue();
  166. 			System.out.println();
  167. 			Queue q2 = new Queue ();
  168.  
  169. 			while (node != null) {
  170. 				if (node.childs != null) {
  171. 					sb.append( node.key );
  172. 					sb.append (":");
  173. 					List<NaryTreeNode> childs = node.childs;
  174. 					Iterator<NaryTreeNode> iter = childs.iterator();
  175. 					while (iter.hasNext()) {
  176. 						NaryTreeNode child = iter.next();
  177. 						q2.enqueue(child);
  178. 						sb.append(child.key);
  179. 					}
  180. 					sb.append (",");
  181. 				}
  182. 				node = (NaryTreeNode) q.dequeue();
  183. 			}
  184. 			q = q2;
  185. 		}
  186.  
  187. 		if (sb.length() == 0) {
  188. 			sb.append(root.key);
  189. 		}
  190. 		return sb.toString();
  191. 	}
  192.  
  193. 	public static void main(String[] args) throws InterruptedException {
  194. 		testcase_1 ();
  195. 		// testcase_2 ();
  196. 	}
  197.  
  198. 	private static void testcase_2 () throws InterruptedException {
  199. 		Ideone tree = new Ideone ();
  200. 		String nodes = "A";
  201. 		tree.add('A', "");
  202. 		tree.levelorder();
  203. 		tree.parents ("A");
  204. 		String serializedTree = tree.serialize();
  205. 		System.out.println("Serialized String: " + serializedTree);
  206.  
  207. 		System.out.println("\nAfter Deserilization:");
  208. 		tree.deserialize (serializedTree, nodes);
  209. 	}
  210.  
  211. 	private static void testcase_1 () throws InterruptedException {
  212. 		Ideone tree = new Ideone ();
  213. 		tree.add('A', "BCD");
  214. 		tree.add('B', "EF");
  215. 		tree.add('D', "GHIJ");
  216. 		tree.levelorder();
  217.  
  218. 		String nodes = "ABCDEFGHIJ";
  219. 		tree.parents (nodes);
  220. 		String serializedTree = tree.serialize();
  221. 		System.out.println("Serialized String: " + serializedTree);
  222. 		tree.deserialize (serializedTree, nodes);	
  223. 	}
  224.  
  225. 	private void deserialize(String serializedTree, String nodes) throws InterruptedException {
  226. 		Ideone tree = new Ideone ();
  227. 		int index = 0;
  228. 		while (index < serializedTree.length()) {
  229. 			char root = serializedTree.charAt(index);
  230. 			index++;// passing root
  231. 			index++; //skipping :
  232. 			String childs = serializedTree.substring (index, serializedTree.indexOf(',', index));
  233. 			index += childs.length();
  234. 			index++; //skipping ,
  235. 			System.out.println("root:" + root + ", childs: " + childs);
  236. 			tree.add(root, childs);
  237. 		}
  238. 		tree.levelorder();
  239. 		tree.parents (nodes);	
  240. 	}
  241.  
  242. 	private void parents (String nodes) throws InterruptedException {
  243. 		System.out.println();
  244. 		for (int i = 0; i < nodes.length(); i++) {
  245. 			char key = nodes.charAt(i);
  246. 			System.out.println("Parent of " + key + " : " + parent (key));			
  247. 		}
  248. 	}
  249.  
  250. 	private char parent(char k) throws InterruptedException {
  251. 		Queue q = new Queue ();
  252. 		q.enqueue(root);
  253.  
  254. 		while (!q.isEmpty()) {
  255. 			NaryTreeNode node = (NaryTreeNode) q.dequeue();
  256.  
  257. 			Queue q2 = new Queue ();
  258. 			while (node != null) {
  259.  
  260. 				if (node.childs != null) {
  261. 					List<NaryTreeNode> childs = node.childs;
  262. 					Iterator<NaryTreeNode> iter = childs.iterator();
  263. 					while (iter.hasNext()) {
  264. 						NaryTreeNode child = iter.next();
  265. 						if (child.key == k) {
  266. 							return node.key;
  267. 						}
  268. 						q2.enqueue(child);
  269. 					}
  270. 				}
  271. 				node = (NaryTreeNode) q.dequeue();
  272. 			}
  273. 			q = q2;
  274. 		}
  275. 		return (char) -1;
  276. 	}
  277. }
Success #stdin #stdout 0.07s 380224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
A, 
B, C, D, 
E, F, G, H, I, J, 
Parent of A : ￿
Parent of B : A
Parent of C : A
Parent of D : A
Parent of E : B
Parent of F : B
Parent of G : D
Parent of H : D
Parent of I : D
Parent of J : D



Serialized String: A:BCD,B:EF,D:GHIJ,
root:A, childs: BCD
root:B, childs: EF
root:D, childs: GHIJ

A, 
B, C, D, 
E, F, G, H, I, J, 
Parent of A : ￿
Parent of B : A
Parent of C : A
Parent of D : A
Parent of E : B
Parent of F : B
Parent of G : D
Parent of H : D
Parent of I : D
Parent of J : D
https://ideone.com/TO4dEs
language:
Java (HotSpot 12)
created:
9 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!