中序遍历按照“左孩子-根结点-右孩子”的顺序进行访问。
- 递归遍历
/**
* 中序遍历
* @param node
*/
public static void inOrderTraverse(Node node) {
if (node == null) return;
inOrderTraverse(node.leftNode);
System.out.print(node.data + "\t");
inOrderTraverse(node.rightNode);
}
- 非递归遍历
- 若其左孩子不为空，则将P入栈并将P的左孩子置为当前的P，然后对当前结点P再进行相同的处理；
- 若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的P置为栈顶结点的右孩子；
- 直到P为NULL并且栈为空则遍历结束。
public static void nonInOrder(Node root) {
Stack<Node> stack = new Stack<Node>();
while(root != null || !stack.isEmpty()) {
if (root != null) {
stack.push(root);
root = root.leftNode;
} else {
root = stack.pop();
System.out.print(root.data + "\t");
root = root.rightNode;
}
}
}
