遍历二叉树

二叉树的定义

/**
 * 二叉树
 * @param {any} val 
 * @param {BinaryTree} left 
 * @param {BinaryTree} right 
 */
function /*class*/ BinaryTree(val, left, right) {
    this.val = val;
    this.left = left || null;
    this.right = right || null;
}

二叉树的实例化

const root1 = new BinaryTree(
    0,
    new BinaryTree(
        1,
        new BinaryTree(3),
        new BinaryTree(7)
    ),
    new BinaryTree(
        2,
        new BinaryTree(4),
        new BinaryTree(
            5,
            new BinaryTree(6)
        )
    )
);

// root1
/*
                    root1(0)
        left(1)                right(2)
left(3)     right(7)     left(4)        right(5)
                                    left(6)

*/

const root2 = new BinaryTree(
    8,
    new BinaryTree(
        3,
        new BinaryTree(1),
        new BinaryTree(
            6,
            new BinaryTree(4),
            new BinaryTree(7)
        )
    ),
    new BinaryTree(
        10,
        null,
        new BinaryTree(
            14,
            new BinaryTree(13)
        )
    )
);

// root2
/*
                           root2(8)
        left(3)                           right(10)
left(1)         right(6)             null          right(14)
            left(4)     right(7)              left(13)        null
*/

遍历二叉树

前序遍历

// 对于前序遍历，首先遍历根节点，其次遍历左孩子，再遍历右孩子，按照如此的顺序遍历整棵树
function preOrder(tree) {
    if (tree) {
        console.log(tree.val);
        preOrder(tree.left);
        preOrder(tree.right);
    }
}

// preOrder(root1);
// 0 1 3 7 2 4 5 6
// preOrder(root2);
// 8 3 1 6 4 7 10 14 13

中序遍历

// 中序遍历，首先遍历左子树，其次遍历父节点，最后遍历右子树
function inOrder(root) {
    if (root) {
        inOrder(root.left);
        console.log(root.val);
        inOrder(root.right);
    }
}

// inOrder(root1);
// 3 1 7 0 4 2 6 5
// inOrder(root2);
// 1 3 4 6 7 8 10 13 14

后序遍历

// 后序遍历，首先遍历左子树，其次遍历右子树，最后遍历父节点
function postOrder(root) {
    if (root) {
        postOrder(root.left);
        postOrder(root.right);
        console.log(root.val);
    }
}

// postOrder(root1);
// 3 7 1 4 6 5 2 0
// postOrder(root2);
// 1 4 7 6 3 13 14 10 8

层次遍历

// 层次遍历，需要使用队列存储每一层的节点，同时，遍历完一个节点，将其左右子节点增加到队列中
function leverOrder(root) {
    const nodes = [root];

    let cur = nodes[0];
    while(nodes.length > 0) {
        console.log(cur.val);
        if (cur.left) nodes.push(cur.left);
        if (cur.right) nodes.push(cur.right);

        nodes.shift();
        cur = nodes[0];
    }
}

// leverOrder(root1);
// 0 1 2 3 7 4 5 6
// leverOrder(root2);
// 8 3 10 1 6 14 4 7 13