java 二叉树的深度优先遍历、搜索，广度优先遍历、搜索 2017年9月1日
未分类
0 条评论

java 二叉树的深度优先遍历、搜索，广度优先遍历、搜索

（2017.9.5 这里要补充一点，树是图的子集，图的遍历、搜索也是同理）

深度优先需要借助栈、直接递归实现，广度优先需要借助队列实现。

在了解本文之前，需要先弄懂java中的ArrayDeque（ArrayDeque既可以作为队列使用，也可以作为栈使用），本文不另行介绍（其实直接看看ArrayDeque的Api就行了，很好懂）。

 

一、深度优先遍历

直接递归遍历：

1
2
3
4
5
6
7
8
9
10
public static void depthTraversal(Node node) {
 
if (node != null) {
 
System.out.print(node.data + " ");
 
depthTraversal(node.left);
depthTraversal(node.right);
}
}

二、深度优先搜索

深度优先搜索就是一直往下搜索，有两种实现思路：递归、栈。

使用栈实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public static Node depthTraversal(Node root, int data) {
 
if (root == null) {
 
throw new RuntimeException("empty tree!");
}
 
ArrayDeque<Node> stack = new ArrayDeque<>();
 
stack.push(root);
 
while (stack.isEmpty() == false) {
 
Node node = stack.pop();
System.out.println(node.data);
 
if (node.data == data) {
 
return node;
 
} else {
 
if (node.right != null) {
 
stack.push(node.right);
}
 
if (node.left != null) {
 
stack.push(node.left);
}
}
}
return null;
}

三、广度优先遍历

使用队列实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public static void wideTraversal(Node node) {
 
if (node == null) {
 
System.out.println("empty tree");
}
 
ArrayDeque<Node> queue = new ArrayDeque<Node>();
 
queue.add(node);
 
while (!queue.isEmpty()) {
 
Node n = queue.remove();
 
System.out.print(n.data + " ");
 
if (n.left != null) {
 
queue.add(n.left);
}
 
if (n.right != null) {
 
queue.add(n.right);
}
}
}

四、广度优先搜索

广度优先搜索就是“横向”搜索（同级搜索）。

使用队列实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public static Node wideTraversal(Node root, int data) {
 
if (root == null) {
 
throw new RuntimeException("empty tree!");
}
 
ArrayDeque<Node> queue = new ArrayDeque<>();
 
queue.add(root);
 
while (queue.isEmpty() == false) {
 
Node node = queue.remove();
 
System.out.println(node.data);
 
if (node.data == data) {
 
return node;
 
} else {
 
if (node.right != null) {
 
queue.add(node.right);
}
 
if (node.left != null) {
 
queue.add(node.left);
}
}
}
 
return null;
}

五、搜索某个元素时，应该使用深度、广度优先搜索吗？

如果我们需要搜索元素，首先应该考虑、使用二叉树的特性。个人认为：一般不会使用这两种搜索方式去搜索某个元素。

正确的搜索方式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static Node find(Node root, int data) {
 
if (root == null) {
 
return null;
}
System.out.println(root.data);
if (root.data == data) {
return root;
}
if (data > root.data) {
return find(root.right, data);
} else {
return find(root.left, data);
}
}

六、总结

个人认为所谓的“深度、广度优先遍历”确实有用，而“深度、广度优先搜索似乎没有必要”。当然具体情况需要具体分析。

Post Views: 210