遍历二叉树

void preOrderTraverse(Node root) {
    if (root == null) return;

    System.out.println(root.data);
    preOrderTraverse(root.lchild);
    preOrderTraverse(root.rchild);
}

void inOrderTraverse(Node root) {
    if (root == null) return;

    preOrderTraverse(root.lchild);
    System.out.println(root.data);
    preOrderTraverse(root.rchild);
}

void postOrderTraverse(Node root) {
    if (root == null) return;

    preOrderTraverse(root.lchild);
    preOrderTraverse(root.rchild);
    System.out.println(root.data);
}

void preOrderTraverse(Node root) {  
    Stack<Node> nodeStack = new Stack<>();  
    nodeStack.push(root);  
    while(!nodeStack.isEmpty()) {  
        Node node = nodeStack.pop();  
        System.out.println(node.data);
        if(node.rChild != null) {  
            nodeStack.push(node.rChild);  
        }  
        if(node.lChild != null) {  
            nodeStack.push(node.lChild);  
        }
    }  
}

void inOrderTraverse(Node root) {
	Stack<Node> nodeStack = new Stack<Node>();
	Node node = root;
	while(node != null || !nodeStack.isEmpty()) {
		while(node != null) {
			nodeStack.push(node);
			node = node.lChild;
		}
		if(nodeStack.size() > 0) {
			node = nodeStack.pop();
			System.out.println(node.data);
			node = node.rightChild;
		}
	}
}

void postOrderTraverse(Node root) {
	Stack<Node> nodeStack = new Stack<>();
	Node node = root;
	// 访问根节点时判断其右子树是够被访问过
	Node preNode = null;
	while (node != null || !nodeStack.isEmpty()) {
		// 把当前节点的左侧节点全部入栈
		while (node != null) {
			stack.push(node);
			node = node.lChild;
		}
		if (nodeStack.size() > 0) {
			Node temp = stack.peek().rChile;
			// 一个根节点被访问的前提是：无右子树或右子树已被访问过
			if (temp == null || temp == preNode) {
				node = stack.pop();
				System.out.println(node.data);
				// 记录刚被访问过的节点
				preNode = node;
				node = null;
			} else {
				// 处理右子树
				node = temp;
			}
		}
	}
}

void breadthFirstSearch(Node root) {
	Queue<Node> nodeQueue = new LinkedList<>();
	nodeQueue.push(root);
	while (!nodeQueue.isEmpty()) {
		Node node = nodeQueue.pop();
		System.out.println(node.data);
		if (node.lChild != null) {
			nodeQueue.push(node.lChild);
		}
		if (node.rChild != null) {
			nodeQueue.push(node.rChild);
		}
	}
}