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); } } |
六、总结
个人认为所谓的“深度、广度优先遍历”确实有用,而“深度、广度优先搜索似乎没有必要”。当然具体情况需要具体分析。