How to implement binary tree traversal using Python

As a commonly used data structure, binary trees are often used to store data, search and sort. Traversing a binary tree is one of the very common operations. As a simple and easy-to-use programming language, Python has many methods to implement binary tree traversal. This article will introduce how to use Python to implement pre-order, in-order and post-order traversal of a binary tree.

Basics of Binary Trees

Before learning how to traverse a binary tree, we need to understand the basic concepts of a binary tree. A binary tree consists of nodes, each node has a value and two children (left child and right child). A node's children can be empty.

Binary tree traversal

Binary tree traversal refers to visiting all nodes in the binary tree in a certain order. There are three commonly used traversal methods: pre-order traversal, in-order traversal and post-order traversal.

Preorder traversal

The order of preorder traversal is the root node, left subtree, and right subtree. In specific implementation, you can first output the value of the root node, and then recursively traverse the left subtree and right subtree.

The following is the Python code implementation:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def preorderTraversal(root: TreeNode):
    if root is None:
        return []
    res = [root.val]
    res += preorderTraversal(root.left)
    res += preorderTraversal(root.right)
    return res

In-order traversal

The order of in-order traversal is left subtree, root node, and right subtree. In specific implementation, it is necessary to recursively traverse the left subtree, output the value of the root node, and then recursively traverse the right subtree.

The following is the Python code implementation:

def inorderTraversal(root: TreeNode):
    if root is None:
        return []
    res = []
    res += inorderTraversal(root.left)
    res.append(root.val)
    res += inorderTraversal(root.right)
    return res

Post-order traversal

The order of post-order traversal is left subtree, right subtree, and root node. In specific implementation, it is necessary to recursively traverse the left subtree and right subtree, and finally output the value of the root node.

The following is the Python code implementation:

def postorderTraversal(root: TreeNode):
    if root is None:
        return []
    res = []
    res += postorderTraversal(root.left)
    res += postorderTraversal(root.right)
    res.append(root.val)
    return res

Summary

In Python, when using binary tree traversal, you can achieve pre-order, mid-order and post-order traversal through recursion . In addition to recursion, it can also be implemented using methods such as stack and breadth-first search. Mastering the method of binary tree traversal will be very useful for daily programming work.

The above is the detailed content of How to implement binary tree traversal using Python. For more information, please follow other related articles on the PHP Chinese website!