树的深度优先遍历

二叉树的遍历(递归版)

一个树结构:

var tree = {
        value: 3,
        left: {
            value: 9,
            left: null,
            right: null
        },
        right: {
            value: 20,
            left: {
                value: 15,
                left: null,
                right: null
            },
            right: {
                value: 7,
                left: null,
                right: null
            }
        }
    }

1. 先序遍历(根 左 右)

function xian(root) {
        if (!root) return
        console.log(root.value)
        xian(root.left)
        xian(root.right)
    }
    xian(tree) // 3 9 20 15 7

2. 中序遍历(左 根 右)

function xian(root) {
        if (!root) return
        xian(root.left)
        console.log(root.value)
        xian(root.right)
    }
    xian(tree)// 9 3 15 20 7

3. 后续遍历(左 右 根)

function xian(root) {
            if (!root) return
            xian(root.left)
            xian(root.right)
            console.log(root.value)
        }
        xian(tree) // 9 15 20 7 3

通过二叉树的先序遍历对递归的理解:

1. 给调用函数的地方打上断点

2. 点击执行一步
3. 此时函数调用栈中有一个xian函数,参数的值:root={left: {value: 9, left: null, right: null}right: {value: 20, left: {…}, right: {…}}value: 3}
4. 函数执行到699行,又会往函数调用栈里面push一个(1)xian(root.left) root= {left: null,right: null,value: 9},但是上一个函数还没有执行完,①xian(root.right)还没有执行到,后面会调用①
5. 继续执行,又会执行(2)xian(root.left) root = {root: null}
6. 执行(2) 会直接return 函数调用栈会弹出(2),然后又会往函数调用栈里push一个函数 ②xian(root.right) 由于root = null 也直接return
7. ……….就一直压栈,出栈,可以利用goole的调试工具细看,实在是描述不出来……