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<>(); List<Integer> list = new LinkedList<>(); 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) { Queue<TreeNode> queue = new LinkedList<>(); 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.