Java实现深度优先遍历和广度优先遍历

爱被打了一巴掌 2023-06-28 11:19 58阅读 0赞

# Java实现深度优先遍历和广度优先遍历 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDYyNDQxMA_size_16_color_FFFFFF_t_70]  
深度优先搜索的步骤为：

（1）、首先节点 1 进栈，节点1在栈顶；

（2）、然后节点1出栈，访问节点1，节点1的孩子节点3进栈，节点2进栈；

（3）、节点2在栈顶，然后节点2出栈，访问节点2

（4）、节点2的孩子节点5进栈，节点4进栈

（5）、节点4在栈顶，节点4出栈，访问节点4，

（6）、节点4左右孩子为空，然后节点5在栈顶，节点5出栈，访问节点5；

（7）、节点5左右孩子为空，然后节点3在站顶，节点3出栈，访问节点3；

（8）、节点3的孩子节点7进栈，节点6进栈

（9）、节点6在栈顶，节点6出栈，访问节点6；

（10）、节点6的孩子为空，这个时候节点7在栈顶，节点7出栈，访问节点7

（11）、节点7的左右孩子为空，此时栈为空，遍历结束。

广度优先遍历：广度优先遍历是连通图的一种遍历策略，因为它的思想是从一个顶点V0开始，辐射状地优先遍历其周围较广的区域故得名。

根据广度优先遍历的特点我们利用Java数据结构队列Queue来实现。

广度优先搜索的步骤为：

（1）、节点1进队，节点1出队，访问节点1

（2）、节点1的孩子节点2进队，节点3进队。

（3）、节点2出队，访问节点2，节点2的孩子节点4进队，节点5进队；

（4）、节点3出队，访问节点3，节点3的孩子节点6进队，节点7进队；

（5）、节点4出队，访问节点4，节点4没有孩子节点。

（6）、节点5出队，访问节点5，节点5没有孩子节点。

（7）、节点6出队，访问节点6，节点6没有孩子节点。

（8）、节点7出队，访问节点7，节点7没有孩子节点，结束。

代码：

二叉树的基础代码：

/** * 二叉树数据结构 * * */
    public class TreeNode { 
    	int data;
    	TreeNode leftNode;
    	TreeNode rightNode;
    	public TreeNode() { 
    		
    	}
    	public TreeNode(int d) { 
    		data=d;
    	}
    	
    	public TreeNode(TreeNode left,TreeNode right,int d) { 
    		leftNode=left;
    		rightNode=right;
    		data=d;
    	}
    	
     
    }

广度优先和深度优先遍历算法实现代码:

import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Stack;
     
    //二叉树插入数据
    public class DeepFirstSort { 
    	public static void main(String[] args) { 
    		TreeNode head=new TreeNode(1);
    		TreeNode second=new TreeNode(2);
    		TreeNode three=new TreeNode(3);
    		TreeNode four=new TreeNode(4);
    		TreeNode five=new TreeNode(5);
    		TreeNode six=new TreeNode(6);
    		TreeNode seven=new TreeNode(7);
    		head.rightNode=three;
    		head.leftNode=second;
    		second.rightNode=five;
    		second.leftNode=four;
    		three.rightNode=seven;
    		three.leftNode=six;
    		System.out.print("广度优先遍历结果：");
    		new DeepFirstSort().BroadFirstSearch(head);
    		System.out.println();
    		System.out.print("深度优先遍历结果：");
    		new DeepFirstSort().depthFirstSearch(head);
    	}
    	
    	//广度优先遍历是使用队列实现的
    	public void BroadFirstSearch(TreeNode nodeHead) { 
    		if(nodeHead==null) { 
    			return;
    		}
    		Queue<TreeNode> myQueue=new LinkedList<>();
    		myQueue.add(nodeHead);
    		while(!myQueue.isEmpty()) { 
    			TreeNode node=myQueue.poll();
    			System.out.print(node.data+" ");
    			if(null!=node.leftNode) { 
    				myQueue.add(node.leftNode);    //深度优先遍历，我们在这里采用每一行从左到右遍历
    			}
    			if(null!=node.rightNode) { 
    				myQueue.add(node.rightNode);
    			}
    			
    		}
    	}
    	
    	//深度优先遍历
    	public void depthFirstSearch(TreeNode nodeHead) { 
    		if(nodeHead==null) { 
    			return;
    		}
    		Stack<TreeNode> myStack=new Stack<>();
    		myStack.add(nodeHead);
    		while(!myStack.isEmpty()) { 
    			TreeNode node=myStack.pop();    //弹出栈顶元素
    			System.out.print(node.data+" ");
    			if(node.rightNode!=null) { 
    				myStack.push(node.rightNode);    //深度优先遍历，先遍历左边，后遍历右边,栈先进后出
    			}
    			if(node.leftNode!=null) { 
    				myStack.push(node.leftNode);
    			}
    		}
    		
    	}
     
    }

结果为：  
![在这里插入图片描述][20200109091411393.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDYyNDQxMA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200109091156485.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDYyNDQxMA==,size_16,color_FFFFFF,t_70
[20200109091411393.png]: https://img-blog.csdnimg.cn/20200109091411393.png