二叉树先中后遍历

By bobo 2021-12-26 18:50:08 文章分类:JavaScript

先序遍历

const bt = require('./bt')
/**
 * 先序遍历算法口诀
 * 1.访问 根 节点
 * 2.对根节点的 左 子树进行先序遍历
 * 3.对根节点的 右 子树进行先序遍历
 */

/**
 * 先序遍历
 * 根 - 左 - 右
 * @param {*} root 
 * @returns 
 */
function preorder(root) {
    if (!root) return
    // 1.访问 根 节点
    console.log(root.val)

    // 2.对根节点的 左 子树进行先序遍历
    preorder(root.left)

    // 3.对根节点的 右 子树进行先序遍历
    preorder(root.right)
}


/*
        1
     /   \
    2     3
   / \    / \
  4   5  6   7
*/
// preorder(bt) // 1,2,4,5,3,6,7

// 非递归版本
function preorder(root) {
    if (!root) return

    const stack = [root]

    /**
     * 出栈就是输出
     * 
     * 第一次入栈,stack: [1]
     * 出栈1,statck: []
     * 入栈右左 ,stack: [3,2]
     * 出栈2:stack: [3]
     * 入栈右左:stack[3,5,4]
     * 出栈4:stack: [3,5]
     * 出栈5: stack: [3]
     * 出栈3: stack: []
     * 入栈右左:stack: [7,6]
     * 出栈6: stack: [7]
     * 出栈7: stack: []
     */
    while (stack.length) {
        const node = stack.pop()
        // 1.访问 根 节点
        console.log(node.val)

        // 3.对根节点的 右 子树进行先序遍历
        if (node.right) {
            stack.push(node.right)
        }

        // 栈 - 后进先出
        // 2.对根节点的 左 子树进行先序遍历
        if (node.left) {
            stack.push(node.left)
        }
        // 循环一次得到的栈:stack: [right, left]
    }
}

preorder(bt) // 1,2,4,5,3,6,7

中序遍历

/**
 * 中序遍历算法口诀
 * 1.对根节点的左子树进行中序遍历
 * 2.访问根节点
 * 3.对根节点的右子树进行中序遍历
 */

const bt = require('./bt')

/**
 * 中序遍历
 * 左-根-右
 * 
 * @param {*} root 
 * @returns 
 */
function inorder(root) {
    if (!root) return

    // 1.对根节点的左子树进行中序遍历
    inorder(root.left)

    // 2.访问根节点
    console.log(root.val)

    // 3.对根节点的右子树进行中序遍历
    inorder(root.right)
}

/*
       1
     /   \
    2     3
   / \   / \
  4  5  6   7
*/
// inorder(bt) // 4,2,5,1,6,3,7

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

    const stack = []
    let p = root;

    /**
     * 入栈1:stack: [1]
     * 入栈1左节点2: stack: [1,2] p =2
     * 入栈2左节点4: stack: [1,2,4]
     *  4下无right节点,p = null,第二个while循环结束,
     * 出栈4:stack: [1,2], 
     * 出栈2,stack: [1], 2下存在right节点,p = 5
     * 入栈5,stack: [1,5], 5下无right节点,p=null
     * 出栈5, stack: [1]
     * 出栈1,stack: [], p = 3
     * 入栈3,stack: [3]
     * 入栈6,stack: [3,6]
     * 出栈6,stack: [3], 6下无节点
     * 出栈3,stack: [3], 3下有节点:p = 7
     * 出栈7
     */


    while (stack.length || p) {
        // 这个 while 的作用是把寻找最左叶子结点的过程中,途径的所有结点都记录下来 
        while (p) {
            stack.push(p)
            // 1.对根节点的左子树进行中序遍历
            p = p.left
        }

        const node = stack.pop()
        // 2.访问根节点
        console.log(node.val)
        // 3.对根节点的右子树进行中序遍历
        p = node.right
    }
}

inorder(bt) // 4,2,5,1,6,3,7

后序遍历

/**
 * 后序遍历算法口诀
 * 1.对根节点的左子树进行后序遍历
 * 2.对根节点的右子树进行后序遍历
 * 3.访问根节点
 */
const bt = require('./bt')

/**
 * 后序遍历
 * 左-右-根
 * 
 * @param {*} root 
 * @returns 
 */
function postorder(root) {
    if (!root) return

    // 1.对根节点的左子树进行后序遍历
    postorder(root.left)

    // 2.对根节点的右子树进行后序遍历
    postorder(root.right)

    // 3.访问根节点
    console.log(root.val)
}


/*
       1
     /   \
    2     3
   / \   / \
  4  5  6   7
*/
// postorder(bt) // 4,5,2,6,7,3,1

// 非递归版本
function postorder(root) {
    if (!root) return

    const stack = [root]
    const outputStack = []

    /**
     * 入栈:stack: [1]
     * 出栈1,stack: []
     * 入栈1左右节点:stack: [2,3]
     * 出栈3:stack: [2]
     * 入栈3左右节点:stack: [2,6,7]
     * 出栈7: stack: [2,6]
     * 出栈6: stack: [2]
     * 出栈2: stack: []
     * 入栈2的左右节点:stack: [4,5]
     * 出栈5: stack: [4]
     * 出栈4: stack: []
     * 
     * 出栈即是 outputStack 入栈
     * 最后 outputStack 分别出栈输出
     */

    while (stack.length) {
        const node = stack.pop()
        outputStack.push(node)

        // 1.对根节点的左子树进行后序遍历
        if (node.left) {
            stack.push(node.left)
        }
        // 2.对根节点的右子树进行后序遍历
        if (node.right) {
            stack.push(node.right)
        }
    }

    while (outputStack.length) {
        // 3.访问根节点
        const node = outputStack.pop()
        console.log(node.val)
    }
}

postorder(bt) // 4,5,2,6,7,3,1