树 - 《前端算法基础》

深度优先遍历
二叉树
遍历 json 的所有节点值

一种分层数据的抽象模型
前端中常见的树包括：DOM树、级联选择、树形控件

js 中没有树，但可以用 Object 和 Array 构建树

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

树的常用操作
- 深度广度优先遍历、先中后续遍历

深度优先遍历

尽可能深的搜索树的分支

口诀
- 访问根节点
- 对根节点 children 挨个进行深度优先遍历 ```javascript /**
  - 深度优先遍历：访问根结点，对根结点 children 挨个进行深度优先遍历 */ const dfs = (root) => { console.log(root.val);
root.children.forEach(child => dfs(child)); }

dfs(tree);


<a name="WHQBO"></a>
## 广度优先遍历
先访问离根节点最近的节点<br />![image.png](https://cdn.nlark.com/yuque/0/2021/png/340142/1613112420022-2df83296-a399-4fdd-8b78-44137cf48223.png#align=left&display=inline&height=293&margin=%5Bobject%20Object%5D&name=image.png&originHeight=956&originWidth=444&size=171042&status=done&style=none&width=136)
口诀
- 新建一个队列，把根节点入队
- 把对头出队并访问
- 把对头的 children 挨个入队
- 重复二三步，直到队列为空
```javascript
/**
 * 广度优先遍历：
 * 1.新建一个队列，把根结点入队
 * 2.把队头出队并访问
 * 3.把队头的 children 挨个入队
 * 4.重复第二、三步，直到队列为空
 */
const bfs = (root) => {
  const q = [root];
  while(q.length > 0) {
    const n = q.shift();
    console.log(n.val);
    n.children.forEach(item => q.push(item));
  }
}
bfs(tree);

二叉树

什么是二叉树？

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

js 中通常用 Object 来模拟二叉树 ```javascript const bt = { val: 1, left: { val: 2, left: {

val: 4,
left: {
  val: 8,
  left: null,
  right: 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,

} } }

module.exports = bt;


<a name="E2CqD"></a>
### 二叉树先序遍历

- 访问根节点
- 对根节点的左子树进行先序遍历
- 对根节点的右子树进行先序遍历
```javascript
/** 
 * 先序遍历
 * 访问根结点
 * 对根结点的左子树进行先序遍历
 * 对根结点的右子树进行先序遍历
 */ 
const preOrder = (root) => {
  if (!root) {
    return;
  }

  console.log(root.val);

  preOrder(root.left);
  preOrder(root.right);
}

/** 
 * 非递归版
 */
const preOrder = (root) => {
  if (!root) { return };

  const stack = [root];

  while(stack.length > 0) {
    const n = stack.pop();

    if (n) {
      console.log(n.val);

      stack.push(n.right)
      stack.push(n.left)
    }
  }
}

preOrder(bt);

二叉树中序遍历

对根结点的左子树进行中序遍历
访问根结点
对根节点的右子树进行中序遍历 ```javascript /**
- 中序遍历
- 对根结点的左子树进行中序遍历
- 访问根结点
- 对根节点的右子树进行中序遍历 */ const inOrder = (root) => { if (!root) { return; }
inOrder(root.left);

console.log(root.val);

inOrder(root.right); }

inOrder(bt);


```javascript
/** 
 * 非递归版
 */
const inOrder = (root) => {
  if (!root) {
    return;
  }

  const stack = [];
  let p = root;

  while(stack.length || p) {
    while(p) {
      stack.push(p);

      p = p.left;
    }

    const n = stack.pop();
    console.log(n.val);

    p = n.right;
  }
}

inOrder(bt);

二叉树后序遍历

对根结点的左子树进行先序遍历
对根结点的右子树进行先序遍历
访问根节点 ```javascript /**
- 后续遍历
- 对根结点的左子树进行先序遍历
- 对根结点的右子树进行先序遍历
- 访问根节点 */ const postOrder = (root) => { if (!root) { return; }
postOrder(root.left); postOrder(root.right);

console.log(root.val); }

postOrder(bt);

```javascript
/** 
 * 非递归版
 */
const postOrder = (root) => {
  if (!root) {
    return;
  }

  const stack = [root];
  const outStack = [];

  while(stack.length) {
    const n = stack.pop();
    outStack.push(n);

    if (n.left) {
      stack.push(n.left);
    }

    if (n.right) {
      stack.push(n.right);
    }
  }

  while(outStack.length) {
    const n = outStack.pop();

    console.log(n.val);
  }
}

postOrder(bt);

遍历 json 的所有节点值

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, []);

结果

JSjsonjs
1
constjson
a:fb:fc:1j万,
2
d:[1,2],
3
4
5
constdfs(n,path)>
67
conso1e.1og(n,path);
object.keys(n).forEach(k->
8
dfs(n[k],path.concat(k));
9
);
10
11
12
dfs(json,[i);
13
1