Data Structures and Algorithms – Basics (8) Traversal binary trees

“This is my seventh day of the November Gwen Challenge.The final text challenge in 2021”

Abstract

Traversal binary tree is the basic operation of binary tree, later more logical other binary tree should be often applied to traversal mode. Second, the idea of recursion and its application to queues can be understood by traversing the binary tree.

Traversal is a common operation in data structures, where all elements are iterated through. There are no more than two kinds of traversal of linear structures, positive traversal and reverse traversal, that is, traversal from the beginning or from the end.

Traversal of a binary tree is to traverse from the root node to the leaf node, and each node has its left or right subtree in addition to itself. Therefore, different traversal methods are defined according to the traversal of these three nodes in different order.

There are four traversal modes, which are distinguished according to different node access sequences:

From the table above, it can be roughly concluded that the difference between the first three traversals is the order of accessing these three nodes. Both left and right subtrees can be regarded as a whole (such as a node), and the first node itself can also be regarded as the root node of the subtree range. Therefore, traversing the subtree means continuously treating the subtree as a new binary tree until the leaf node is traversed.

According to the above logical sorting, you can use the recursive way to pre-order traversal, mid-order traversal and post-order traversal.

Note: When recursion is used, a condition must be determined to end recursion, because the binary tree traversal starts from the root node until all nodes are traversed, so the condition to end recursion is null node.

// End recursion condition if (node == null) return;Copy the code

The order of the preceding traversal is the root node, the left subtree, and finally the right subtree

public void preorderTanversal() { preorderTanversal(root, visitor); } private void preorderTanversal(Node<E> Node) {if (Node == null) return; // Access the root node system.out.println (node.element); // Call left subtree preorderTanversal(node. Left, visitor); // Call right subtree preorderTanversal(node.right, visitor); }Copy the code

The middle order traversal is the left subtree, the root node, and finally the right subtree

/ / public void inorderTraversal() {void inorderTraversal(); } private void inorderTraversal(Node<E> Node) {if (Node == null) return; InorderTraversal (node. Left, visitor); // Access the root node system.out.println (node.element); // Access right subtree inorderTraversal(node.right, visitor); }Copy the code

In particular, middle-order traversal is to visit the left subtree or the right subtree first, depending on the mood, as long as the root node is accessed in the middle.

The order of the back-order traversal is left subtree, right subtree, and finally root node:

Public void postorderTraversal() {return traversal () {return traversal (); } private void postorderTraversal(Node<E> Node) {if (Node == null) return; // Access left traversal (node. Left, visitor); // Access the right subtree postorderTraversal(node.right, visitor); // Access the root node system.out.println (node.element); }Copy the code

Sequential traversal is accessed from top to bottom and left to right. That is, the binary tree from the root node to the leaf node structure, each layer of nodes from left to right traversal completed. This traversal mode has a point that must be paid attention to, that is, until traversal of one layer, nodes of the next layer cannot be traversed.

As it happens, the FIFO mode of the queue structure ensures that the absolute order of the elements in the sequence is not broken, and that there is only one entry and exit. So you can queue up all the nodes in a binary tree from the root to the leaf and out at the other end. At the same time, it can also add its left and right child nodes to the queue, which does not affect the node order in the current sequence. It can be perfect.

In this case, we only need to pay attention to the process of enqueuing the left and right subtrees of the node successively, i.e. enqueuing if there is one, and enqueuing if there is no one. If the number of elements in the queue is null, the traversal is completed.

public void leverOrderTraversal() { if (root == null) return; Queue<Node<E>> Queue = new LinkedList<>(); Queue.offer (root); // Queue. while (! Queue.isempty ()) {// Handle the event Node<E> Node = queue.poll(); System.out.println(node.element); If (node.left! = null) { queue.offer(node.left); } if (node.right ! = null) { queue.offer(node.right); }}}Copy the code

Sequential traversal is a very useful traversal method, later in the calculation of the height of the binary tree, or to determine whether or not a complete binary tree, so it is very important to understand the use of queue processing.