Preorder traversal, inorder traversal and postorder traversal of binary trees

Article directory

• 0 Preface
• 1 binary tree
• • 1.1 Definition
  • 1.2 Features
• 2 Preorder traversal
• 3 In-order traversal
• 4 Postorder traversal
• 5 Summary

0 Introduction

This article mainly studies binary trees in data structures, including three commonly used traversal methods: pre-order traversal, in-order traversal and post-order traversal.

1 Binary tree

1.1 Definition

Binary tree is a common tree-like data structure, which consists of nodes. Each node has at most two child nodes, called left child node and right child node. Each node can store a value or other related information.

1.2 Features

1. Each node has at most two child nodes, and the order of the left child node and the right child node is fixed. The left child node is located on the left side of the parent node, and The right child node is located on the right side of the parent node. This structure can visually represent many problems, such as tree structures, ordered lists, etc.
2. Binary trees can be empty, that is, there are no nodes. If a node has no child nodes, it is called a leaf node or terminal node. Every node, except leaf nodes, has a parent node, and every node, except the root node, has a unique parent node.
3. Binary trees can have different special forms, such as Binary Search Tree (Binary Search Tree), in which the value of the left child node is less than or equal to the value of the parent node, and the value of the right child node is less than or equal to the value of the parent node. The value is greater than or equal to the value of the parent node. There is also a Balanced Binary Tree (Balanced Binary Tree), in which the height difference between the left subtree and the right subtree does not exceed one.
4. Binary tree traversal refers to visiting the nodes in the tree in a certain order. Common traversal methods include Pre-order traversal (Pre-order), In-order traversal (In-order) , Post-order traversal (Post-order). These traversal methods can help us effectively process nodes in binary trees.

2 Preorder traversal

Pre-order traversal (Pre-order traversal) is a method of binary tree traversal, which visits the nodes in the binary tree in the order of the root node, left subtree, and right subtree.

Specifically, the steps of preorder traversal are as follows:

1. Visit the current node (root node).
2. Recursively traverse the left subtree in preorder.
3. Recursively traverse the right subtree in preorder.

Preorder traversal can be implemented using recursion or iteration.

The pseudocode for recursively implementing preorder traversal is as follows:

preorderTraversal(node):
    if node is null:
        return
    Access the current node (output the value of the node or perform other operations)
    preorderTraversal(node.left) # Recursive preorder traversal of the left subtree
    preorderTraversal(node.right) # Recursive preorder traversal of the right subtree

Iterative implementation of preorder traversal is usually accomplished using the stack (Stack) data structure. The algorithm steps are as follows:

1. Create an empty stack and push the root node onto the stack.
2. When the stack is not empty, perform the following operations:
   • Pop the top node of the stack and access the node (output the value of the node or perform other operations).
   • Push the right child node (if it exists) onto the stack.
   • Push the left child node (if it exists) onto the stack.
   • Note: Since the stack is a last-in-first-out (LIFO) data structure, the right child node is pushed into the stack first, and then the left child node is pushed into the stack to ensure that the left child node is on the right The child node has been visited before.

The pseudocode for iterative implementation of preorder traversal is as follows:

preorderTraversal(node):
    if node is null:
        return
    Create an empty stack
    Push the root node onto the stack
    while stack is not empty:
        Pop the top node from the stack and access it
        If the right child node of the node is not empty, push the right child node onto the stack
        If the left child node of the node is not empty, push the left child node onto the stack

Regardless of whether it is recursive or iterative, preorder traversal will traverse the nodes in the binary tree in the order of the root node, left subtree, and right subtree. This traversal method is very useful in solving certain problems, such as copying a binary tree, evaluating expressions, etc.

3 In-order traversal

In-order traversal (In-order traversal) is a way of traversing a binary tree. It visits the nodes in the binary tree in the order of left subtree, root node, and right subtree. .

Specifically, the steps for in-order traversal are as follows:

1. Recursively traverse the left subtree in inorder.
2. Visit the current node (root node).
3. Recursively traverse the right subtree in inorder.

In-order traversal can be implemented using recursion or iteration.

The pseudocode for recursive implementation of in-order traversal is as follows:

inorderTraversal(node):
    if node is null:
        return
    inorderTraversal(node.left) # Recursive inorder traversal of the left subtree
    Access the current node (output the value of the node or perform other operations)
    inorderTraversal(node.right) # Recursive inorder traversal of the right subtree

Iterative implementation of in-order traversal usually uses the stack (Stack) data structure to assist in completing it. The algorithm steps are as follows:

1. Create an empty stack.
2. Initialize the current node as the root node.
3. When the stack is not empty or the current node is not empty, perform the following operations:
   • Push the current node and all its left child nodes onto the stack in sequence until the current node is empty.
   • Pop the top node of the stack and access the node (output the value of the node or perform other operations).
   • Point the current node to the right child of the popup node.

The pseudocode for iterative implementation of in-order traversal is as follows:

inorderTraversal(node):
    Create an empty stack
    Initialize the current node as the root node
    while The stack is not empty or the current node is not empty:
        Push the current node and all its left child nodes onto the stack in sequence until the current node is empty
        Pop the top node from the stack and access it
        Point the current node to the right child node of the popup node

Whether implemented recursively or iteratively, in-order traversal traverses the nodes in the binary tree in the order of left subtree, root node, and right subtree. Inorder traversal is often used to sort binary search trees. It can also be used to find nodes in a binary tree or perform other operations related to node order.

4 Postorder traversal

Post-order traversal (Post-order traversal) is a method of binary tree traversal. It visits the nodes in the binary tree in the order of left subtree, right subtree, and root node. .

Specifically, the steps for post-order traversal are as follows:

1. Recursively traverse the left subtree in postorder.
2. Recursively traverse the right subtree in postorder.
3. Visit the current node (root node).

Postorder traversal can be implemented using recursion or iteration.

The pseudocode for recursively implementing post-order traversal is as follows:

postorderTraversal(node):
    if node is null:
        return
    postorderTraversal(node.left) # Recursive postorder traversal of the left subtree
    postorderTraversal(node.right) # Recursive postorder traversal of the right subtree
    Access the current node (output the value of the node or perform other operations)

Iterative implementation of post-order traversal usually uses the stack (Stack) data structure to assist in completing it. The algorithm steps are as follows:

1. Create two stacks, one to store nodes and the other to store the results of postorder traversal.
2. Initialize the current node as the root node and push it onto the stack.
3. When the node stack is not empty, perform the following operations:
   • Pop the top node from the stack and push it into the result stack.
   • If the left child node of the popped node is not empty, put the left child node into the node stack.
   • If the right child node of the popped node is not empty, put the right child node into the node stack.
4. When the node stack is empty, all nodes have been traversed. Pop the nodes in the result stack one by one, which is the result of post-order traversal.

The pseudo code for iterative implementation of post-order traversal is as follows:

postorderTraversal(node):
    Create a node stack
    Create a result stack
    Add the root node to the node stack
    while node stack is not empty:
        Pop the top node from the stack and push it onto the result stack
        If the left child node of the popped node is not empty, put the left child node into the node stack.
        If the right child node of the popped node is not empty, put the right child node into the node stack
    while result stack is not empty:
        Pop the top node of the result stack and access the node (output the value of the node or perform other operations)

Regardless of whether it is recursive or iterative, post-order traversal will traverse the nodes in the binary tree in the order of left subtree, right subtree, and root node. Post-order traversal is often used in scenarios such as releasing memory resources of binary trees, calculating the value of expressions, etc. It can also be used to perform other operations related to node order.

5 Summary

Preorder traversal: root node->left subtree->right subtree

In-order traversal: left subtree->root node->right subtree

Post-order traversal: left subtree->right subtree->root node

Take the following binary tree as an example, detailed steps of preorder traversal:

1. The first two levels have only one root node 0, and the traversal result is: 0->1->2
2. Adding the third layer, there are two root nodes 1,2, and the traversal results are: 1->3->4 and 2->5->6 , combined with the previous step, that is, 3,4 is added after 1, and 5,6 is added After 2, the traversal result is: 0->1->3->4->2->5->6
3. Adding the fourth layer, there are two more root nodes 3,4, and the traversal results are: 3->7->8 and 4->9 code>, combined with the previous step, that is, 7,8 is added after 3, and 9 is added after After 4, the traversal result: 0->1->3->7->8->4->9->2->5->6

Detailed steps of in-order traversal:

1. The first two levels have only one root node 0, and the traversal result is: 1->0->2
2. Adding the third layer, there are two root nodes 1,2, and the traversal results are: 3->1->4 and 5->2->6 , combined with the previous step, that is, 3,4 are added before and after 1, 5,6 code> is also added before and after 2, and the traversal result is: 3->1->4->0->5->2->6
3. Adding the fourth layer, there are two more root nodes 3,4, and the traversal results are: 7->3->8 and 9->4 code>, combined with the previous step, that is, 7,8 are added before and after 3 respectively, and 9 is added after The front of 4, the traversal result: 7->3->8->1->9->4->0->5->2->6

Detailed steps of post-order traversal:

1. The first two levels have only one root node 0, and the traversal result is: 1->2->0
2. Adding the third layer, there are two root nodes 1,2, and the traversal results are: 3->4->1 and 5->6->2 , combined with the previous step, that is, 3,4 is added in front of 1, and 5,6 is added In front of 2, the traversal result is: 3->4->1->5->6->2->0
3. Adding the fourth layer, there are two more root nodes 3,4, and the traversal results are: 7->8->3 and 9->4 code>, combined with the previous step, that is, 7,8 is added in front of 3, and 9 is added in front of The front of 4, the traversal result: 7->8->3->9->4->1->5->6->2->0
   

It should be noted that when he was young, Ling Yunzhi once promised to be the best in the world.

? ?