[数据结构与算法]Javascript之“树“

一种分层数据的模型
前端工作中常见包括：DOM树，级联选择，树形控件
JS中没有树，但是可以用Object和Array构建树
树的常用操作：深度/广度优先遍历，先中后序遍历

1. 常用操作

DFS实现

• 访问根节点
• 对根节点的children挨个进行深度优先遍历

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

const dfs = (root) => {
	console.log(root.val)
	root.children.forEach(dfs)
}
dfs(tree)

BFS实现

• 新建一个队列，把根节点入队
• 把对头出队并访问
• 把对头的children挨个入队
• 重复第二三步，直到队列为空

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

const bfs = (root) => {
	const q = [root]
	while(q.length > 0) {
		const r = q.shift()
		console.log(r)
		r.children.forEach(item => q.push(item))
	}
}
bfs(tree)

二叉树的先中后序遍历（递归）

const bt = {
	val: 1,
	left: {
		val: 2,
		left: {
			val: 4,
			left: 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,
		}
	}
}

// 先序遍历
const preorder = (root) => {
	if(!root) { return }
	console.log(root.val)
	preorder(root.left)
	preorder(root.right)
}
// 中序遍历
const inorder = (root) => {
	if(!root) { return }
	inorder(root.left)
	console.log(root.val)
	inorder(root.right)
}
// 后序遍历
const postorder = (root) => {
	if(!root) { return }
	postorder(root.left)
	postorder(root.right)
	console.log(root.val)
}

二叉树的先中后序遍历（非递归）

// 先序遍历
const preorder = (root) => {
  if(!root) { return }
  const stack = [root]
  while(stack.length) {
    const n = stack.pop()
    console.log(n.val)
    if( n.right ) stack.push(n.right)
    if( n.left ) stack.push(n.left)
  }
}

// 中序遍历
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
  }
}

// 后续遍历
const postorder = (root) => {
  if(!root) { return }
  const outputStack = []
  const stack = [root]
  while(stack.length) {
    const n = stack.pop()
    outputStack.push(n)
    if(n.left) stack.push(n.left)
    if(n.right) stack.push(n.right)
  }
  while(outputStack.length) {
    const n = outputStack.pop()
    console.log(n.val)
  }
}

2. 练习

二叉树的最大深度
二叉树的最小深度

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖