Binary tree traversal (recursive and non-recursive)
Traversal: traversal Recursion: recursion
Stack———-Backtracking———-Recursion
The stack is related to backtracing
This article discusses the code (Java) implementation of common binary tree traversal methods, including
Preorder, inorder, postorder, level order,
Further consider recursive and non-recursive implementations.
The implementation method of recursion is relatively simple, but since the recursive execution method will generate a new method call stack every time, if the recursion level is deep, it will cause large memory overhead.
In contrast, non-recursive methods can avoid this problem. Recursive traversal is easy to implement, but non-recursive call is not that simple. Non-recursive call essentially maintains a stack to simulate the behavior of the method call stack of recursive call.
Binary tree traversal by Java
There are many traversal methods for binary trees, including depth-first traversal and breadth-first traversal (level traversal).
This article only covers recursive and non-recursive traversal of binary trees in preorder, inorder, and postorder.
All the code involved is written in Java.
First give the binary tree node class:
Tree node:
1 class TreeNode {
2 int val;
3 //Left subtree
4TreeNode left;
5 //right subtree
6TreeNode right;
7 //Construction method
8 TreeNode(int x) {
9 val = x;
10}
11}
No matter which traversal method is used, the order of testing nodes is the same (when thinking about doing test papers, manually traverse the testing order). It’s just that sometimes the node is examined and temporarily stored, and needs to be output in the subsequent process.
Figure 2: Pre-order, mid-order, and post-order traversal node inspection order
As shown in Figure 1, the results obtained by the three traversal methods (manual) are:
Precedence: 1 2 4 6 7 8 3 5 Middle order: 4 7 6 8 2 1 3 5 Sequence: 7 8 6 4 2 5 3 1
The examination order of the three traversal methods is the same, but the results obtained are different. The reasons are:
Preorder: After inspecting a node, immediately output the value of the node and continue traversing its left and right subtrees. (root or so)
In-order: After inspecting a node, it is temporarily stored. After traversing the left subtree, the value of the node is output, and then the right subtree is traversed. (left root right)
Post-order: After detecting a node, temporarily store it, and then output the value of the node after traversing the left and right subtrees. (left and right roots)
Preorder traversal
Recursive pre-order traversal
Recursive pre-order traversal is easy to understand. It first outputs the value of the node, and then recursively traverses the left and right subtrees. The recursion of in-order and post-order is similar, just change the output position of the root node.
1 // Recursive pre-order traversal
2 public static void recursionPreorderTraversal(TreeNode root) {
3 if (root != null) {
4 System.out.print(root.val + " ");
5 recursionPreorderTraversal(root.left);
6 recursionPreorderTraversal(root.right);
7}
8}
Non-recursive pre-order traversal
Because we need to traverse the right subtree of the node after traversing the left subtree of the node, in order to find the node, we need to use the stack for temporary storage. Both in-order and post-order also involve backtracking, so they both need to use the stack.
Figure 2: Non-recursive pre-order traversal
Traversal process reference notes
1 // Non-recursive pre-order traversal
2 public static void preorderTraversal(TreeNode root) {
3 // Stack used to temporarily store nodes
4 Stack<TreeNode> treeNodeStack = new Stack<TreeNode>();
5 // Create a new cursor node as the root node
6 TreeNode node = root;
7 // When the last node is traversed, both its left and right subtrees are empty, and the stack is also empty.
8 //So, as long as these two points are not met at the same time, you need to enter the loop
9 while (node != null || !treeNodeStack.isEmpty()) {
10 // If the current node under examination is not empty, output the value of the node
11 // From the test sequence, we know that we need to keep going left
12 while (node != null) {
13 System.out.print(node.val + " ");
14 // In order to find the right subtree of the node later, temporarily store the node
15 treeNodeStack.push(node);
16 node = node.left;
17}
18 // Until the left subtree is empty, start considering the right subtree
19 // If the stack is empty, there is no need to consider it again
20 // Pop the top element of the stack and set the cursor equal to the right subtree of the node
21 if (!treeNodeStack.isEmpty()) {
22 node = treeNodeStack.pop();
23 node = node.right;
twenty four }
25}
26}
Results of preorder traversal:
Recursive pre-order traversal: 1 2 4 6 7 8 3 5 Non-recursive preorder traversal: 1 2 4 6 7 8 3 5
In-order traversal
Recursive in-order traversal
The process is similar to recursive preorder traversal
1 // Recursive in-order traversal
2 public static void recursionMiddleorderTraversal(TreeNode root) {
3 if (root != null) {
4 recursionMiddleorderTraversal(root.left);
5 System.out.print(root.val + " ");
6 recursionMiddleorderTraversal(root.right);
7}
8}
Non-recursive in-order traversal
Similar to non-recursive pre-order traversal, the only difference is that when the current node is examined, the node is not output directly.
Instead, when the node being examined is empty, it will be output when it is popped from the stack (the left subtree is always considered first, and the root node is not accessed until the left subtree is empty).
1 // Non-recursive in-order traversal
2 public static void middleorderTraversal(TreeNode root) {
3 Stack<TreeNode> treeNodeStack = new Stack<TreeNode>();
4 TreeNode node = root;
5 while (node != null || !treeNodeStack.isEmpty()) {
6 while (node != null) {
7 treeNodeStack.push(node);
8 node = node.left;
9 }
10 if (!treeNodeStack.isEmpty()) {
11 node = treeNodeStack.pop();
12 System.out.print(node.val + " ");
13 node = node.right;
14}
15}
16}
In-order traversal results
Recursive in-order traversal: 4 7 6 8 2 1 3 5 Non-recursive in-order traversal: 4 7 6 8 2 1 3 5
Post-order traversal
Recursive post-order traversal
The process is similar to recursive preorder traversal
1 // Recursive post-order traversal
2 public static void recursionPostorderTraversal(TreeNode root) {
3 if (root != null) {
4 recursionPostorderTraversal(root.left);
5 recursionPostorderTraversal(root.right);
6 System.out.print(root.val + " ");
7}
8}
Non-recursive post-order traversal
Subsequent traversal is different from pre-order and in-order traversal.
When post-order traversal determines whether the value of the current node can be output, it needs to consider whether its left and right subtrees have been traversed.
So you need to set up a lastVisit cursor.
If lastVisit is equal to the right subtree of the current node under examination, it means that the left and right subtrees of the node have been traversed, and the current node can be output.
And set the lastVisit node to the current node, set the current cursor node node to empty, and the top element of the stack can be accessed in the next round.
If not, you need to consider the right subtree next, node = node.right.
Consider the following three situations in postorder traversal:
Figure 3: Post-order, the right subtree is not empty, node = node.right
As shown in Figure 3, the left subtree starting from node 1 to node 4 is empty.
Note: The cursor node node = 4.left == null at this time.
At this time, you need to Peek() the top element of the stack from the stack.
It is found that the right subtree of node 4 is not empty. We need to check the right subtree next. 4 cannot be output, node = node.right.
Figure 4: Post-order, both left and right subtrees are empty, output directly
As shown in Figure 4, it is found that node 7 (7.left == null, 7 is popped from the stack), its left and right subtrees are empty, and 7 can be output directly.
At this time, you need to set lastVisit to node 7, and set the cursor node node to null. In the next cycle, node 6 in the stack will be examined.
Figure 5: Post-order, right subtree = lastVisit, direct output
As shown in Figure 5, after checking node 8 (lastVisit == node 8), the cursor node node is assigned to the top element 6 of the stack, and the right subtree of node 6 is exactly equal to node 8. Indicates that the left and right subtrees of node 6 have been traversed, and 6 is output directly.
At this time, the node can be popped directly from the stack with Pop(). Previously, only Peek() was used.
Set the cursor node node to null.
1 // Non-recursive post-order traversal
2 public static void postorderTraversal(TreeNode root) {
3 Stack<TreeNode> treeNodeStack = new Stack<TreeNode>();
4 TreeNode node = root;
5 TreeNode lastVisit = root;
6 while (node != null || !treeNodeStack.isEmpty()) {
7 while (node != null) {
8 treeNodeStack.push(node);
9 node = node.left;
10}
11 //View the current top element of the stack
12 node = treeNodeStack.peek();
13 //If its right subtree is also empty, or the right subtree has been accessed
14 //You can directly output the value of the current node
15 if (node.right == null || node.right == lastVisit) {
16 System.out.print(node.val + " ");
17 treeNodeStack.pop();
18 lastVisit = node;
19 node = null;
20 } else {
21 // Otherwise, continue traversing the right subtree
22 node = node.right;
twenty three }
twenty four }
25}
Post-order traversal results
Recursive post-order traversal: 7 8 6 4 2 5 3 1 Non-recursive post-order traversal: 7 8 6 4 2 5 3 1
Test:
package BinaryTreeTraversal;
public class Test {
/*
* 1
* / \
* twenty three
* / \
* 4 5
*\
*6
* / \
* 7 8
*/
public static void main(String[] args) {
TreeNode root=new TreeNode(1);
root.left=new TreeNode(2);
root.right=new TreeNode(3);
root.left.left=new TreeNode(4);
root.right.right=new TreeNode(5);
root.left.left.right=new TreeNode(6);
root.left.left.right.left=new TreeNode(7);
root.left.left.right.right=new TreeNode(8);
System.out.println("preorder:");
PreorderTraversal.recursionPreorderTraversal(root);
System.out.println();
PreorderTraversal.preorderTraversal(root);
System.out.println("\
");
System.out.println("inorder:");
InorderTraversal.recursionInorderTraversal(root);
System.out.println();
InorderTraversal.inorderTraversal(root);
System.out.println("\
");
System.out.println("postorder:");
PostorderTraversal.recursionPostorderTraversal(root);
System.out.println();
PostorderTraversal.postorderTraversal(root);
}
}
Reprint link: Binary tree traversal (pre-order, in-order, post-order)