2.1.3 树、二叉树、图的遍历
1.树的深度优先、广度优先遍历算法
2.二叉树先序、中序、后序遍历;满二叉树、完全二叉树的定义
3.图的深度优先、广度优先遍历算法
树的遍历方式有深度优先和广度优先两种。
深度优先搜索就是在搜索树的每一层始终只扩展一个子节点,不断地向下一层前进(到达叶子结点或受到深度限制)时,才从当前节点返回到上一级节点,沿着另一个方向继续前进。广度优先搜索是深度越大的节点越先得到扩展,本层的节点没有搜索处理完时,不能对下层节点进行处理。
图2.8 搜索树(1)
如图2.8所示的搜索树,深度遍历结果为ABCDEFGHK,广度遍历结果为ABECFDGHK。
深度优先遍历算法中,采用栈来实现非递归算法,以二叉树为例,代码如下。
1.public void depthOrderTraversal(){ 2. if(root==null){ 3. System.out.println("empty tree"); 4. return; 5. } 6. ArrayDeque<TreeNode> stack=new ArrayDeque<TreeNode>(); 7. stack.push(root); 8. while(stack.isEmpty()==false){ 9. TreeNode node=stack.pop(); 10. System.out.print(node.value+" "); 11. if(node.right!=null){ 12. stack.push(node.right); 13. } 14. if(node.left!=null){ 15. stack.push(node.left); 16. } 17. } 18. System.out.print("\n"); 19. } 20. |
广度优先是利用队列来实现非递归算法,以二叉树为例,代码如下。
1. public void levelOrderTraversal(){ 2. if(root==null){ 3. System.out.println("empty tree"); 4. return; 5. } 6. ArrayDeque<TreeNode> queue=new ArrayDeque<TreeNode>(); 7. queue.add(root); 8. while(queue.isEmpty()==false){ 9. TreeNode node=queue.remove(); 10. System.out.print(node.value+" "); 11. if(node.left!=null){ 12. queue.add(node.left); 13. } 14. if(node.right!=null){ 15. queue.add(node.right); 16. } 17. } 18. System.out.print("\n"); 19. } |
版权声明:51Testing软件测试网获作者授权连载本书部分章节。
任何个人或单位未获得明确的书面许可,不得对本文内容复制、转载或进行镜像,否则将追究法律责任。