数据结构 — 树
🌲

数据结构 — 树

Introduction
树是一种分层数据的抽象模型
Category
Data Structure
Algorithm
CreateTime
Sep 14, 2021
notion image

什么是树

  • 树是一种 分层 数据的抽象模型
  • 前端工作中常用的树:
    • DOM树
    • 级联选择
    • 树形控件
  • JS 中没有树,但是可以使用 ArrayObject 来模拟树
  • 树的常用操作
    • 深度/广度优先遍历
    • 先中后序遍历
 

深度/广度优先遍历

深度优先遍历

👇
尽可能的深的搜索树的分支
 
notion image

算法口诀

  1. 访问根节点
  1. 对根节点的每个 children 进行深度优先遍历
 
const dfs = (tree) => {
	console.log(tree.val);
	tree.children.foreach(dfs);
}
 

广度优先遍历

👉
先访问离根节点近的节点
 
notion image

算法口诀

  1. 新建一个队列,把根节点入队
  1. 把队头出队并访问
  1. 把队头的 children 挨个入队
  1. 重复第二、三步,直到队列为空
 
const bfs = (tree) => {
	const queue = [tree];
	while (queue.length > 0) {
		const n = queue.shift();
		n.children.forEach((child) => {
			queue.push(child);
		})
	}
}
 

二叉树

👉
二叉树是指树中每个节点最多有 两个 子节点
JS 中我们通常使用 Object 来模拟二叉树
const binaryTree = {
	val: 1,
	left: {
		val: 2,
		left: null,
		right: null,
	},
	right: {
		val: 3,
		left: null,
		right: null,
	},
}
 

二叉树的先序遍历

根 — 左 — 右
notion image
  1. 访问节点
  1. 对根节点的左子树进行先序遍历
  1. 对根节点的右子树进行先序遍历
 
const preorder = (root) => {
	if (!root) {
		return;
	}
	console.log(root.val);
	preorder(root.left);
	preorder(root.right);
}
 

二叉树的中序遍历

左 — 根 — 右
notion image
  1. 对根节点的子树进行中序遍历
  1. 访问节点
  1. 对根节点的子树进行中序遍历
 
const inorder = (root) => {
	if (!root) {
		return;
	}
	inorder(root.left);
	console.log(root.val);
	inorder(root.right)
}
 

二叉树的后序遍历

左 — 右 — 根
notion image
  1. 对根节点的子树进行后序遍历
  1. 对根节点的子树进行后序遍历
  1. 访问节点
 
const postorder = (root) => {
	if (!root) {
		return;
	}
	postorder(root.left);
	postorder(root.right);
	console.log(root.val)
}
 

二叉树力扣题目总结

二叉树的遍历方式

144 - 二叉树的前序遍历
145 - 二叉树的后序遍历
94 - 二叉树的中序遍历
102 - 二叉树的层序遍历
 

二叉树的属性

101 - 对称二叉树
104 - 二叉树的最大深度
111 - 二叉树的最小深度
222 - 完全二叉树的节点个数
110 - 平衡二叉树
257 - 二叉树的所有路径
404 - 左叶子之和
513 - 找树左下角的值
112 - 路径总和
 

二叉树的修改与构造

226 - 翻转二叉树
 

Loading Comments...