二叉树

二叉树是什么

• 树的每个节点最多只有两个子节点。
• JS可以用Object来模拟二叉树。

{
	val: 'a',
	left: {
		val: 'b',
		left: {
			val: 'c',
			left: null,
			right: null
		},
		right: {
			val: 'd',
			left: null,
			right: null
		}
	},
	right: {
		val: 'e',
		left: {
			val: 'f',
			left: null,
			right: null
		},
		right: {
			val: 'g',
			left: null,
			right: null
		}
	}
}

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

先序遍历

算法口诀：（根 —> 左 —> 右）

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

const root = {
  val: 'a',
  left: {
    val: 'b',
    left: {
      val: 'c',
      left: null,
      right: null
    },
    right: {
      val: 'd',
      left: null,
      right: null
    }
  },
  right: {
    val: 'e',
    left: {
      val: 'f',
      left: null,
      right: null
    },
    right: {
      val: 'g',
      left: null,
      right: null
    }
  }
};

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

preorder(root);

// 输出：a b c d e f g

中序遍历

算法口诀：（左 —> 根 —> 右）

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

const root = {
  val: 'a',
  left: {
    val: 'b',
    left: {
      val: 'c',
      left: null,
      right: null
    },
    right: {
      val: 'd',
      left: null,
      right: null
    }
  },
  right: {
    val: 'e',
    left: {
      val: 'f',
      left: null,
      right: null
    },
    right: {
      val: 'g',
      left: null,
      right: null
    }
  }
};

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

midorder(root);

// 输出： c b d a f e g

后序遍历

算法口诀：（左 —> 右 —> 根）

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

const root = {
  val: 'a',
  left: {
    val: 'b',
    left: {
      val: 'c',
      left: null,
      right: null
    },
    right: {
      val: 'd',
      left: null,
      right: null
    }
  },
  right: {
    val: 'e',
    left: {
      val: 'f',
      left: null,
      right: null
    },
    right: {
      val: 'g',
      left: null,
      right: null
    }
  }
};

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

nextorder(root);

// 输出： c d b f g e a

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

• 利用栈和循环实现

先序遍历（根 —> 左 —> 右）

1. 创建一个栈
2. 先把根节点放入栈中
3. 根节点出栈并打印，然后把右节点先入栈，再把左节点入栈
4. 重复3步骤，直至栈为空

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

preorder(root);

中序遍历（左 —> 根 —> 右）

1. 创建一个栈
2. 先把根节点放入栈中，再把左节点入栈
3. 重复2步骤，直至当前子树的左节点为空
4. 当前栈顶出栈并打印，将指针指向当前栈顶元素的右节点
5. 重复2、3、4步骤，直至栈和指针都为空停止

const midorder = (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;
  }
}

midorder(root);

后序遍历（左 —> 右 —> 根）

1. 创建两个栈stack和outStack
2. stack用来循环将节点以根 —> 右 —> 左的顺序推入outStack栈中
3. 依次输出outStack栈顶节点

const nextorder = (root) => {
  if (!root) return;
  const stack = [root];
  const outStack = [];
  while (stack.length) {
    const n = stack.pop();
    outStack.push(n);
    if (n.left) stack.push(n.left);
    if (n.right) stack.push(n.right);
  }

  while (outStack.length) {
    const r = outStack.pop();
    console.log(r.val)
  }
}

nextorder(root);