forked from TheAlgorithms/Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathGenericTree.java
More file actions
234 lines (206 loc) · 5.97 KB
/
GenericTree.java
File metadata and controls
234 lines (206 loc) · 5.97 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
package DataStructures.Trees;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;
/**
* 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.
* <p>
* 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 class GenericTree {
private class Node {
int data;
ArrayList<Node> child = new ArrayList<>();
}
private Node root;
private int size;
public GenericTree() { //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 child = create_treeG(node, i, scn);
size++;
node.child.add(child);
}
return node;
}
/**
* Function to display the generic tree
*/
public void display() { //Helper function
display_1(root);
}
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));
}
}
/**
* One call store the size directly but if you are asked compute size this function to calculate
* size goes as follows
*
* @return size
*/
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
*
* @return maximum value
*/
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
*
* @return height
*/
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
*
* @param info number
* @return present 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
*
* @param dep depth
*/
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 +
57C9
" ");
}
/**
* 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);
}
}
}