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

Commitfc06690

Browse files
authored
fixes:TheAlgorithms#1280 and test: added tests for DFS algorithm (TheAlgorithms#1303)
* fix: fixed error in DepthFirstSearch algorithm and test: added tests for DepthFirstSearch algorithm.* changed traverseDFS function parameters in DepthFirstSearch.js file
1 parent566d910 commitfc06690

File tree

2 files changed

+62
-19
lines changed

2 files changed

+62
-19
lines changed

‎Trees/DepthFirstSearch.js

Lines changed: 16 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -4,35 +4,32 @@
44
* DFS Algorithm for traversing or searching graph data structures.
55
*/
66

7-
functiontraverseDFS(root){
8-
conststack=[root]
7+
// traverses a give tree from specified root's value
8+
functiontraverseDFS(tree,rootValue){
9+
conststack=[]
910
constres=[]
10-
11+
stack.push(searchDFS(tree,rootValue))
12+
// if root is not present in the tree, returning empty array
13+
if(!stack[0])returnres
1114
while(stack.length){
1215
constcurr=stack.pop()
13-
res.push(curr.key)
14-
15-
if(curr.right){
16-
stack.push(curr.right)
17-
}
18-
16+
res.push(curr.value)
1917
if(curr.left){
20-
stack.push(curr.left)
18+
stack.push(tree[curr.left])
19+
}
20+
if(curr.right){
21+
stack.push(tree[curr.right])
2122
}
2223
}
23-
2424
returnres.reverse()
2525
}
2626

2727
functionsearchDFS(tree,value){
2828
conststack=[]
29-
3029
stack.push(tree[0])
31-
3230
while(stack.length!==0){
3331
for(leti=0;i<stack.length;i++){
3432
constnode=stack.pop()
35-
3633
if(node.value===value){
3734
returnnode
3835
}
@@ -59,11 +56,10 @@ const tree = [
5956
{value:10,left:null,right:null},
6057
{value:1,left:null,right:null}
6158
]
62-
63-
searchDFS(tree,9)
64-
searchDFS(tree,10)
65-
66-
traverseDFS(6)
59+
searchDFS(tree,9)// { value: 9, left: 7, right: 8 }
60+
searchDFS(tree,200)// null
61+
traverseDFS(tree,6)// [ 1, 2, 3, 4, 5, 8, 10, 9, 7, 6 ]
62+
traverseDFS(tree,200)// []
6763

6864
// 6
6965
// / \
@@ -74,3 +70,4 @@ traverseDFS(6)
7470
// 2 8 10
7571
// /
7672
// 1
73+
export{searchDFS,traverseDFS}

‎Trees/test/DepthFirstSearch.test.js

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
import{searchDFS,traverseDFS}from'../DepthFirstSearch'
2+
3+
describe('Depth First Tree Traversal',()=>{
4+
consttree=[
5+
{value:6,left:1,right:2},
6+
{value:5,left:3,right:4},
7+
{value:7,left:null,right:5},
8+
{value:3,left:6,right:null},
9+
{value:4,left:null,right:null},
10+
{value:9,left:7,right:8},
11+
{value:2,left:9,right:null},
12+
{value:8,left:null,right:null},
13+
{value:10,left:null,right:null},
14+
{value:1,left:null,right:null}
15+
]
16+
17+
// 6
18+
// / \
19+
// 5 7
20+
// / \ \
21+
// 3 4 9
22+
// / / \
23+
// 2 8 10
24+
// /
25+
// 1
26+
27+
it('should be null if given value is not present in the tree - DF Search',()=>{
28+
constres=searchDFS(tree,200)
29+
expect(res).toStrictEqual(null)
30+
})
31+
32+
it('should return the node if given value is present in the tree - DF Search',()=>{
33+
constres=searchDFS(tree,9)
34+
expect(res).toStrictEqual({value:9,left:7,right:8})
35+
})
36+
37+
it('should return empty array if given root is not present in the tree - DF Traversal',()=>{
38+
consttraversal=traverseDFS(tree,200)
39+
expect(traversal).toStrictEqual([])
40+
})
41+
42+
it('should return DFT array of given tree from specified root if given root is present in the tree - DF Traversal',()=>{
43+
consttraversal=traverseDFS(tree,6)
44+
expect(traversal).toStrictEqual([1,2,3,4,5,8,10,9,7,6])
45+
})
46+
})

0 commit comments

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