什么是二叉树？

原文链接：https://note.noxussj.top/?source=helloworld

什么是二叉树？

树中每个节点最多只能有两个子节点，在 JavaScript 中一般都是通过 Object 来模拟二叉树。

常用操作

• 前序遍历
• 中序遍历
• 后序遍历

前序遍历

根左右。

口诀：

1. 访问根节点
2. 对根节点的左子树进行前序遍历
3. 对根节点的右子树进行前序遍历

通过递归方式实现

1function preorder(root) {
2    if (!root) return
3
4    console.log(root.val)
5    preorder(root.left)
6    preorder(root.right)
7}

通过迭代方式实现

1function preorder(root) {
2    if (!root) return
3
4    const stack = [root]
5
6    while (stack.length) {
7        const n = stack.pop()
8
9        console.log(n)
10        if (n.right) stack.push(n.right)
11        if (n.left) stack.push(n.left)
12    }
13}

中序遍历

左根右。

口诀：

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

通过递归方式实现

1function inorder(root) {
2    if (!root) return
3
4    inorder(root.left)
5    console.log(root.val)
6    inorder(root.right)
7}javascript

通过迭代方式实现

1function inorder(root) {
2    if (!root) return
3
4    const stack = [root]
5
6    while (stack.length) {
7        const n = stack.pop()
8
9        console.log(n)
10        if (n.right) stack.push(n.right)
11        if (n.left) stack.push(n.left)
12    }
13}

后序遍历

左右根。

口诀：

1. 对根节点的左子树进行后序遍历
2. 对根节点的右子树进行后序遍历
3. 访问根节点

通过递归方式实现

1function postorder(root) {
2    if (!root) return
3
4    postorder(root.left)
5    postorder(root.right)
6    console.log(root.val)
7}

通过迭代方式实现

1function postorder(root) {
2    if (!root) return
3
4    const outputStack = []
5    const stack = [root]
6
7    while (stack.length) {
8        const n = stack.pop()
9
10        outputStack.push(n)
11        if (n.left) stack.push(n.left)
12        if (n.right) stack.push(n.right)
13    }
14
15    while (outputStack.length) {
16        const n = outputStack.pop()
17        console.log(n.val)
18    }
19}