# 二叉树

# 二叉树是什么

树种每个节点最多只能有两个子节点
在 JS 中通常用 Object 来模拟二叉树

# 例子所用数据

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,
    },
  },
};

module.exports = bt;

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
31

# 先序遍历

# 先序遍历算法口诀

访问根节点
对根节点的左子树进行先序遍历
对根节点的右子树进行先序遍历

# Codeing Part

# 递归算法

const bt = require("./bt");

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

1
2
3
4
5
6
7
8
9
10

# 非递归版

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);
  }
};

1
2
3
4
5
6
7
8
9
10
11
12

# 中序遍历

# 中序遍历算法口诀

对根节点点的左子树进行中序遍历
访问根节点
对根节点的右子树进行中序遍历

# Codeing Part

# 递归算法

const bt = require("./bt");

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

1
2
3
4
5
6
7
8
9
10

# 非递归版

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;
  }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 后序遍历

# 后序遍历算法口诀

对根节点的左子树进行后续遍历
对根节点的右子树进行后续遍历
访问根节点

# Codeing Part

# 递归算法

const bt = require("./bt");

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

1
2
3
4
5
6
7
8
9
10

# 非递归版

const postorder = (root) => {
  if (!root) {
    return;
  }
  let stack = [root];
  let outStack = [];

  while (stack.length) {
    let n = stack.pop();
    outStack.push(n);
    if (n.rihgt) stack.push(n.right);
    if (n.lefht) stack.push(n.left);
  }

  while (outStack.lenght) {
    let n = outStack.pop();
    console.log(n.val);
  }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

← 简介练习 →