Tree.md

树

1. 根结点唯一
2. 子树个数没有限制，但一定互不相交

相关概念

• 结点的度
  • 分支结点（度非0）
  • 终端结点（度为0）
• 树的度：树中结点度的最大值
• 结点间的关系
  • 根结点
  • 双亲结点（parent）
  • 兄弟结点（sibling）
  • 祖先结点 | 子孙结点
• 树的深度（高度 | 最大层次）：根（1）... n（n + 1）

树的存储

• 双亲表示法（孩子指向双亲，根结点没有双亲-1填充）

  • 缺点：找孩子必须遍历整个表

    编号	data	parent
    0	A	-1
    1	B	0
    2	C	0
    3	D	1
    4	E	2
    5	F	2
    6	G	3
    7	H	3
    8	I	3
    9	J	4

• 孩子表示法（双亲结点指向孩子）

  • [data][child1][...][childn]
    • 孩子域个数由树的度决定，所有结点都有n个用来存放孩子
    • 缺点：当度相差比较大时，比较浪费空间
  • [data][degree][child1][...][childn]
    • 多一个 degree 表示当前结点的度，对应几个孩子域
    • 缺点：计算时间损耗，处理结点时代码不容易统一

• 孩子兄弟表示法

  • 混合结构
    • 结点放在顺序存储的数组（编号）
    • 每个结点的孩子用单链表

      1. 遍历整棵树：循环数组
      2. 某个结点的孩子：找到对应结点，顺着链表找
      3. 如何找某个结点的双亲（这个结构就不友好了）:需要遍历整棵树，检测每个结点下面的孩子结点包不包括自己

  • 在数组中结合双亲表示法：添加 parent
  • 兄弟的角度：[data][firstchild][rightsib]

二叉树

Binary Tree 是n(n>=0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成

特殊二叉树

• 斜树（所有结点都只有一个孩子结点，且方向一致）
  • 每层只有一个结点
  • 结点个数和深度是相同的
• 满二叉树（所有结点都有左右子树，并且所有的叶子结点都在同一层）
  • 叶子只能出现在最下面一层
  • 非叶子结点的度一定是2
  • 如果与其他二叉树相比同深度，则结点个数最多，叶子最多
• 完全二叉树（若二叉树结点编号与满二叉树结点编号位置完全相同）

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

  • 完全二叉树的所有结点与同深度的满二叉树按程序编号一定能够一一对应

  • 用数组表示很方便

    A	B	C	D	E	F
    0	1	2	3	4	5

    • A:0 B:1 C:2
      • B = 2 * 0 + 1
      • C = 2 * (0 + 1)
    • B:1 D:3 E:4
      • D = 2 * 1 + 1
      • E = 2 * (1 + 1)
    • 对于位置为 k 的结点
      • 左子结点 = 2 * k + 1
      • 右子结点 = 2 * (k + 1)
    • 最后一个非叶子结点的位置为 (N/2) - 1，N 为数组长度

二叉树表示

[data][leftchild][rightchild]

也有增加双亲结点、兄弟结点，具体视场景使用。

二叉树的遍历

• 中序遍历
  • 树为空返回 空
  • 根结点开始 中序遍历 根结点的 左子树（递归定义）
  • 左子树 访问完，访问根结点（往上一层）
  • 访问完根结点，访问其 右子树
  • 访问完后再向上访问 根结点 （重复上面过程）
    • 有右子树 -> 右子树
    • 无右子树 -> 根结点（往上一层）
• 前序遍历
• 后序遍历
• 层序遍历