数据结构 — 树

什么是树

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

• 前端工作中常用的树：
• DOM树
• 级联选择
• 树形控件

• JS 中没有树，但是可以使用 Array 和 Object 来模拟树

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

深度/广度优先遍历

深度优先遍历

算法口诀

1. 访问根节点

2. 对根节点的每个 children 进行深度优先遍历

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

广度优先遍历

算法口诀

1. 新建一个队列，把根节点入队

2. 把队头出队并访问

3. 把队头的 children 挨个入队

4. 重复第二、三步，直到队列为空

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

二叉树

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

二叉树的先序遍历

根 — 左 — 右

1. 访问根节点

2. 对根节点的左子树进行先序遍历

3. 对根节点的右子树进行先序遍历

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

二叉树的中序遍历

左 — 根 — 右

1. 对根节点的左子树进行中序遍历

2. 访问根节点

3. 对根节点的右子树进行中序遍历

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

二叉树的后序遍历

左 — 右 — 根

1. 对根节点的左子树进行后序遍历

2. 对根节点的右子树进行后序遍历

3. 访问根节点

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

二叉树力扣题目总结

二叉树的遍历方式

二叉树的属性

二叉树的修改与构造