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软件测试网获作者授权连载本书部分章节。
任何个人或单位未获得明确的书面许可，不得对本文内容复制、转载或进行镜像，否则将追究法律责任。
