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

Commitaf6daf7

Browse files
authored
Merge pull requestTheAlgorithms#737 from abircb/Development
Added DepthFirstSearch.java and DepthFirstTestSearch.java
2 parentsada660a +fa1503f commitaf6daf7

File tree

2 files changed

+159
-0
lines changed

2 files changed

+159
-0
lines changed
Lines changed: 123 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,123 @@
1+
packagesrc.main.java.com.search;
2+
3+
/**
4+
* Searching is faster in sorted structures. Binary search is O(log n).
5+
* However, the cost of sorting is O(n · log n).
6+
* What to do when adding or removing elements? Sort again? No.
7+
* Create efficient data structures to maintain sorted sequences, and search in them
8+
* Key example: binary sorted tree, allowing O(log N) insert, remove and lookup.
9+
10+
In comes, depth-first search
11+
* Worst-case performanceO(n)
12+
* Best-case performanceO(1)
13+
* Average performance O(n)
14+
*
15+
*/
16+
17+
publicclassDepthFirstSearch {
18+
19+
/**
20+
* Depth-first search method
21+
*
22+
* @param tree- Binary tree to be searched
23+
* @param value- Key being searched for
24+
* @return Location of the key
25+
*/
26+
27+
publicstatic <TextendsComparable<T>>Tfind(Tkey,BinaryTree<T>tree) {
28+
returntree.get(key);
29+
}
30+
31+
}
32+
33+
/**
34+
* The BinaryTree class defines the structure of a binary tree
35+
* Also contains a static nested class called TreeNode
36+
* @param <T>
37+
*/
38+
classBinaryTree<TextendsComparable<T>> {
39+
40+
privateTreeNode<T>root;
41+
42+
/**
43+
* @param <P>
44+
* This class defines what a node in a binary tree looks like
45+
*/
46+
privatestaticclassTreeNode<PextendsComparable<P>> {
47+
48+
Pkey,value;
49+
TreeNode<P>left,right;
50+
51+
privateTreeNode(Pkey,Pvalue) {
52+
this.key =key;
53+
this.value =value;
54+
this.left =null;
55+
this.right =null;
56+
}
57+
58+
/**
59+
* @param node
60+
* adds the specified node
61+
*/
62+
privatevoidadd(TreeNode<P>node) {
63+
if (node.key.compareTo(this.key) <0) {
64+
if(this.left ==null) {
65+
this.left =node;
66+
}
67+
else {
68+
this.left.add(node);
69+
}
70+
}
71+
72+
else {
73+
if(this.right ==null) {
74+
this.right =node;
75+
}
76+
else {
77+
this.right.add(node);
78+
}
79+
}
80+
}
81+
82+
/**
83+
* @param key
84+
* @return the tree node corresponding to the key
85+
*/
86+
privateTreeNode<P>find(Pkey) {
87+
if (key.compareTo(this.key) ==0)returnthis;
88+
89+
elseif(key.compareTo(this.key) <0) {
90+
if (this.left ==null)returnnull;
91+
elsereturnthis.left.find(key);
92+
}
93+
94+
else {
95+
if(this.right ==null)returnnull;
96+
elsereturnthis.right.find(key);
97+
}
98+
}
99+
100+
}
101+
102+
publicBinaryTree() {
103+
this.root =null;
104+
}
105+
106+
publicvoidadd(Tkey,Tvalue) {
107+
TreeNode<T>node =newTreeNode<T>(key,value);
108+
if(this.root ==null) {
109+
this.root =node;
110+
}
111+
else {
112+
this.root.add(node);
113+
}
114+
}
115+
116+
publicTget(Tkey) {
117+
if(this.root ==null)returnnull;
118+
119+
TreeNode<T>node =this.root.find(key);
120+
if(node ==null)returnnull;
121+
returnnode.value;
122+
}
123+
}
Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
packagesrc.test.java.com.search;
2+
3+
importorg.junit.Assert;
4+
importorg.junit.Test;
5+
importsrc.main.java.com.search.DepthFirstSearch;
6+
importsrc.main.java.com.search.BinaryTree;
7+
8+
publicclassDepthFirstSearchTest {
9+
@Test
10+
publicvoidtestDepthFirstSearch() {
11+
12+
BinaryTree<Integer>tree1 =newBinaryTree<Integer>();
13+
tree1.add(1,1);
14+
tree1.add(2,2);
15+
tree1.add(3,3);
16+
tree1.add(4,4);
17+
Assert.assertEquals("Incorrect index",3,DepthFirstSearch.find(3,tree1));
18+
Assert.assertEquals("Incorrect index",1,DepthFirstSearch.find(1,tree1));
19+
Assert.assertEquals("Incorrect index",null,DepthFirstSearch.find(0,tree1));
20+
Assert.assertEquals("Incorrect index",null,DepthFirstSearch.find(8,tree1));
21+
Assert.assertEquals("Incorrect index",null,DepthFirstSearch.find(-2,tree1));
22+
23+
BinaryTree<String>tree2 =newBinaryTree<String>();
24+
tree2.add("1","A");
25+
tree2.add("2","B");
26+
tree2.add("3","C");
27+
tree2.add("4","D");
28+
29+
Assert.assertEquals("Incorrect index","C",LinearSearch.findIndex(tree2,"3"));
30+
Assert.assertEquals("Incorrect index","B",LinearSearch.findIndex(tree2,"2"));
31+
Assert.assertEquals("Incorrect index",null,LinearSearch.findIndex(tree2,"F"));
32+
33+
BinaryTree<String>tree3 =newBinaryTree<String>();
34+
Assert.assertEquals("Incorrect index",null,LinearSearch.findIndex(tree3,""));
35+
}
36+
}

0 commit comments

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