二叉樹的數(shù)據(jù)結構在js中可以如此表示:

const tree = {
    value: 1,
    left: {
        value: 2,
        left: {
            value: 4,
            left: {
                value: 8
            },
            right: {
                value: 9
            }
        },
        right: {
            value: 5
        }
    },
    right: {
        value: 3,
        left: {
            value: 6
        },
        right: {
            value: 7
        }
    }
}

我們分別采用深度和廣度遍歷一遍：

深度優(yōu)先

此處就使用前序遍歷了

遞歸實現(xiàn)

function dfsRecursion(tree) {
    let res = [];
    function dfs(node){
        if(node) {
            res.push(node.value);
            dfs(node.left);
            dfs(node.right);
        }
    }
    dfs(tree);
    return res;
}

非遞歸實現(xiàn)

/**
 * @param tree 
 * 非遞歸實現(xiàn)，需要自行實現(xiàn)“回溯”，可以使用棧來巧妙實現(xiàn)
 * 將某個節(jié)點的右節(jié)點、左節(jié)點依次壓倒棧中，會先消費該左節(jié)點，再次將其右子節(jié)點、左子節(jié)點壓入棧...
 */
function dfsNonRecursion(tree) {
    let arr = [];
    let res = [];
    arr.push(tree);
    while (arr.length) {
        const node = arr.pop();
        res.push(node.value);
        if (node.right) {
            arr.push(node.right);
        }
        if (node.left) {
            arr.push(node.left);
        }
    }
    return res
}

廣度優(yōu)先

function bfs(tree) {
    let res = [];
    let arr = [];
    arr.push(tree);
    while(arr.length) {
        const node = arr.shift();
        res.push(node.value);
        if(node.left) {
            arr.push(node.left);
        }
        if(node.right) {
            arr.push(node.right);
        }
    }
    return res;
}