在遇到树的时候，很重要的一点就是对于树的遍历，树的遍历方式分为先序、中序、后序和层次遍历
先序遍历是首先输出根节点其次是左子树和右子树 中序遍历是先输出左子树其次是根节点然后再右子树 后序遍历是先输出左子树和右子树最后输出根节点 层序遍历是从根节点开始，遍历所有子节点之后进入子节点所在层次
本文中会对于先序、中序和后序遍历进行递归和非递归两种操作的实现，而对于层次遍历只进行非递归的实现 而且递归实现比较简单，在此就不详细讨论
对于前序遍历的非递归实现，首先要将当前节点保存到栈中，再所有左子树遍历完之后，输出栈顶节点，并以相同方式遍历右子树
//前序遍历的递归实现
public void PreorderRecursionTraversal(TreeNode node) {
if (node != null) {
System.out.print(node.val + " ");
PreorderRecursionTraversal(node.left);
PreorderRecursionTraversal(node.rigth);
}
}
//前序遍历的非递归实现
public void PreorderTraversal(TreeNode node) {
Stack<TreeNode> stack = new Stack<>();
while (node != null || !stack.empty()) {
while (node != null) {
stack.push(node);
System.out.print(node.val + " ");
node = node.left;
}
if (!stack.empty()) {
node = stack.pop();
node = node.rigth;
}
}
}
中序遍历的非递归实现与前序遍历基本相同，所以在此不再详细讨论
//中序遍历的递归实现
public void InorderRecursionTraversal(TreeNode node) {
if (node != null) {
InorderRecursionTraversal(node.left);
System.out.print(node.val + " ");
InorderRecursionTraversal(node.rigth);
}
}
//中序遍历的非递归实现
public void InorderTraversal(TreeNode node) {
Stack<TreeNode> stack = new Stack<>();
while (node != null || !stack.empty()) {
while (node != null) {
stack.push(node);
node = node.left;
}
if (!stack.empty()) {
System.out.print(stack.peek().val + " ");
node = stack.pop();
node = node.rigth;
}
}
}
后序遍历的非递归实现主要是要考虑根节点是否遍历过的问题，所以要通过一个Visited节点来标记，如果为假则访问左子树，否则访问右子树
//后序遍历的递归实现
public void PostorderRecursionTraversal(TreeNode node) {
if (node != null) {
PostorderRecursionTraversal(node.left);
PostorderRecursionTraversal(node.rigth);
System.out.print(node.val + " ");
}
}
//后序遍历的非递归实现
public void PostorderTraversal(TreeNode node) {
Stack<Object[]> stack = new Stack<>();
stack.push(new Object[]{node, false});
while (!stack.empty()) {
node = (TreeNode) stack.peek()[0];
boolean visited = (boolean) stack.peek()[1];
stack.pop();
if (node == null) {
continue;
}
if (visited) {
System.out.print(node.val + " ");
} else {
stack.push(new Object[]{node, true});
stack.push(new Object[]{node.rigth, false});
stack.push(new Object[]{node.left, false});
}
}
}
层次遍历需要一个队列来存储当前层的所有节点，并将队列的头节点的所有子节点加入到队列的末尾
//层次遍历的非递归实现
public void LevelorderTraversal(TreeNode node) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(node);
while (!queue.isEmpty()) {
node = queue.peek();
System.out.print(node.val + " ");
if (node.left != null) {
queue.offer(node.left);
}
if (node.rigth != null) {
queue.offer(node.rigth);
}
queue.poll();
}
}