Version: Next

树

基本概念

  • 节点、根节点、父节点、兄弟节点
  • 一棵树可以没有任何节点，称为空树
  • 可以只有1个节点，即根节点
  • 子树、左子树、右子树

  • 节点的度 (degree)：子树的个数

  • 树的度：所有节点度的最大值

  • 叶子节点：度为0的节点

  • 非叶子节点：度不为0的节点

层数 (level)：根第1层，根节点的子节点为第2层

节点的深度（depth）：从根节点到当前节点的唯一路径上的节点总数（包含根节点）

节点的高度（height）：从当前节点到最远叶子节点的路径上的节点总数

树的深度：所有节点深度中的最大值

树的高度：所有节点中高度的最大值

树的深度 等于 树的高度

有序树与无序树

  • 有序树：树中任意节点的子节点之间有顺序关系
  • 无序树：树中任意节点的子节点之间没有顺序关系

森林

由m (m ≥ 0)棵不相交的树组成的集合

二叉树（BinaryTree）

  • 每个节点的度，最大为2（最多有用2棵子树）
  • 左子树与右子树有顺序
  • 即使某节点只有一颗子树，也要区分左右子树

二叉树的性质

  • 非空二叉树的第i层，最多有 2 ^ (i - 1)个节点， 即 1 -> 2 -> 4 -> 8 -> 16 -> 32 -> 64 ...

  • 在高度h的二叉树上最多有(2 ^ h) - 1个节点

  • n = n0 + n1 + n2，节点总数等于度为0的节点数 + 度为1的节点数 + 度为2的节点数

  • 二叉树的边数： T = 0 * n0 + 1 * n1 + 2 * n2

    = n1 + 2*n2 = 节点数n - 1= n0 + n1 + n2 - 1

  • 由n1 + 2*n2 = n0 + n1 + n2 -1 -> n2 = n0 - 1 对于任何一颗非空二叉树，如果叶子节点个数为n0，度为2的节点个数为n2，则 n0 = n2 + 1

真二叉树（Proper Binary Tree）

真二叉树：所有节点的度 = 0 或 2

满二叉树（Full Binary Tree）

  • 所有节点的度 = 0 或 2，且所有叶子节点都在最后一层
  • 即：所有叶子节点都在最后一层的真二叉树

在同样高度的二叉树中，满二叉树的叶子节点数量最多，总节点数量最多 满二叉树一定是真二叉树，真二叉树不一定是满二叉树

完全二叉树（Complete Binary Tree）

  • 叶子节点只会出现在最后2层，且最后1层的叶子节点都靠左对齐 即：从上到下，从左到右排列

  • 完全二叉树从根到倒数第二层是一棵完全二叉树

  • 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树

性质：

  • 度为1的节点只有左子树
  • 度为1的节点，要么为1个，要么为0个
  • 同样节点数量的二叉树中，完全二叉树的高度最小
  • 假设完全二叉树的高度为h，则至少有2 ^ (h - 1)个节点，最多有2 ^ h - 1个节点
  • 若总结点数为n，则有 2 ^ (h - 1) ≤ n ＜ 2 ^ h
  • h = logn向下取整 + 1 ==> h = floor(logn) + 1

编号性质：

  • 一颗有n个节点的完全二叉树(n > 0)，从上到下，从左到右对节点从1开始进行编号，对于任意第i个节点
    • 如果i = 1，则它是根节点
    • 如果i > 1，则它的父节点编号为floor(i / 2)
    • 如果2i + 1 < n，它的左子节点编号为2i
    • 如果2i > n，它无左子节点
    • 如果2i + 1 ≤ n，它的右子节点编号为2i + 1
    • 如果2i + 1 > n，它无右子节点

题

如果一颗完全二叉树有768个节点，求叶子节点的个数

  • 假设叶子节点的个数为n0(度为0)，度为1的节点个数为n1，度为2的节点个数为n2
  • 总结点个数n = n0 + n1 + n2，而且n0 = n2 + 1
  • -> n = 2n0 + n1 - 1
  • 由度为1的节点要么为0个要么为1个 -> n1 = 0 或 n1 = 1 -> n为奇数 或 n为偶数
  • 由n = 768为偶数，可知n1 = 1，则n0 = n / 2 = 768 / 2 = 384
结论
  • 当n为偶数
    • 叶子节点的个数n0 = n / 2
    • 非叶子节点的个数n1 + n2 = n / 2
  • 当n为奇数
    • 叶子节点的个数n0 = (n + 1) / 2
    • 非叶子节点的个数n1 + n2 = (n - 1) / 2
编程中统一n为奇数与偶数的情况

n0 = floor((n + 1) / 2)

在使用整型时，自带向下取证，除2使用位运算实现

int n0 = (n + 1) >> 1

也可以视作 n0 = 向上取整(n / 2)

结论：

  • 叶子节点的个数n0 = floor((n + 1) / 2) = ceiling(n / 2)
  • 非叶子节点的个数n1 + n2 = floor(n / 2) = ceiling((n - 1) / 2)

打印树

https://github.com/CoderMJLee/BinaryTrees

  • BinaryTreePrinter
    • 实现BinaryTreeInfo接口，四个方法
      1. Object root() 返回当前树根节点
      2. Object left(Object node) 返回当前节点的左节点
      3. Object right(Object node) 返回当前节点的右节点
      4. Object string(Object node) 打印节点类的哪些内容

工具网站