Java/DataStructures/Trees/GenericTree.java at master · comelf/Java · GitHub

History

234 lines (206 loc) · 5.97 KB

Raw

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 + " ");

}

/**

* 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);

}

Java/DataStructures/Trees/GenericTree.java at master · comelf/Java · GitHub

Expand file tree

Breadcrumbs

GenericTree.java

Latest commit

History

Breadcrumbs

GenericTree.java

File metadata and controls