Loveyless的学习笔记

Appearance

Return to top
On this page

基本知识

二叉树是指满足以下要求的树：

  1. 它可以没有根结点，作为一棵空树存在

  2. 如果它不是空树，那么必须由根结点、左子树和右子树组成，且左右子树都是二叉树。

注意：二叉树不能被简单定义为每个结点的度都是 2 的树。普通的树并不会区分左子树和右子树，但在二叉树中，左右子树的位置是严格约定、不能交换的。

二叉树的遍历

顺序规则

  • 先序遍历(根结点 -> 左子树 -> 右子树)
  • 中序遍历(左子树 -> 根结点 -> 右子树)
  • 后序遍历(左子树 -> 右子树 -> 根结点)
  • 层次遍历

规则分类

  • 递归遍历（先、中、后序遍历）
  • 迭代遍历（层次遍历）
javascript
// 二叉树
var a = {
  val: "A",
  left: { val: "B", left: { val: "D" }, right: { val: "E" } },
  right: { val: "C", left: { val: "F" }, right: { val: "G" } },
};

// 前序遍历 递归 我只能说牛逼 递归的思想真的不是一般人能写出来的
// 这个前序遍历我就没想到这么简单 几行就能写出来
function preOrder(root) {
  if (!root) {
    return;
  }
  console.log("当前的节点值为", root.val);
  preOrder(root.left);
  preOrder(root.right);
}
preOrder(a);

// 理解了先序遍历的过程，中序遍历就不是什么难题。
// 唯一的区别只是把遍历顺序调换了左子树 -> 根结点 -> 右子树：
function inOrder(root) {
  if (!root) {
    return;
  }
  inOrder(root.left);
  console.log("当前的节点值为", root.val);
  inOrder(root.right);
}
inOrder(a);

//后续遍历...