Javascript 与算法之树

树

树是一种分层数据的抽象模型。例如：DOM树、树形控件等。

Javascript 中没有树，但是可以用 Object 和 Array 构建树。

树的常用操作：深度/广度优先遍历、先中后序遍历。

树的深度/广度优先遍历

深度优先遍历

定义：从根节点，尽可能深的搜索树的分支。
遍历算法：访问根节点，对根节点的 children 挨个进行深度优先遍历。

遍历代码：

const dfs = (root) => {
    console.log(root);
    root.children.forEach(dfs);
}

遍历顺序图：

深度优先遍历.png

广度优先遍历

定义：先访问里根节点最近的节点。

遍历算法：

1. 新建队列，把根节点入队
2. 把队头出队，并访问。
3. 把对头 children 挨个入队。
4. 重复2.3.直到队列为空。

遍历代码：

const bfs = (root) => {
    const queue = [root];
    while (queue.length > 0) {
        const n = queue.shift();
        console.log(n);
        queue.children.forEach(i => queue.push(i));
    }
}

遍历顺序图：

广度优先遍历.png

二叉树

树中每个节点最多只能有两个子节点。

在 Javascript 中通常用对象来模拟二叉树。

二叉树代码示例：

const binaryTree = {
    val:1,
    left: {
        val: 2,
        left: Object,
        right: Object
    },
    right: {
        val: 3,
        left: Object,
        right: Object
    }
}

二叉树先序遍历

遍历算法（中->左->右）：

1. 访问根节点。
2. 对根节点的左子树进行先序遍历。
3. 对根节点的右子树进行先序遍历。

二叉树先序遍历.png

递归法实现先序遍历：

const preorder = (bt) => {
    if (!bt) { return; }
    console.log(bt.val);
    preorder(bt.left);
    preorder(bt.right);
}

栈实现先序遍历：

const preorder = (bt) => {
    if (!bt) { return; }
    const stack = [bt];
    while(stack.length > 0) {
        const n = stack.pop();
        console.log(n);
        if (bt.right) stack.push(bt.right);
        if (bt.left) stack.push(bt.left);
    }
}

二叉树中序遍历

遍历算法（左->中->右）：

1. 对根节点左子树进行中序遍历。
2. 访问根节点。
3. 对根节点的右子树进行中序遍历。

二叉树中序遍历.png

递归法实现中序遍历：

const inorder = (bt) => {
    if (!bt) { return; }
    inorder(bt.left);
    console.log(be.val);
    inorder(bt.right);
}

栈实现中序遍历：

const inorder = (bt) => {
    if (!bt) { return; }
    const stack = [];
    const p = bt;
    while(stack.length>0 || p) {
        while(p) {
            stack.push(p);
            p = p.left;
        }
        const n = stack.pop();
        console.log(n);
        p = n.right;
    }
}

二叉树后序遍历

遍历算法（左->右->中）：

1. 对根节点左子树进行中序遍历。
2. 对根节点的右子树进行中序遍历。
3. 访问根节点。

二叉树后序遍历.png

递归法实现后序遍历：

const postorder = (bt) => {
    if (!bt) { return; }
    postorder(bt.left);
    postorder(bt.right);
    console.log(be.val); // 谁先遍历完输出谁
}

栈实现后序遍历：

1. 后序遍历遍历顺序是 左右中，现将遍历顺序倒过来就是，中右左
2. 按照中右左的顺序推入栈中，再将这个栈推出，推出的顺序即为后序遍历

const postorder = (bt) => {
    if (!bt) { return; }
    const stack = [bt];
    const outputStack = [];
    while(stack.length > 0) {
        const n = stack.pop();
        outputStack.push(n);
        if (n.left) stack.push(n.left);
        if (n.right) stack.push(n.right);
    }
    while(outputStack.length > 0) {
        const n = outputStack.pop();
        console.log(n.val);
    }
}