Traversal of binary tree

Traversal of binary tree

Overview of Binary Tree Traversal

Traversal is a common operation in data structures.
The traversal of the binary tree is to visit all the elements once.

According to the different order of node access, there are 4 common ways to traverse a binary tree:

  • Preorder Traversal
  • Inorder Traversal
  • Postorder Traversal
  • Level Order Traversal

Preorder traversal

The idea of pre-order traversal:
1. Visit the root node;
2. Visit the left subtree of the
current node ; 3. If the current node has no left subtree, then visit the right subtree of the current node.

For the left subtree and the right subtree, pre-order traversal is also used.

Schematic diagram of binary tree preorder traversal:

The process of pre-order traversal of the binary tree in the above figure:
1) Visit the root node of the binary tree and find A;
2) Visit the left subtree of node A and find node B;
3) Visit the left subtree of node B and find node D;
4 ) Since access to the left subtree of node D fails, and there is no right subtree, the traversal of the subtree with node D as the root node is completed. But node B has not traversed its right subtree, so now it starts to traverse, that is, visit node E;
5) Since node E has no left and right subtrees, node E has completed traversal, and the subtree with node B as the root node is also The traversal is complete. Now go back to node A and start to traverse the right subtree of the node, that is, visit node C;
6) visit the left subtree of node C, and find node F;
7) because node F has no left and right subtrees, node F is traversed. Go back to node C and traverse its right subtree to find node G;
8) Node G has no left and right subtrees, so the subtree traversal with node C as the root node is completed, and node A is returned at the same time. The entire binary tree traversal is complete.

First-order traversal results:

A, B, D, E, C, F, G

Recursive implementation of pre-order traversal

Note: For node classes, the following three traversal methods use the same node class.
Node class:

/** * Node class * @param <E> Generic */ private static class Node < E > { E element; //Node data Node<E> left; //Left node Node<E> right; //Right node Node<E> parent; //Parent node-additional public Node (E element, Node<E> parent) { this .element = element; this .parent = parent; } } Copy code

First traverse the recursive code:

/** * First traverse the external api */ public void preOrder () { preOrderPrint(root); } /** * Specific implementation of first-order traversal-recursion */ private void preOrderPrint (Node<E> node) { if (node == null ) return ; //access subtree node data System.out.println(node.element); //Recursively traverse the left subtree preOrderPrint(node.left); //Recursively traverse the right subtree preOrderPrint(node.right); } Copy code

First-order traversal non-recursive implementation (stack structure)

The non-recursive pre-order traversal is completed with the help of the stack structure:
Put the root node into the stack;
Judging that the stack is empty, and get the output of the top element of the stack;
Judging whether the right subtree is empty, if it is not empty, then the right subtree will be pushed into the stack; judge again Whether the left subtree is empty, if not empty, the left subtree will be put on the stack, and go back to to execute.

The right subtree must be judged first, then the left subtree, because the stack rule is first-in-last-out, that is: the right subtree is pushed into the stack first, and the left subtree is pushed into the stack later. When accessing node data (popping), then Will first left subtree and then right subtree.

For the binary tree in the above figure, the traversal process is roughly as follows: The
first step: the root node (A) is pushed into the stack, and there is only node A in the stack at this time.

Step 2: The stack is not empty, visit the top element (A), pop the stack (node A pops the stack), and then judge the right and left subtrees of A successively, and then push them into the stack. At this time, there is node B (stack Top) and node C (bottom of stack).

Step 3: Repeat execution (judge whether the stack is empty, and pop out of the stack if it is not empty), access the top element of the stack (B), pop out of the stack (node B pops out of the stack), and then put the right subtree and the left subtree of B in sequence Stack, there are nodes D, E, and C in the stack at this time.

The fourth step is to repeat the execution....

The result of the final traversal is: A, B, D, E, C, F, G

First traverse non-recursive code:

/** * Specific implementation of first-order traversal-non-recursive * 1. Put the root node into the stack first, * 2. When the stack is not empty, perform the following operations in a loop: * 2.1 Visit the top node of the stack * 2.2 The right node of the top node of the stack is pushed into the stack * 2.3 The left node of the top node of the stack is pushed into the stack */ private void preOrderPrint2 () { if (root == null ) return ; Stack<Node<E>> stack = new Stack<>(); //1. The root node is pushed onto the stack stack.push(root); //Repeat the following operations when the stack is not empty while (!stack.isEmpty()) { //2. Visit the top node of the stack (pop out of the stack) Node<E> topNode = stack.pop(); System.out.println(topNode.element); //3. The right node of the top node of the stack is pushed into the stack (when the right node is not empty) if (topNode.right != null ) { stack.push(topNode.right); } //4. The left node of the top node of the stack is pushed into the stack (when the left node is not empty) if (topNode.left != null ) { stack.push(topNode.left); } } } Copy code


In-order traversal

The idea of in-order traversal:
1. Visit the left subtree of the current node;
2. Visit the root node;
3. Visit the right subtree of the current node.

The middle order traverses the left subtree and the root node, and the middle order traverses the right subtree.

Schematic diagram of binary tree in-order traversal:

The above figure uses the middle-order traversal process as follows:
1) Visit the root node of the binary tree and find A;
2) Traverse the left subtree of node A to find node B;
3) Traverse the left subtree of node B to find node D;
4) Since node D has no left child, find node D and traverse the right subtree
of node D ; 5) Since node D has no right subtree, the left subtree of node B is traversed, and node B is visited;
6) traverse Node B's right subtree, find node E;
7) Since node E has no left subtree, node E is visited, and because node E does not have a right subtree, the left subtree of node A is traversed, node A is visited, and Traverse the right subtree of node A and find node C;
8) traverse the left subtree of node C and find node F;
9) because node F has no left subtree, so visit node F, and because this node has no right subtree, Therefore, the traversal of the left subtree of node C is completed, start to visit node C, and traverse the right subtree of node C to find node G;
10) Since node G has no left subtree, node G is visited, and because this node has no right child Tree, so the right subtree of node A is traversed, that is, the entire tree is traversed;

Therefore, the result of using in-order traversal is:

D, B, E, A, F, C, G

Recursive implementation of mid-order traversal

In-order traversal code:

public void inOrder () { inOrderPrint(root); } /** * Specific implementation of middle order traversal */ public void inOrderPrint (Node<E> node) { if (node == null ) return ; //Recursively traverse the left subtree inOrderPrint(node.left); //Access subtree node data System.out.println(node.element); //Recursively traverse the right subtree inOrderPrint(node.right); } Copy code


In-order traversal non-recursive implementation (stack structure)

/** * Specific implementation of mid-order traversal-non-recursive, using stack implementation * 1. Put the root node on the stack first, set node = root; * 2. Put all the left children of the current node on the stack until the left child is empty * 3. Visit the top element of the stack, if the top element has a right child, continue to step 2 (the right subtree of the top element is pushed into the stack) * 4. Repeat steps 2 and 3 until the stack is empty and all nodes have been visited (end of loop) * * The above four steps are broken down into the code to understand as follows: * 1. Set node = root; * 2. If the node is not null or the stack is not empty, the following operations are executed in a loop: * If node! = null, put node on the stack, set node = node.left; * If node == null, pop the stack, visit the top element of the stack, and set node = node.right; */ public void inorderPrint2 () { if (root == null ) return ; Stack<Node<E>> stack = new Stack<>(); //Set node = root, the root node will be pushed onto the stack at the beginning of the while loop Node<E> node = root; while (node != null || !stack.isEmpty()) { //Push all the left subtrees of the current node into the stack (in the beginning, the root node will be pushed into the stack (node = root)) while (node != null ) { stack.push(node); node = node.left; } //Pop the stack to access the top element of the stack Node<E> headNode = stack.pop(); System.out.println(headNode.element); //Assign the right node of the top element of the stack to node, and execute the right child of the top element of the stack onto the stack node = headNode.right; } } Copy code


Post-order traversal

The idea of middle-order traversal:
Starting from the root node, traverse the left and right subtrees of each node in turn, and then visit the node element until the left and right subtrees of the current node are traversed.

Post-order traversal of the left sub-tree, post-order traversal of the right sub-tree, root node

Schematic diagram of post-order traversal of binary tree:

The post-order traversal of this binary tree is as follows:
1) Starting from the root node A, traverse the left subtree of the node (take node B as the root node);
2) traverse the left subtree of node B (take node D as the root node) Root node);
3) Since node D has neither a left subtree nor a right subtree, the element D in the node is accessed at this time, and it is returned to node B, and the right subtree of node B is traversed (take E as the root Node);
4) Since node E has no left and right subtrees, it can visit node E, and the left and right subtrees of node B are also traversed at this time, so node B can also be visited;
5) now go back to node A and start Traverse the right subtree of node A (take node C as the root node);
6) traverse the left subtree of node C (take node F as the root node);
7) Since node F has no left and right subtrees, visit node F, and Go back to node C and start traversing the right subtree of node C (with node G as the root node);
8) Since node G has no left and right subtrees, it visits node G, and the left and right subtrees of node C are also traversed. Visit node C; the left and right subtrees of node A are also traversed, and node A can be visited;
9) At this point, the traversal of the entire tree ends.

Therefore, the result of the post-order traversal is adopted:

D, E, B, F, G, C, A

Recursive implementation of post-order traversal

Post-order traversal code:

public void postorder () { postorderPrint(root); } /** * Specific implementation of post-order traversal-recursion */ public void postorderPrint (Node<E> node) { if (node == null ) return ; postorderPrint(root.left); postorderPrint(root.right); System.out.println(node.element); } Copy code


Sequence traversal

Traverse the nodes in each layer in turn from left to right according to the levels in the binary tree.

Visit each node in turn from top to bottom and left to right

Schematic diagram of binary tree sequence traversal:

Implementation Idea: Use Queues
By using the data structure of queues, starting from the root node of the tree, the left and right children are enqueued in sequence. Then every time a node in the queue leaves the team, its left child and right child are added to the team, until all nodes in the tree are dequeued, and the order of the leaving nodes is the final result of the hierarchy traversal.

  1. Enlist the root node A

  2. Perform the following operations in a loop until the queue is empty:
    dequeue the head node X for access;
    enqueue the left child node of
    X ; enqueue the right child node of X;

The above picture shows:
1. the root node A enters the team; the
root node A leaves the team, while leaving the team, the left child B and the right child C enter the team separately; the
head node B leaves the team at the same time as leaving the team , The left child D and right child E of node B enter the team in turn; the
head node C leaves the team, while leaving the team, the left child F and right child G of node C are entered into the team in turn;
continuously looping, Until the queue is empty.

Sequence traversal code:

/** * Sequence traversal */ public void levelOrder () { if (root == null ) return ;; Queue<Node<E>> queue = new LinkedList<>(); //The root node joins the team queue.offer(root); while (!queue.isEmpty()) { //The head of the queue leaves the queue Node<E> headNode = queue.poll(); //Access the head node data of the dequeue System.out.println(headNode.element); //Put the left and right children of the head node into the team in turn if (headNode.left != null ) { queue.offer(headNode.left); } if (headNode.right != null ) { queue.offer(headNode.right); } } } Copy code