A binary tree structure
Let’s look at the basic structure of a binary tree.
1 (root)
/ \
(root.left) 2 3 (root.right)
/ \ / \
4 5 6 7
Copy the codeBinary trees are an updated version of the linked list structure. What’s better about them than linked lists? A node in a linked list has only one child node, whereas a binary tree has two. A node in a binary tree will hold at least two Pointers, one to its left child and one to its right child. Let’s look at the node structure of a binary tree:
class TreeNode {
TreeNode left;// Left child of the current node
TreeNode right;// Right child of the current node
int value;/ / data
}
Copy the codeFor the binary tree structure, how do we access each node? Usually, there are several kinds of binary tree traversal, first sequence traversal, in sequence traversal, after the sequence traversal and level traversal, for after the first sequence traversal, we can simply understand to, are on the parent node, that is to say, I’m traversal of a binary tree, is the first access to the parent node, then visit left child node, right child nodes, is called the first sequence traversal. In the three nodes, the left child node is traversed first, the parent node is traversed in the middle, and the right child node is traversed last, which is the middle order traversal. The left child node is visited first, then the right child node, and finally the parent node, which is a back-order traversal. Sequential traversal is a layer of nodes traversed from left to right. So for our given binary tree structure, the result of the first order traversal is: 1,2,4,5,3,6,7, the result of the middle order traversal is: 4,2,5,1,6,3,7, and the result of the second order traversal is: 4,5,2,6,7,3,1. The sequence traversal results are: 1,2,3,4,5,6,7. How do you do that in code? It’s actually very simple, and we can do it recursively.
Recursively traverses the binary tree
- Recursion is sequential traversal
// Recursively traverses the binary tree first
public void preOrderRecursive(TreeNode root) {
if (root == null) return;// End condition of recursion
System.out.print(root.value + "");// Before accessing the left and right child nodes *, access the current node data and print
preOrderRecursive(root.left);// The left child node is traversed in order
preOrderRecursive(root.right);// Walk through the right child node first
}
Copy the code- Sequential traversal in recursion
// The binary tree is traversed recursively
public void inOrderRecursive(TreeNode root) {
if (root == null) return;// End condition of recursion
inOrderRecursive(root.left);// The left child node is traversed in order
System.out.print(root.value + "");// Access between left and right child nodes *, access the current node data and print
inOrderRecursive(root.right);// The sequence traverses the right child node
}
Copy the code- Recursive order traversal
// the binary tree is traversed recursively
public void postOrderRecursive(TreeNode root) {
if (root == null) return;// End condition of recursion
postOrderRecursive(root.left);// The left child node is traversed sequentially
postOrderRecursive(root.right);// Walk through the right child node in sequence
System.out.print(root.value + "");// After accessing the left and right child nodes *, access the current node data and print it
}
Copy the codeAs you can see, the way to recursively traverse a binary tree is very simple, so if we don’t want to recursively traverse a binary tree, what do we do?
3. Traversing the binary tree in a non-recursive manner
Without further ado, let’s get right to the code:
- The first sequence traversal
public void preOrder(TreeNode root) {
if (root == null) return;
System.out.println("binary tree pre order traverse: ");
Stack<TreeNode> stack = new Stack<>();// Use the stack structure to store access information
stack.push(root);
while(! stack.isEmpty()) { root = stack.pop();// Access the current node when it is popped from the stack
System.out.println("cur = " + root.value);// Displays node information
if(root.right ! =null) {// Because of the lifO nature of the stack, we will push the right node first, ensuring that it is accessed after the left node
stack.push(root.right);
}
if(root.left ! =null) {// The left node is pushed back and the first node is eject to ensure that the parent node -> left node -> right node access orderstack.push(root.left); }}}Copy the code- In the sequence traversal
Middle order traversal can also be understood asfigureThe depth-first traversal (DFS) for the left child of the parent node goes back to explore other nodes when there is no way out.
public void inOrder(TreeNode root) {
if (root == null) return;
System.out.println("binary tree in order traverse: ");
Stack<TreeNode> stack = new Stack<>();// Also need a stack to assist the operation, compared to the sequential traversal, no stack first
while(! stack.isEmpty() || root ! =null) {
if(root ! =null) {
stack.push(root);
root = root.left;// If a node has left children, the left children are pushed until there are no left children
} else {// If the current traversal node has no left child node, the left node is accessed
root = stack.pop();
System.out.println("val = " + root.value);// Access node information and print it
root = root.right;// Since the current node has no left child, the current pointer advances to the right child, and the process is repeated}}}Copy the code- After sequence traversal sequence traversal process and sequence traversal can be understood as the process of the first is on the contrary, for in the first sequence traversal process – > right – > left, after the sequence traversal process for left – > right – >, we understand, reversed the first sequence traversal process execution, swaps, again about the node access sequence can, on the basis of prior sequence traversal sequence traversal after implementation.
public void postOrder(TreeNode root) {
if (root == null) return;
System.out.println("binary tree post order traverse: ");
Stack<TreeNode> stack1 = new Stack<>();// Backorder traversal requires two stacks
Stack<TreeNode> stack2 = new Stack<>();// Invert the result of the sequence traversal
stack1.push(root);
while(! stack1.isEmpty()) { root = stack1.pop(); stack2.push(root);if(root.left ! =null) {// Note that this is different from sequential traversal in that the left node is pushed first, i.e. the access order of the left and right nodes is reversed
stack1.push(root.left);
}
if(root.right ! =null) { stack1.push(root.right); }}while(! stack2.isEmpty()) {// Use the last-in, first-out feature of the stack to invert the entire traversal result of the first order, i.e., to obtain the desired post-order traversal result
System.out.println(stack2.pop().value + ""); }}Copy the code4. Sequence traversal binary tree
Binary tree can be understood as a graph with a specific structure, and sequence traversal is an embodiment of breadth first traversal (BFS) of the graph. Here we use the structure of a queue to aid in traversal. Queues are characterized by first in, first out.
public void levelOrder(TreeNode root) {
if (root == null) return;
System.out.println("binary tree level traverse: ");
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(! queue.isEmpty()) { root = queue.poll();// The nodes in the advanced queue are popped up first and accessed first
System.out.print(root.val + "");
if(root.left ! =null) {// Each parent node has left and right child nodes. Hierarchical traversal means that the parent node is accessed first and then the left and right child nodes are accessed in order from left to right.
queue.offer(root.left);// The left child node is queued. The next cycle is to eject the left child node and queue the left and right children of the left child node.
}
if(root.right ! =null) {
queue.offer(root.right);// The right child node is queued,
}
}
System.out.println();
}
Copy the codeFive, the summary
This paper introduces several basic traversal methods of binary tree, and gives the implementation code of recursive and non-recursive traversal, through the code annotation to deeply understand the traversal process of binary tree.