中序遍历.md

/**
 *         A 
 *      B    C
 *    D  E  F  G
 * 
 *  D B E A F C G
 * 
 * */ 

const root = {
    val: 'A',
    left: {
        val: 'B',
        left: {
            val: 'D',
            left: null,
            right: null
        },
        right: {
            val: 'E', 
            left: null,
            right: null
        },
    },
    right: {
        val: 'C', 
        left: {
            val: 'F',
            left: null,
            right: null
        },
        right: {
            val: 'G',
            left: null,
            right: null
        }
    }
}

function inorder(root) {
    if (!root) return 
    inorder(root.left)
    console.log(root.val)
    inorder(root.right)
}

inorder(root)  // D B E A F C G

// 非递归
// 利用栈
function inorder2(root) {
    const stack = []
    while (true) {
        while (root) {
            // 先将根结点压入栈中
            stack.push(root)
            // 然后循环遍历左子树， 直到左子树为 null
            root = root.left
        }
        if (!stack.length) return
        // 取出栈顶的结点
        const top = stack.pop()
        console.log(top.val)
        // 然后再看栈顶的结点是否有右子树，若没有，则继续取出栈顶结点，若有，则会继续循环 while, 将右子树结点压入栈中，继续遍历左子树
        root = top.right
    }
}

inorder2(root)  // D B E A F C G