树是一种数据结构，它是由n(n≥0)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
每个节点有零个或多个子节点；没有父节点的节点称为根节点；每一个非根节点有且只有一个父节点；除了根节点外，每个子节点可以分为多个不相交的子树。
- 深度优先遍历/广度优先遍历
const tree = {
name: 'node-1',
children: [
{
name: 'node-2',
children: [
{
name: 'node-6',
children: []
}
]
},
{
name: 'node-3',
children: [
{
name: 'node-4',
children: []
},
{
name: 'node-5',
children: []
}
]
}
]
}
//深度优先
const dfs = (node) => {
console.log(node.name)
node.children.forEach(dfs)
}
dfs(tree)
//node-1
//node-2
//node-6
//node-3
//node-4
//node-5
//广度优先
const bfs = (node) => {
const queue = [node]
while (queue.length) {
const head = queue.shift()
console.log(head.name)
head.children.forEach(child => queue.push(child))
}
}
bfs(tree)
//node-1
//node-2
//node-3
//node-6
//node-4
//node-5
二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分 [1] 。
二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个节点 [1] 。
const binaryTree = {
name: 'node-1',
left: {
name: 'node-2',
left: {
name: 'node-4',
left: null,
right: null
},
right: {
name: 'node-5',
left: null,
right: {
name: 'node-8',
left: null,
right: null
}
}
},
right: {
name: 'node-3',
left: {
name: 'node-6',
left: null,
right: null
},
right: {
name: 'node-7',
left: null,
right: null
}
}
}
- 先序遍历/中序遍历/后序遍历（递归）
//先序遍历
const preorder = (node) => {
if (!node) return
console.log(node.name)
preorder(node.left)
preorder(node.right)
}
preorder(binaryTree)
// node-1
// node-2
// node-4
// node-5
// node-8
// node-3
// node-6
// node-7
//中序遍历
const inorder = (node) => {
if (!node) return
inorder(node.left)
console.log(node.name)
inorder(node.right)
}
inorder(binaryTree)
// node-4
// node-2
// node-5
// node-8
// node-1
// node-6
// node-3
// node-7
//后序遍历
const postorder = (node) => {
if (!node) return
postorder(node.left)
postorder(node.right)
console.log(node.name)
}
postorder(binaryTree)
// node-4
// node-8
// node-5
// node-2
// node-6
// node-7
// node-3
// node-1
- 先序遍历/中序遍历/后序遍历（使用栈实现）
//先序遍历
const preorder = (node) => {
if (!node) return
const stack = [node]
while (stack.length) {
const head = stack.pop()
console.log(head.name)
if (head.right) {
stack.push(head.right)
}
if (head.left) {
stack.push(head.left)
}
}
}
preorder(binaryTree)
// node-1
// node-2
// node-4
// node-5
// node-8
// node-3
// node-6
// node-7
//中序遍历
const inorder = (node) => {
if (!node) return
const stack = []
let p = node
while (stack.length || p) {
while (p) {
stack.push(p)
p = p.left
}
const head = stack.pop()
console.log(head.name)
p = head.right
}
}
inorder(binaryTree)
// node-4
// node-2
// node-5
// node-8
// node-1
// node-6
// node-3
// node-7
//后序遍历
const postorder = (node) => {
if (!node) return
const stack = [node]
const outputStack = []
while (stack.length) {
const head = stack.pop()
outputStack.push(head.name)
if (head.left) {
stack.push(head.left)
}
if (head.right) {
stack.push(head.right)
}
}
while (outputStack.length) {
const head = outputStack.pop()
console.log(head)
}
}
postorder(binaryTree)
// node-4
// node-8
// node-5
// node-2
// node-6
// node-7
// node-3
// node-1
