算法思想:每次把最左边的加到栈里,一直到没有左结点,从栈中取数据并打印,把右孩子当作头再遍历该子树
package com.algorithm.practice.tree.traversal;
import java.util.Stack;
public class InOrderPrint {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
public static void InOrderPrint(Node head){
System.out.print("in-order: ");
if (head!=null){
Stack<Node> stack=new Stack<>();
while (!stack.isEmpty()||head!=null){
if (head!=null){
stack.push(head);
head=head.left;
}else {
head=stack.pop();
System.out.print(head.value+" ");
head=head.right;
}
}
}
}
public static void main(String[] args){
Node head = new Node(5);
head.left = new Node(3);
head.right = new Node(8);
head.left.left = new Node(2);
head.left.right = new Node(4);
head.left.left.left = new Node(1);
head.right.left = new Node(7);
head.right.left.left = new Node(6);
head.right.right = new Node(10);
head.right.right.left = new Node(9);
head.right.right.right = new Node(11);
InOrderPrint(head);
System.out.println();
}
}