树

树是什么

• 树是一种分层数据的抽象模型

• 前端中常见的树有：DOM树，级联菜单，树形控件等等

• JS中没有树，前端可以用Object和Array来构建树。

{
	value: 'a',
	lable: '第一个',
	childen: [
		{
			value: 'b',
			lable: '第二个',
		},
		{
			value: 'c',
			lable: '第三个',
		},
	]

}

树的深度和广度优先遍历

树的深度优先遍历

原则：尽可能深的搜索树的分支。

算法口诀：（递归）

1. 访问根节点
2. 对根节点的children进行深度优先遍历

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

const dfs = (root) => {
  if(!root) return;
  console.log(root.val);
  root.children.forEach(dfs)
}

dfs(root);

// 输出：a b c d e f g

树的广度优先遍历

原则：先访问离根节点最近的节点。

算法口诀：

1. 新建一个队列，把根节点入队。
2. 对头出队并访问
3. 将对头的children入队
4. 重复2、3，直至队列为空

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

const bfs = (root) => {
  if (!root) return;
  const stack = [root];
  while (stack.length) {
    const n = stack.shift();
    console.log(n.val);
    if (n && n.children) {
      n.children.forEach((item) => {
        stack.push(item);
      });
    }
  }
}

bfs(root);

// 输出： a b e c d f g