一棵树

const tree = {
    val: "a",
    children: [
        {
            val: "b",
            children: [
                {
                    val: "d",
                    children: [],
                },
                {
                    val: "e",
                    children: [],
                },
            ],
        },
        {
            val: "c",
            children: [
                {
                    val: "f",
                    children: [],
                },
                {
                    val: "g",
                    children: [],
                },
            ],
        },
    ],
};

搜索算法

DFS 深度优先遍历

递归

const dfs = node => {
    console.log(node.val);
    node.children.forEach(dfs);
};
dfs(tree);

BFS 广度优先遍历

维护一个队列，将每一层的结点推入队列，最后打印

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

二叉树的遍历

二叉树

const binaryTree = {
    val: 1,
    left: {
        val: 2,
        left: {
            val: 4,
            left: null,
            right: null,
        },
        right: {
            val: 5,
            left: null,
            right: null,
        },
    },
    right: {
        val: 3,
        left: {
            val: 6,
            left: null,
            right: null,
        },
        right: {
            val: 7,
            left: null,
            right: null,
        },
    },
};

递归版

1. 先序遍历：根左右
2. 中序遍历：左中右
3. 后序遍历：左右中

const prevOrder = node => {
    if (!node) return;
    console.log(node.val);
    prevOrder(node.left);
    prevOrder(node.right);
};
const inOrder = node => {
    if (!node) return;
    prevOrder(node.left);
    console.log(node.val);
    prevOrder(node.right);
};
// 后序遍历：左右中
const postOrder = node => {
  if (!node) return;
  postOrder(node.left);
  postOrder(node.right);
  console.log(node.val);
};

非递归版：维护栈

1. prevOrder：利用栈FILO，先入栈右节点，其次是左节点，最后依次打印
2. inOrder：先入栈左节点直到为null，依次出栈输出，同时入栈出栈结点的右节点（如果有）并出栈，如此循环
3. 维护两个栈，一个控制过程，另一个outStk存放输出顺序
   1. 根结点一定是最后输出，所以先入栈outStk
   2. 其次是入栈找到的右
   3. 最后入栈左节点 ```javascript const prevOrder = node => { // 利用栈的先进后出FILO if (!node) return; const stk = [node]; while (stk.length > 0) { const curr = stk.pop(); console.log(curr.val); if (curr.right) stk.push(curr.right); if (curr.left) stk.push(curr.left); } };

const inOrder = node => { / 维护一个栈，先将左节点一层层放入栈中直到没有 此时依次出栈，打印出当前出栈结点的同时，将当前结点的右节点（如果有）推入栈中，再出栈 循环直到栈为空 /

if (!node) return;
const stk = [];
let curr = node;
while (curr || stk.length > 0) {
    while (curr) {
        stk.push(curr);
        curr = curr.left;
    }
    const last = stk.pop();
    console.log(last.val);
    curr = last.right;
}

}; const postOrder = node => { / 维护两个栈，一个控制过程，另一个存放输出顺序 根结点一定是最后输出，所以先入栈 其次是入栈找到的右节点 最后是左节点 / if (!node) return; const stk = [node]; const outStk = []; while (stk.length) { const curr = stk.pop(); outStk.push(curr) if (curr.left) stk.push(curr.left); if (curr.right) stk.push(curr.right); } while(outStk.length) { console.log(outStk.pop().val ) } };

<a name="aWCHR"></a>
# 遍历JSON所有的节点（清理JSON）
```javascript
const json = {
    a: { b: { c: 1 } },
    d: [1, 2],
};
const dfs = (n, path) => {
    console.log(n, path);
    Object.keys(n).forEach(k => {
        dfs(n[k], path.concat(k));
    });
};
dfs(json, []);