data-structures-java/BinaryTree.java at main · MartinCastroAlvarez/data-structures-java · GitHub

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
importjava.util.ArrayList;
importjava.util.InputMismatchException;
importjava.util.Scanner;

// ------------------------------------------------------------------------------
// A Binary Tree data structure containing just a root integer, a left
// and a right leaf branches and a counter of the amount of times the
// root integer has been added to the Tree.
// The left and the right branches are implemented using recursion.
// ------------------------------------------------------------------------------
classBinaryTree {

privateintweight = 0;
privateintroot = 0;
privateBinaryTreeleft;
privateBinaryTreeright;

// ------------------------------------------------------------------------------
// Returns True if the BinaryTree is empty.
//
// That happens when the weight of the BinaryTree is 0, since the weight is
// incremented every time the root value is added to the list.
// ------------------------------------------------------------------------------
publicbooleanisEmpty() {
if (this.weight == 0) {
returntrue;
 }
returnfalse;
 }

// ------------------------------------------------------------------------------
// Returns True if this Node has a left node.
// ------------------------------------------------------------------------------
publicbooleanhasLeft() {
if (this.left != null) {
returntrue;
 }
returnfalse;
 }

// ------------------------------------------------------------------------------
// Returns True if this Node has a right node.
// ------------------------------------------------------------------------------
publicbooleanhasRight() {
if (this.right != null) {
returntrue;
 }
returnfalse;
 }

// ------------------------------------------------------------------------------
// Method for adding a value to the BinaryTree.
//
// If the root value is currently null, then the root
// value will be updated.
//
// If the new value is less than than the root value,
// then a left BinaryTree is updated/created.
//
// If the new value is larger than than the root value,
// then a right BinaryTree is updated/created.
// ------------------------------------------------------------------------------
publicvoidadd(intnumber) {
if (this.isEmpty()) {
this.root = number;
this.weight++;
 } elseif (number < this.root) {
if (!this.hasLeft()) {
this.left = newBinaryTree();
 }
this.left.add(number);
 } else {
if (!this.hasRight()) {
this.right = newBinaryTree();
 }
this.right.add(number);
 }
 }

// ------------------------------------------------------------------------------
// Method responsible for iterating over the sorted values in the BinaryTree.
// ------------------------------------------------------------------------------
publicArrayList<Integer> toList() {
ArrayList<Integer> numbers = newArrayList<Integer>();
if (this.hasLeft()) {
numbers.addAll(this.left.toList());
 }
for (inti = 0; i < this.weight; i++) {
numbers.add(this.root);
 }
if (this.hasRight()) {
numbers.addAll(this.right.toList());
 }
returnnumbers;
 }

// ------------------------------------------------------------------------------
// Main method.
//
// This just accepts integers from the STDIN and adds them to the BinaryTree
// instance.
//
// Once the loop is broken, the BinaryTree is printed to STDOUT.
// The output is a sorted list of integers in ascending mode.
// ------------------------------------------------------------------------------
publicstaticvoidmain(String [] args) {

// Declaring variables.
Scannerscanner;
BinaryTreetree;
intnumber;

// Initializing variables.
scanner = newScanner(System.in);
tree = newBinaryTree();

// Reading integers from STDIN until the User introudces
// an invalid value that can not be casted to integer.
try {
while (true) {
System.out.println("Insert a number or 'exit' to quit: ");
System.out.print(">>> ");
number = scanner.nextInt();
System.out.println("Added: " + number);
tree.add(number);
 }
 } catch (java.util.InputMismatchExceptionerror) {}

// Printing the results to STDOUT.
System.out.println("Sorted values:");
ArrayList<Integer> numbers = tree.toList();
for (inti = 0; i < numbers.size(); i++) {
System.out.print(numbers.get(i) + " ");
 }
	}
}