bfs 二叉树 遍历

bfs 遍历二叉树

之前只知道bfs 的思想以及需要使用队列来进行存储

为了更好的理解bfs
手写了bfs 遍历二叉树的两种方式

方法:

一种是采用常用的递归执行
另一种是采用循环执行(使用栈来代替递归)

二叉树定义

class Node {
	//get set方法省略
	private Node leftChild;
	private Node rightChild;
	private int data;

	public Node(int data) {
		this.data = data;
	}
	
}

构造二叉树

Node node = new Node(1);

		node.setLeftChild(new Node(2));
		node.setRightChild(new Node(3));
		node.getLeftChild().setLeftChild(new Node(4));
		node.getLeftChild().setRightChild(new Node(5));
	
		bfs(node);

使用bfs

方式一:递归

public static void bfs(Node node) {
		if (node != null) {
			System.out.println(node.getData());
			if (node.getLeftChild() != null) {
				queue.add(node.getLeftChild());
			}
			if (node.getRightChild() != null) {
				queue.add(node.getRightChild());
			}
		}
		if(!queue.isEmpty()){
			bfs(queue.remove());
		}
	}

方式二:循环

public static void bfsUseLoop(Node node) {
		queue.add(node);
		while (!queue.isEmpty()) {

			Node remove = queue.remove();
			System.out.println(remove.getData());
			if (remove.getLeftChild() != null) {
				queue.add(remove.getLeftChild());
			}
			if (remove.getRightChild() != null) {
				queue.add(remove.getRightChild());
			}
		}
	}

参考文章

数据结构—递归与非递归实现DFS与BFS