dfs 遍历二叉树

dfs 遍历二叉树

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

方法:

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

二叉树定义

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));
	
		dfs(node);

使用dfs

方式一:递归

public static void dfs(Node node) {

		if (node == null) {
			return;

		} else {
			// 本处使用先序遍历
			System.out.println(node.getData());
			dfs(node.getLeftChild());
			dfs(node.getRightChild());
		}
	}

方式二:循环

public static void dfsUseLoop(Node node) {
		// 由于不使用递归 故须使用栈来等价替代
		Stack<Node> stack = new Stack<Node>();
		stack.add(node);

		while (!stack.isEmpty()) {
			Node pop = stack.pop();
			System.out.println(pop.getData());
			stack.add(pop.getLeftChild());
			stack.add(pop.getRightChild());
		}

	}