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

Commitcdd28e9

Browse files
authored
Merge branch 'TheAlgorithms:master' into elementary-cellular-automata
2 parents78d5512 +fc06690 commitcdd28e9

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