This is the sixth day of my participation in the August More Text Challenge. For details, see “August More Text Challenge”.

The previous chapter introduced the basic concepts of trees and briefly talked about depth-first and breadth-first traversals.

This chapter will introduce another tree structure binary tree, and talk about its first and second order traversal.

Binary tree

  • Each node in the tree can have at most two child nodes.

  • Below is a real binary tree with two byte points under each node. To be honest, I admire the photographer, he actually found a real binary tree in real life.

  • inJSBe showedObjectTo simulate a binary tree. The following code:
const binaryTree = {
    val: 1,
    left: {
        val: 2,
        left: null,
        right: null
    }
    right: {
        val: 3,
        left: null,
        right: null}}Copy the code

Is a simple binary tree simulated by JS Object.

The first sequence traversal

  • Access the root node.

  • Preorder traversal of the left subtree of the root node.

  • Preorder traversal of the right subtree of the root node.

The code is as follows:

const binaryTree = {
    val: 1,
    left: {
        val: 2,
        left: {
            val: 3,
            left: null,
            right: null
        },
        right: {
            val: 4,
            left: {
                val: 5,
                left: null,
                right: null
            },
            right: null
        }
    },
    right: {
        val: 6,
        left: null,
        right: {
            val: 7,
            left: null,
            right: null}}}Copy the code

To perform sequence traversal:

const preorder = (root) => {
    if(! root)return
    console.log(root.val)
    preorder(root.left)
    preorder(root.right)
}

preorder(binaryTree)

// 1 2 3 4 5 6 7
Copy the code

In the sequence traversal

  • Perform in-order traversal of the left subtree of the root node.

  • Access the root node.

  • Perform in-order traversal of the right subtree of the root node.

The code is as follows:

const binaryTree = {
    val: 5,
    left: {
        val: 2,
        left: {
            val: 1,
            left: null,
            right: null
        },
        right: {
            val: 4,
            left: {
                val: 3,
                left: null,
                right: null
            },
            right: null
        }
    },
    right: {
        val: 6,
        left: null,
        right: {
            val: 7,
            left: null,
            right: null}}}Copy the code

Ongoing order traversal:

const inorder = (root) => {
    if(! root)return
    inorder(root.left)
    console.log(root.val)
    inorder(root.right)
}

inorder(binaryTree)
// 1 2 3 4 5 6 7
Copy the code

After the sequence traversal

  • Perform in-order traversal of the left subtree of the root node.

  • Perform in-order traversal of the right subtree of the root node.

  • Access the root node.

The code structure is as follows:

const binaryTree = {
    val: 7,
    left: {
        val: 4,
        left: {
            val: 1,
            left: null,
            right: null
        },
        right: {
            val: 3,
            left: {
                val: 2,
                left: null,
                right: null
            },
            right: null
        }
    },
    right: {
        val: 6,
        left: null,
        right: {
            val: 5,
            left: null,
            right: null}}}Copy the code

Perform a post-order traversal:

const postorder = (root) => {
    if(! root)return
    postorder(root.left)
    postorder(root.right)
    console.log(root.val)
}

postorder(binaryTree)
// 1 2 3 4 5 6 7
Copy the code

End~~~