Java实现二叉树的深度和广度优先搜索算法
1 package com.java; 2 3 import java.util.ArrayDeque; 4 5 /** 6 * 广度优先搜索 7 * 算法思路：首先访问起始顶点v，然后由v出发，依次访问v的各个未被访问过的邻接顶点w1,w2,w3….wn， 8 * 然后再依次访问w1，w2,…,wn的所有未被访问过的邻接顶点，再从这些访问过的顶点出发， 9 * 再访问它们所有未被访问过的邻接顶点….以此类推，直到所有的顶点都被访问过为止。 10 * 11 * 深度优先遍历 12 * 算法思路：首先访问该顶点v，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图， 13 * 直至图中所有和v有路径相通的顶点都被访问到。若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点， 14 * 重复上述过程，直至所有顶点都被访问到为止。 15 */ 16 17 public class BinaryTree { 18static class TreeNode{ 19 int value; 20 TreeNode left; 21 TreeNode right; 22 23 public TreeNode(int value){ 24 this.value=value; 25 } 26} 27 28TreeNode root; 29 30public BinaryTree(int[] array){ 31 root=makeBinaryTreeByArray(array,1); 32} 33 34/** 35* 采用递归的方式创建一颗二叉树 36* 传入的是二叉树的数组表示法 37* 构造后是二叉树的二叉链表表示法 38*/ 39public static TreeNode makeBinaryTreeByArray(int[] array,int index){ 40 if(index<array.length){ 41 int value=array[index]; 42 if(value!=0){ 43 TreeNode t=new TreeNode(value); 44 array[index]=0; 45 t.left=makeBinaryTreeByArray(array,index*2); 46 t.right=makeBinaryTreeByArray(array,index*2+1); 47 return t; 48 } 49 } 50 return null; 51} 52 53/** 54* 深度优先遍历，相当于先根遍历 55* 采用非递归实现 56* 需要辅助数据结构：栈 57*/ 58public void depthOrderTraversal(){ 59 if(root==null){ 60 System.out.println("empty tree"); 61 return; 62 } 63 ArrayDeque<TreeNode> stack=new ArrayDeque<TreeNode>(); 64 stack.push(root); 65 while(stack.isEmpty()==false){ 66 TreeNode node=stack.pop(); 67 System.out.print(node.value+" "); 68 if(node.right!=null){ 69 stack.push(node.right); 70 } 71 if(node.left!=null){ 72 stack.push(node.left); 73 } 74 } 75 System.out.print("\n"); 76} 77 78/** 79* 广度优先遍历 80* 采用非递归实现 81* 需要辅助数据结构：队列 82*/ 83public void levelOrderTraversal(){ 84 if(root==null){ 85 System.out.println("empty tree"); 86 return; 87 } 88 ArrayDeque<TreeNode> queue=new ArrayDeque<TreeNode>(); 89 queue.add(root); 90 while(queue.isEmpty()==false){ 91 TreeNode node=queue.remove(); 92 System.out.print(node.value+" "); 93 if(node.left!=null){ 94 queue.add(node.left); 95 } 96 if(node.right!=null){ 97 queue.add(node.right); 98 } 99 }100 System.out.print("\n");101}102 103/**104* 13105* / \106*65 5107* / \ \108* 97 25 37109* / /\ /110* 22 4 28 32111*/112public static void main(String[] args) {113 int[] arr={0,13,65,5,97,25,0,37,22,0,4,28,0,0,32,0};114 BinaryTree tree=new BinaryTree(arr);115 System.out.println("深度优先遍历结果为:");116 tree.depthOrderTraversal();117 System.out.println("广度优先遍历结果为:");118 tree.levelOrderTraversal();119}120 }
如果觉得《二叉树的深度和广度优先搜索算法》对你有帮助，请点赞、收藏，并留下你的观点哦！
