# Sequence traversal of binary tree: pre order, middle order, post order, sequence traversal, Java implementation (recursive, non recursive)

As for the content of binary tree, I think the core of binary tree is its several traversal methods. Basically, all problems revolve around several traversal methods. So I will summarize these traversal methods here.

## Preorder traversal

I. Introduction
Preorder traversal (DLR) is a kind of binary tree traversal, also known as root traversal, preorder traversal, which can be recorded as root left and right.
The preorder traversal first accesses the root node, then traverses the left subtree, and finally traverses the right subtree. When traversing the left and right subtrees, we still visit the root node first, then the left subtree, and finally the right subtree.
If the binary tree is empty, it ends returning. Otherwise:
1. Access root node
2. Preorder traversal of left subtree
2. Preorder traversal right subtree
As shown in the figure: Previous traversal result: ABDECF 2, Code implementation
1. Recursive implementation

```class TreeNode{//TreeNode class, the same at the back
TreeNode left;
TreeNode right;
int val;
TreeNode(int val){
this.val = val;
}
}

public class PreOrderTraversal {
public void preOrder(TreeNode root){
if(root != null){
System.out.println(root.val);//Print root node
preOrder(root.left);//Access left subtree
preOrder(root.right);//Access right subtree
}
}
}
```

2. Non recursive implementation
Method 1: the root node is stored in the stack to print the root node, and then access the left subtree of the root node. The left subtree also stores the root of the left subtree in the stack to print the root node, and then goes down until the left subtree is empty, and then takes out the top element of the stack (the root node of the left subtree after visiting) as a new root node to access the right subtree.

```public void preorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();//Use a stack to store nodes in the tree
while(root != null || !stack.isEmpty()) {//As long as the current node is not empty (that is, the left and right subtrees of the current node are not fully accessed) or there are nodes in the stack (there are still nodes that are not accessed)
while (root != null) {//Go all the way to the left
stack.push(root);//Root node stack
System.out.println(root.val);//Print root node
root = root.left;//Access left subtree
}
root = stack.pop();//Take out the root node
root = root.right;//Access right subtree
}
}
```

Method 2: we know that the previous traversal follows the order of left and right roots, so we print the root node, and press its right subtree and left subtree into the stack in order. Only one node at the top of the stack is taken out each time, so that all the left subtrees will be taken out and printed before the right subtree.

```import java.util.Stack;

public class PreOrderTraversal {
public void preorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
if(root == null)//The tree is empty.
return;
stack.add(root);//Push the root node into the stack
while(!stack.isEmpty()){//Loop as long as the stack is not empty
TreeNode node = stack.pop();//Take out the stack top element to print. At this time, the stack top element is the root of the subtree whose root is node
System.out.println(node.val);
if(node.right != null)//Push the right subtree into the stack
stack.push(node.right);
if(node.left != null)//Push the left subtree into the stack
stack.push(node.left);
}
}
}
```

## Sequential traversal

I. Introduction
Middle order traversal (LDR) is a kind of binary tree traversal, also called middle root traversal and middle order traversal. Remember to be left root right
Middle order traversal first traverses the left subtree, then accesses the root node, and finally traverses the right subtree.
If the binary tree is empty, it ends returning. Otherwise:
1. Middle order traversal left subtree
2. Access root node
3. Middle order traversal right subtree
As shown in Figure: middle order traversal result: DBEAFC 2, Code implementation
1. Recursive implementation

```public class InOrderTraversal {
public void inorderTraversal(TreeNode root){
if(root != null){
inorderTraversal(root.left);//Access left subtree
System.out.println(root.val);//Print root node
inorderTraversal(root.right);//Access right subtree
}
}
}
```

2. Non recursive implementation
The same way of thinking is used in the root pre order traversal method. The difference is that the root node is not printed first, but the left subtree is accessed first, then the root node is printed, and the right subtree is accessed.

```import java.util.Stack;

public class InOrderTraversal {
public void inorderTraversal(TreeNode root){
Stack<TreeNode> stack = new Stack<>();
while(root != null || !stack.isEmpty()){//As long as the current node is not empty (that is, the left and right subtrees of the current node are not fully accessed) or there are nodes in the stack (there are still nodes that are not accessed)
while(root != null){
stack.push(root);//Root node stack
root = root.left;//Access left subtree
}
root = stack.pop();//Take out the root node of the left subtree
System.out.println(root.val);//Print root node
root = root.right;//Access right subtree
}
}
}

```

## Post order traversal

I. Introduction
First, we traverse the left subtree, then the right subtree, finally the root node. When we traverse the left and right subtrees, we still traverse the left subtree, then the right subtree, and finally the root node.
If the binary tree is empty, it ends returning. Otherwise:
1. Middle order traversal left subtree
2. Middle order traversal right subtree
3. Access root node
As shown in Figure: post order traversal result: DEBFCA 2, Code implementation
1. Recursive implementation

```public class PostOrderTraversal {
public void postOrder(TreeNode root){
if(root != null){
postOrder(root.left);//Access left subtree
postOrder(root.right);//Access right subtree
System.out.println(root.val);//Print root node
}
}
}
```

2. Non recursive implementation
Method 1: the left and right roots are traversed normally, which is similar to the preorder and middle order methods.

```import java.util.Stack;

public class PostOrderTraversal {
public void postorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode node = root;
TreeNode prev = null;
while(node != null || !stack.isEmpty()){
while(node != null){
//Access left subtree
stack.push(node);
node = node.left;
}
//Judge stack top element (root)
node = stack.peek();
//1. If the right subtree of the root at this time is empty node.right == null
//2. If the right subtree of the root at this time has visited node.right == prev(prev records the node last visited for printing)
if(node.right == null || node.right == prev){
//Print the root node and exit the stack, and delete the printed node from the stack
stack.pop();
System.out.println(node.val);
//Record prev, indicating that the subtree with the current prev as the root has been visited
prev = node;
//If node is set to null, the left and right subtrees with node as root node will not be accessed again. Since the node here has been printed, it means that its left and right subtrees have already been accessed
node = null;
}else{
//Access right subtree
node = node.right;
}
}
}
}
```

Method 2: similar to method 2 of preorder traversal, we can use a linear table to store the results of postorder traversal. We know that the post order traversal is the left and right roots, but we can visit the root first, just put the root behind and then visit the right subtree in front of the root and then the left subtree. We can use linear header interpolation to achieve this operation, first visit the root, then the right subtree and then the left subtree, but we do header interpolation on the linear table every time, so the final result is the left and right roots .

```import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class PostOrderTraversal {
public List<Integer> postorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
if(root == null)
return list;
stack.push(root);
while(!stack.isEmpty()){
TreeNode node = stack.pop();
list.add(0, node.val);//Plug in the root node
if(node.left != null)
stack.push(node.left);
if(node.right != null)
stack.push(node.right);
}
return list;
}
}
```

## level traversal

I. Introduction
In addition to the first order traversal, the middle order traversal and the second order traversal, the binary tree can also be traversed. Let the number of layers of the root node of the binary tree be 1, sequence traversal is to start from the root node of the binary tree, first visit the root node of the first layer, then visit the node of the second layer from left to right, then the node of the third layer, and so on, from top to bottom, from left to right, the process of visiting the node of the tree layer by layer is sequence traversal.
As shown in the figure: sequence traversal result: ABCDEF 2, Code implementation

```import java.util.LinkedList;
import java.util.Queue;

public class LevelOrder {
public void levelOrder(TreeNode root) {
if(root != null){//If the root node is not empty, queue the first level root node
queue.offer(root);
}
while(!queue.isEmpty()){//Loop as long as the queue is not empty
int num = queue.size();//Record the length of the queue at this time. The num at this time represents the total number of nodes in a certain layer, so as to prevent the number of nodes in the queue behind from affecting the output nodes of this layer
for(int i = 0; i < num; i++){//Operate on all nodes of a layer (from left to right)
TreeNode topNode = queue.poll();//Take out the first node of this layer
System.out.println(topNode.val);//Print node
if(topNode.left != null){//Queue the left subtree root node of this node
queue.offer(topNode.left);
}
if(topNode.right != null){//Queue the right subtree root node of this node
queue.offer(topNode.right);
}
}
}
}
}
```

Conclusion:
The so-called traversal refers to a search route along which each node in the tree is visited once and only once. The operation of the access node depends on the specific application problems. Traversal is one of the most important operations on a binary tree and the basis of other operations on a binary tree. Be sure to experience the traversal process carefully.  57 original articles published, praised 0 and visited 782

Keywords: Java

Added by popcornplya on Wed, 26 Feb 2020 12:24:54 +0200