Skip to content

Commit 9ee8039

Browse files
yanglbmeyanglbme
authored
Merge pull request TheAlgorithms#725 from RicardoGuevara/Development
Add binary tree implementation with test
2 parents e5b07eb + 4721cff commit 9ee8039

File tree

2 files changed

+185
-0
lines changed

2 files changed

+185
-0
lines changed

‎src/main/java/com/dataStructures/BinaryTree.java

Lines changed: 125 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,125 @@
1+
package src.main.java.com.dataStructures;
2+
3+
/**
4+
* Binary tree for general value type, without redundancy
5+
* @author RICARDO
6+
* @param <T> root data
7+
*/
8+
public class BinaryTree<T extends Comparable> {
9+
private final T data;
10+
private BinaryTree right, // the upper binary tree
11+
left; // the lower binary tree
12+
13+
public BinaryTree(T data) {
14+
this.data = data;
15+
}
16+
17+
@Override
18+
public String toString(){
19+
return this.data.toString();
20+
}
21+
22+
/**
23+
* inserts a new value in it's correspondant place
24+
* @param newDataValue value of the new banary tree to add on this tree
25+
*/
26+
public void insert(T newDataValue){
27+
this.insert(new BinaryTree(newDataValue));
28+
}
29+
30+
/**
31+
* inserts a new binary tree in it's correspondant place
32+
* @param newData new value to add on this tree
33+
*/
34+
public void insert(BinaryTree newData){
35+
36+
int cpr = newData.data.compareTo(this.data); //new value comparission respect to actual value
37+
38+
if (cpr < 0)
39+
if (this.left == null)
40+
this.setLeft(newData);
41+
else
42+
this.left.insert(newData);
43+
else if (cpr > 0)
44+
if (this.right == null)
45+
this.setRight(newData);
46+
else
47+
this.right.insert(newData);
48+
else
49+
System.out.println("Redundant value, not added");
50+
}
51+
52+
/**
53+
* search and specific value on the tree
54+
* @param data Searched value
55+
* @return Binary tree wich contains the value, null if it doesn't exist
56+
*/
57+
public BinaryTree search(T data){
58+
int cpr = data.compareTo(this.data); //new value comparission respect to actual value
59+
60+
if (cpr < 0) {
61+
if (this.left == null)
62+
return null; //the value doesn't exist
63+
return this.left.search(data);
64+
}
65+
if (cpr > 0) {
66+
if (this.right == null)
67+
return null; //the value doesn't exist
68+
return this.right.search(data);
69+
}
70+
return this;
71+
}
72+
73+
/**
74+
* Checks if the data value exist in the tree
75+
* @param data data to be searched
76+
* @return true if this tree contains the data value, false if not.
77+
*/
78+
public boolean contains(T data){
79+
return this.search(data) != null;
80+
}
81+
82+
/**
83+
* uses recursive black magic to print this tree in console
84+
* @param tabCounter prev tabs
85+
*/
86+
private void print(int tabCounter){
87+
for (int i = 0; i < tabCounter; i++)
88+
System.out.print("\t");
89+
90+
System.out.println(this);
91+
92+
if (this.left != null)
93+
this.left.print(tabCounter + 1); //it can't be ++ , pls don't change it
94+
if (this.right != null)
95+
this.right.print(tabCounter + 1); //it can't be ++ , pls don't change it
96+
}
97+
98+
/**
99+
* uses black magic to print this tree in console
100+
*/
101+
public void print(){
102+
this.print(0);
103+
}
104+
105+
//getters and setters
106+
public T getData() {
107+
return data;
108+
}
109+
110+
public BinaryTree getRight() {
111+
return right;
112+
}
113+
114+
public void setRight(BinaryTree right) {
115+
this.right = right;
116+
}
117+
118+
public BinaryTree getLeft() {
119+
return left;
120+
}
121+
122+
public void setLeft(BinaryTree left) {
123+
this.left = left;
124+
}
125+
}

‎src/test/java/com/dataStructures/BinaryTreeTest.java

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
package src.main.java.com.dataStructures;
2+
3+
import org.junit.Test;
4+
import static org.junit.Assert.*;
5+
6+
/**
7+
*
8+
* @author RICARDO
9+
*/
10+
public class BinaryTreeTest {
11+
12+
public BinaryTreeTest() {
13+
}
14+
15+
/**
16+
* Test of insert method, of class BinaryTree.
17+
*/
18+
@Test
19+
public void testInsert_BinaryTree() {
20+
System.out.println("insert");
21+
BinaryTree<String> lowerdata = new BinaryTree<>("1");
22+
BinaryTree<String> upperdata = new BinaryTree<>("3");
23+
BinaryTree<String> instance = new BinaryTree<>("2");
24+
instance.insert(lowerdata);
25+
instance.insert(upperdata);
26+
String proof = instance.getLeft().toString()+instance.toString()+instance.getRight().toString();
27+
System.out.println(proof);
28+
assertEquals("123", proof);
29+
}
30+
31+
/**
32+
* Test of search method, of class BinaryTree.
33+
*/
34+
@Test
35+
public void testSearch() {
36+
System.out.println("search");
37+
BinaryTree<Integer> instance = new BinaryTree<>(5);
38+
for (int i = 1; i < 10; i++) {
39+
instance.insert(new Integer(i));
40+
}
41+
BinaryTree result = instance.search(new Integer(1));
42+
assertEquals(new Integer(1), result.getData());
43+
}
44+
45+
/**
46+
* Test of contains method, of class BinaryTree.
47+
*/
48+
@Test
49+
public void testContains() {
50+
System.out.println("contains");
51+
BinaryTree<Integer> instance = new BinaryTree<>(5);
52+
for (int i = 1; i < 10; i++) {
53+
instance.insert(i);
54+
}
55+
56+
boolean result = instance.contains(2)&&instance.contains(11);
57+
assertEquals(false, result);
58+
}
59+
60+
}

0 commit comments

Comments
 (0)