package com.camnter.basicexercises.tree;
import com.camnter.basicexercises.core.TreeNode;
import java.util.Stack;
/**
* 中序遍历
*
* 左根右
*
*
* - 1
* - 2 3
* - 4 5 6
* - 7 8
*
* 4 2 7 5 8 1 3 6
*
*
* @author CaMnter
*/
public class InOrder {
void inOrder(TreeNode root) {
if (root == null) return;
Stack> stack = new Stack>();
TreeNode current = root;
while (!stack.isEmpty() || current != null) {
// 处理所有左结点,入栈
while (current != null) {
stack.push(current);
current = current.left;
}
// 执行到这里,栈顶元素没有左孩子或者左子树都被访问过
if (!stack.isEmpty()) {
current = stack.pop();
System.out.print(current.value + " ");
current = current.right;
}
}
}
public static void main(String args[]) {
InOrder inOrder = new InOrder();
inOrder.inOrder(TreeNode.getTree());
}
}