Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit9ee8039

Browse files
authored
Merge pull requestTheAlgorithms#725 from RicardoGuevara/Development
Add binary tree implementation with test
2 parentse5b07eb +4721cff commit9ee8039

File tree

2 files changed

+185
-0
lines changed

2 files changed

+185
-0
lines changed
Lines changed: 125 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,125 @@
1+
packagesrc.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+
publicclassBinaryTree<TextendsComparable> {
9+
privatefinalTdata;
10+
privateBinaryTreeright,// the upper binary tree
11+
left;// the lower binary tree
12+
13+
publicBinaryTree(Tdata) {
14+
this.data =data;
15+
}
16+
17+
@Override
18+
publicStringtoString(){
19+
returnthis.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+
publicvoidinsert(TnewDataValue){
27+
this.insert(newBinaryTree(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+
publicvoidinsert(BinaryTreenewData){
35+
36+
intcpr =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+
elseif (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+
publicBinaryTreesearch(Tdata){
58+
intcpr =data.compareTo(this.data);//new value comparission respect to actual value
59+
60+
if (cpr <0) {
61+
if (this.left ==null)
62+
returnnull;//the value doesn't exist
63+
returnthis.left.search(data);
64+
}
65+
if (cpr >0) {
66+
if (this.right ==null)
67+
returnnull;//the value doesn't exist
68+
returnthis.right.search(data);
69+
}
70+
returnthis;
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+
publicbooleancontains(Tdata){
79+
returnthis.search(data) !=null;
80+
}
81+
82+
/**
83+
* uses recursive black magic to print this tree in console
84+
* @param tabCounter prev tabs
85+
*/
86+
privatevoidprint(inttabCounter){
87+
for (inti =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+
publicvoidprint(){
102+
this.print(0);
103+
}
104+
105+
//getters and setters
106+
publicTgetData() {
107+
returndata;
108+
}
109+
110+
publicBinaryTreegetRight() {
111+
returnright;
112+
}
113+
114+
publicvoidsetRight(BinaryTreeright) {
115+
this.right =right;
116+
}
117+
118+
publicBinaryTreegetLeft() {
119+
returnleft;
120+
}
121+
122+
publicvoidsetLeft(BinaryTreeleft) {
123+
this.left =left;
124+
}
125+
}
Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
packagesrc.main.java.com.dataStructures;
2+
3+
importorg.junit.Test;
4+
importstaticorg.junit.Assert.*;
5+
6+
/**
7+
*
8+
* @author RICARDO
9+
*/
10+
publicclassBinaryTreeTest {
11+
12+
publicBinaryTreeTest() {
13+
}
14+
15+
/**
16+
* Test of insert method, of class BinaryTree.
17+
*/
18+
@Test
19+
publicvoidtestInsert_BinaryTree() {
20+
System.out.println("insert");
21+
BinaryTree<String>lowerdata =newBinaryTree<>("1");
22+
BinaryTree<String>upperdata =newBinaryTree<>("3");
23+
BinaryTree<String>instance =newBinaryTree<>("2");
24+
instance.insert(lowerdata);
25+
instance.insert(upperdata);
26+
Stringproof =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+
publicvoidtestSearch() {
36+
System.out.println("search");
37+
BinaryTree<Integer>instance =newBinaryTree<>(5);
38+
for (inti =1;i <10;i++) {
39+
instance.insert(newInteger(i));
40+
}
41+
BinaryTreeresult =instance.search(newInteger(1));
42+
assertEquals(newInteger(1),result.getData());
43+
}
44+
45+
/**
46+
* Test of contains method, of class BinaryTree.
47+
*/
48+
@Test
49+
publicvoidtestContains() {
50+
System.out.println("contains");
51+
BinaryTree<Integer>instance =newBinaryTree<>(5);
52+
for (inti =1;i <10;i++) {
53+
instance.insert(i);
54+
}
55+
56+
booleanresult =instance.contains(2)&&instance.contains(11);
57+
assertEquals(false,result);
58+
}
59+
60+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp