JS-树：二叉树中序遍历

---

---

前言

最近总结一下树的算法，研究树相关的知识。

---

一、中序遍历-递归

1、左中右
2、如下输入是：4 2 5 1 6 3 7

  // 前序遍历
  const tree = {
    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 },
    },
  }
	
  // 前序遍历
console.log(fun1(tree))

function fun1(root: any) {
  const arr: any[] = []
  const fun = (node: any) => {
    if (!node)
      return
    fun(node.left)
    arr.push(node.val)
    fun(node.right)
  }
  fun(root)
  return arr
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

二、中序遍历-队列

1、左中右
2、如下输入是：4 2 5 1 6 3 7

function fun2(root: any) {
  const arr: any[] = []
  const stack = []
  let o = root
  while (stack.length || o) {
    while (o) {
      stack.push(o)
      o = o.left
    }
    const n = stack.pop()
    arr.push(n.val)
    o = n.right
  }
  return arr
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

总结

这就是树的二叉树中序遍历，希望能帮助到你！