Preorder, inorder and postorder traversal of binary tree

One 、 Binary tree

Binary tree （binary tree） Refers to the degree of nodes in the tree No more than 2 The ordered tree of , Its nodes are divided into left and right subtrees .

Full binary tree ： If a binary tree has only a degree of 0 The node and degree of are 2 The node of , And the degree is 0 The nodes of are on the same layer , Then this binary tree is a full binary tree .

Perfect binary tree ： Leaf nodes can only appear in the lowest and lower layers , And the lowest leaf nodes are concentrated on the left of the tree .

Two 、 The generation of binary tree

function NodeTree (value) {
    this.value = value;
    this.left = null;
    this.right = null;
}

let root = new NodeTree('A');
let t1 = new NodeTree('B');
let t2 = new NodeTree('C');
let t3 = new NodeTree('D');
let t4 = new NodeTree('E');
let t5 = new NodeTree('F');

root.left = t1;
root.right = t2;
t1.left = t3;
t1.right = t4;
t2.left = t5;

console.log(root);

  The generated binary tree is as follows ：

 

3、 ... and 、 Traversal of binary tree

1、 The former sequence traversal

Preorder traversal is to traverse the root node first , Then traverse the left subtree , Finally, traverse the right subtree , namely root —> Left —> Right

The code is as follows ：

/**
 *  The former sequence traversal 
 * @param {NodeTree} root 
 */
let formerSequenceTraversal = function (root) {
    if (!root || root.value === null) {
        return null;
    }
    console.log(root.value);
    formerSequenceTraversal(root.left);
    formerSequenceTraversal(root.right);
}

The output is as follows ：

A、B、D、E、C、F

2、 In the sequence traversal

Middle order traversal is to traverse the left subtree first , Then traverse the root node , Finally, traverse the right subtree , namely Left —> root —> Right

The code is as follows ：

/**
 *  In the sequence traversal 
 * @param {NodeTree} root 
 */
let middleSequenceTraversal = function (root) {
    if (!root || root.value === null) {
        return null;
    }
    middleSequenceTraversal(root.left);
    console.log(root.value);
    middleSequenceTraversal(root.right);
}

The output is as follows ：

D、B、E、A、F、C

3、 After the sequence traversal

Post order traversal is to traverse the left subtree first , Traversing right subtree again , Finally, traverse the root node , namely Left —> Right —> root

The code is as follows ：

/**
 *  After the sequence traversal 
 * @param {NodeTree} root 
 */
let afterSequenceTraversal = function (root) {
    if (!root || root.value === null) {
        return null;
    }
    afterSequenceTraversal(root.left);
    afterSequenceTraversal(root.right);
    console.log(root.value);
}

The output is as follows ：

D、E、B、F、C、A