Add files via upload

ParitoshAggarwal · web-flow · commit c993087737f1 · 2017-08-06T20:32:48.000+05:30
Generic tree updated
diff --git a/data_structures/Trees/GenericTree.Java b/data_structures/Trees/GenericTree.Java
@@ -0,0 +1,226 @@
+import java.util.ArrayList;
+import java.util.LinkedList;
+import java.util.Scanner;
+
+public class treeclass {
+	private class Node {
+		int data;
+		ArrayList<Node> child = new ArrayList<>();
+	}
+
+	private Node root;
+	private int size;
+
+	/*
+	A generic tree is a tree which can have as many children as it can be
+	It might be possible that every node present is directly connected to
+	root node.
+
+	In this code
+	Every function has two copies: one function is helper function which can be called from
+	main and from that function a private function is called which will do the actual work.
+	I have done this, while calling from main one have to give minimum parameters.
+
+	*/
+	public treeclass() {     //Constructor
+		Scanner scn = new Scanner(System.in);
+		root = create_treeG(null, 0, scn);
+	}
+
+	private Node create_treeG(Node node, int childindx, Scanner scn) {
+		// display
+		if (node == null) {
+			System.out.println("Enter root's data");
+		} else {
+			System.out.println("Enter data of parent of index " + node.data + " " + childindx);
+		}
+		// input
+		node = new Node();
+		node.data = scn.nextInt();
+		System.out.println("number of children");
+		int number = scn.nextInt();
+		for (int i = 0; i < number; i++) {
+			Node childd = create_treeG(node, i, scn);
+			size++;
+			node.child.add(childd);
+		}
+		return node;
+	}
+
+	/*
+	Function to display the generic tree
+	*/
+	public void display() {  //Helper function
+		display_1(root);
+		return;
+	}
+
+	private void display_1(Node parent) {
+		System.out.print(parent.data + "=>");
+		for (int i = 0; i < parent.child.size(); i++) {
+			System.out.print(parent.child.get(i).data + " ");
+		}
+		System.out.println(".");
+		for (int i = 0; i < parent.child.size(); i++) {
+			display_1(parent.child.get(i));
+		}
+		return;
+	}
+
+	/*
+	 One call store the size directly but if you are asked compute size this function to calcuate
+	 size goes as follows
+	 */
+
+	public int size2call() {
+		return size2(root);
+	}
+
+	public int size2(Node roott) {
+		int sz = 0;
+		for (int i = 0; i < roott.child.size(); i++) {
+			sz += size2(roott.child.get(i));
+		}
+		return sz + 1;
+	}
+
+	/*
+	Function to compute maximum value in the generic tree
+	*/
+	public int maxcall() {
+		int maxi = root.data;
+		return max(root, maxi);
+	}
+
+	private int max(Node roott, int maxi) {
+		if (maxi < roott.data)
+			maxi = roott.data;
+		for (int i = 0; i < roott.child.size(); i++) {
+			maxi = max(roott.child.get(i), maxi);
+		}
+
+		return maxi;
+	}
+
+	/*
+	Function to compute HEIGHT of the generic tree
+	*/
+
+	public int heightcall() {
+		return height(root) - 1;
+	}
+
+	private int height(Node node) {
+		int h = 0;
+		for (int i = 0; i < node.child.size(); i++) {
+			int k = height(node.child.get(i));
+			if (k > h)
+				h = k;
+		}
+		return h + 1;
+	}
+
+	/*
+	Function to find whether a number is present in the generic tree or not
+	*/
+
+	public boolean findcall(int info) {
+		return find(root, info);
+	}
+
+	private boolean find(Node node, int info) {
+		if (node.data == info)
+			return true;
+		for (int i = 0; i < node.child.size(); i++) {
+			if (find(node.child.get(i), info))
+				return true;
+		}
+		return false;
+	}
+
+	/*
+	Function to calculate depth of generic tree
+	*/
+	public void depthcaller(int dep) {
+		depth(root, dep);
+	}
+
+	public void depth(Node node, int dep) {
+		if (dep == 0) {
+			System.out.println(node.data);
+			return;
+		}
+		for (int i = 0; i < node.child.size(); i++)
+			depth(node.child.get(i), dep - 1);
+		return;
+	}
+
+	/*
+	Function to print generic tree in pre-order
+	*/
+	public void preordercall() {
+		preorder(root);
+		System.out.println(".");
+	}
+
+	private void preorder(Node node) {
+		System.out.print(node.data + " ");
+		for (int i = 0; i < node.child.size(); i++)
+			preorder(node.child.get(i));
+	}
+
+	/*
+	Function to print generic tree in post-order
+	*/
+	public void postordercall() {
+		postorder(root);
+		System.out.println(".");
+	}
+
+	private void postorder(Node node) {
+		for (int i = 0; i < node.child.size(); i++)
+			postorder(node.child.get(i));
+		System.out.print(node.data + " ");
+	}
+
+	/*
+	Function to print generic tree in level-order
+	*/
+
+	public void levelorder() {
+		LinkedList<Node> q = new LinkedList<>();
+		q.addLast(root);
+		while (!q.isEmpty()) {
+			int k = q.getFirst().data;
+			System.out.print(k + " ");
+
+			for (int i = 0; i < q.getFirst().child.size(); i++) {
+				q.addLast(q.getFirst().child.get(i));
+			}
+			q.removeFirst();
+		}
+		System.out.println(".");
+	}
+
+	/*
+	 Function to remove all leaves of generic tree
+	 */
+	public void removeleavescall() {
+		removeleaves(root);
+	}
+
+	private void removeleaves(Node node) {
+		ArrayList<Integer> arr = new ArrayList<>();
+		for (int i = 0; i < node.child.size(); i++) {
+			if (node.child.get(i).child.size() == 0) {
+				arr.add(i);
+				// node.child.remove(i);
+				// i--;
+			} else
+				removeleaves(node.child.get(i));
+		}
+		for (int i = arr.size() - 1; i >= 0; i--) {
+			node.child.remove(arr.get(i) + 0);
+		}
+	}
+
