算法013_树

树形结构

• 树是一种数据结构，比如：目录结构
• 树是一种可以递归定义的数据结构
• 树是由 n 个节点组成的集合
  • 如果 n = 0，那这是一棵空树

  • 如果 n > 0，那存在 1 个节点作为树的根节点，其他节点可以分为 m 个集合，每个集合本身又是一棵树

    
    

相关概念

• 根节点、叶子节点：
  • 根节点 A
  • 叶子节点：不能分叉的节点，也就是最末端，比如 B、C、H、I、P、Q、K、L、M、N
• 树的深度（高度）：最深有几层，这里是 4 层
• 树的度
  • 节点的度：分了几个叉就是多少度（往下的叉）
  • 树的度：树当中哪个节点分叉最多就是树的度，这里树的度是6
• 孩子节点 / 父节点：E 是 I 的父节点、I 是 E 的子节点
• 子树：把树的一些部分单独拎出来，比如 E、I、J、P、Q 就是一个子树

二叉树

• 二叉树：度不超过 2 的树
• 每个节点最多有两个孩子节点
• 两个孩子节点被区分为左孩子节点和右孩子节点

满二叉树和完全二叉树

• 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树
• 完全二叉树：叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树
  • 可以理解为从满二叉树最后拿走几个节点，从上到下必须是连续的，不能从中间拿（相当于编号得是连续的）

满二叉树

满二叉树

完全二叉树

完全二叉树

非完全二叉树

非完全二叉树 非完全二叉树

二叉树的存储方式：
链式存储方式、顺序存储方式

这里使用顺序存储方式（列表）

二叉树的值与列表序号对应关系

父节点和左孩子节点的编号下标有什么关系？ i --> 2i + 1

父亲节点 9 左孩子节点 8: 列表序号对应 0 --> 1
父亲节点 8 左孩子节点 6: 列表序号对应 1 --> 3
父亲节点 7 左孩子节点 0: 列表序号对应 2 --> 5
父亲节点 6 左孩子节点 2: 列表序号对应 3 --> 7
父亲节点 5 左孩子节点 3: 列表序号对应 4 --> 9

父节点和右孩子节点的编号下标有什么关系? i --> 2i + 2

父亲节点 9 右孩子节点 7: 列表序号对应 0 --> 2
父亲节点 8 右孩子节点 5: 列表序号对应 1 --> 4
父亲节点 7 右孩子节点 1: 列表序号对应 2 --> 6
父亲节点 6 右孩子节点 4: 列表序号对应 3 --> 8

孩子找父亲节点：假设孩子节点是 i，父亲节点是 （i - 1）// 2

左孩子节点 8 父亲节点 9: 列表序号对应关系 (1 - 1) // 2 = 0
右孩子节点 7 父亲节点 9: 列表序号对应关系 (2 - 1) // 2 = 0
左孩子节点 6 父亲节点 8: 列表序号对应关系 (3 - 1) // 2 = 1
右孩子节点 5 父亲节点 8: 列表序号对应关系 (4 - 1) // 2 = 1