二叉树的先序、中序、后序遍历（代码实现）

先序遍历

先序遍历的访问顺序为：根节点→左节点→右节点（根左右）

所以下图的访问顺序为：A B D E C F

递归实现

/* 
  二叉树的遍历
            A
          /   \
          B     C
        /   \   /
        D   E  F   
  
  先序遍历：根左右  A B D E C F
  中序遍历：左根右  D B E A F C
  后序遍历：左右根  D E B F C A
*/

function TreeNode(val) {
	this.val = val
	this.left = this.right = null
}

const A = new TreeNode('A')
const B = new TreeNode('B')
const C = new TreeNode('C')
const D = new TreeNode('D')
const E = new TreeNode('E')
const F = new TreeNode('F')

A.left = B
A.right = C
B.left = D
B.right = E
C.left = F

let result = []

// 先序遍历 递归
function preOrder(tree) {
    // 终止条件
    if (!tree) return;
    
    // 开始遍历
    result.push(tree.val) // 根
    preOrder(tree.left) // 左
    preOrder(tree.right) // 右
}

// 测试
preOrder(A)
console.log(result); // [ 'A', 'B', 'D', 'E', 'C', 'F' ]

非递归实现

function preOrder(root) {
    if (!root) return

    let stack = [root]

    let result = [] // 存放遍历结果

    while (stack.length > 0) {
        // 出栈
        let cur = stack.pop()

        if (cur !== null) {

            // 先序遍历是 根左右 所以入栈顺序 就是  右左根（因为栈是先入后出的）
            cur.right !== null && stack.push(cur.right) // 右
            cur.left !== null && stack.push(cur.left) // 左

            stack.push(cur) // 根
            stack.push(null) // 增加一个标识位，当pop出的是这个标识位，说明栈顶的节点需要处理了

        } else { // 当出栈的是 null 的时候，说明是等待处理的节点，我们增加的表示位

            cur = stack.pop() // 再pop一个栈顶的节点 就是待处理的结果
            // 逻辑都写在这里
            result.push(cur.val)
        }
    }

    return result
}

console.log(preOrder(A)); // [ 'A', 'B', 'D', 'E', 'C', 'F' ]

中序遍历

中序遍历的访问顺序为：左子树→根节点→右子树（左根右）

所以下图的访问顺序为：D B E A F C

递归实现

let result = []

// 先序遍历 递归
function inOrder(tree) {
    // 终止条件
    if (!tree) return;

    // 开始中序遍历 左根右
    preOrder(tree.left) // 左
    result.push(tree.val) // 根
    preOrder(tree.right) // 右
}

// 测试
preOrder(A)
console.log(result); // [ 'D', 'B', 'E', 'A', 'F', 'C' ]

非递归实现

function inOrder(root) {
    if (!root) return

    let stack = [root]

    let result = [] // 存放遍历结果

    while (stack.length > 0) {
        // 出栈
        let cur = stack.pop()

        if (cur !== null) {

            // 中序遍历是 左根右 所以入栈顺序 就是  右根左（因为栈是先入后出的）
            cur.right !== null && stack.push(cur.right) // 右

            stack.push(cur) // 根
            stack.push(null) // 增加一个标识位，当pop出的是这个标识位，说明栈顶的节点需要处理了

            cur.left !== null && stack.push(cur.left) // 左

        } else { // 当出栈的是 null 的时候，说明是等待处理的节点，我们增加的表示位

            cur = stack.pop() // 再pop一个栈顶的节点 就是待处理的结果
            // 逻辑都写在这里
            result.push(cur.val)
        }
    }

    return result
}

console.log(inOrder(A)); // [ 'D', 'B', 'E', 'A', 'F', 'C' ]

后序遍历

中序遍历的访问顺序为：左子树→右子树→根节点（左右根）

所以下图的访问顺序为：D E B F C A

递归实现

let result = []

// 后序遍历 递归
function postOrder(tree) {
    if (!tree) return;

    // 开始遍历 左右根
    postOrder(tree.left) // 左
    postOrder(tree.right) // 右
    result.push(tree.val) // 根

}

// 测试
postOrder(A)
console.log(result); // [ 'D', 'E', 'B', 'F', 'C', 'A' ]

非递归

function postOrder(root) {
    if (!root) return

    let stack = [root]

    let result = [] // 存放遍历结果

    while (stack.length > 0) {
        // 出栈
        let cur = stack.pop()

        if (cur !== null) {

            // 后序遍历是 左右根 所以入栈顺序 就是  根右左（因为栈是先入后出的）

            stack.push(cur) // 根
            stack.push(null) // 增加一个标识位，当pop出的是这个标识位，说明栈顶的节点需要处理了

            cur.right !== null && stack.push(cur.right) // 右
            cur.left !== null && stack.push(cur.left) // 左

        } else { // 当出栈的是 null 的时候，说明是等待处理的节点，我们增加的表示位

            cur = stack.pop() // 再pop一个栈顶的节点 就是待处理的结果
            // 逻辑都写在这里
            result.push(cur.val)
        }
    }

    return result
}

console.log(postOrder(A)); // [ 'D', 'E', 'B', 'F', 'C', 'A' ]

参考

数据结构-6,树