二叉树（待完善）

2021-07-18 本文已影响0人愿你我皆是黑马

每个节点最多只有两个分支（即分支度不大于2）的树结构

空二叉树：节点个数为0的树，也叫空树
斜树：相当于链表的特殊结构，所有节点都只有左节点或 都只有右节点
左斜树：
右斜树：
满二叉树：除了底层叶子节点，所以其他节点都存在左右子节点
1. 叶子节点只能出现在最下一层
2. 非叶子节点的度一定是2
3. 同样深度的树，满二叉树节点个数最多，叶子数最多
完全二叉树：满二叉树从最后开始按顺序去掉n(>=0)个节点的树
1. 叶子节点只会出现在最下两层
2. 最下层的叶子节点都往左连续靠
3. 倒数第二层，叶子节点都往右连续靠
4. 同样节点数的二叉树，完全二叉树的深度最小
5. 具有n个节点的完全二叉树的深度为 $\lfloor \log_2{n} \rfloor +1$
6. 具有n个节点的完全二叉树,按层编号,
  i=1 ：无双亲,属于该完全二叉树的根
  i>1 : 双亲节点是 $\lfloor i/2 \rfloor$
  2i>n : 则节点i无左孩子，否则左孩子为2i
  2i+1>n : 则节点i无右孩子，否则右孩子为2i+1
二叉搜索树
平衡二叉搜索树
线索二叉树
红黑树
AVL树
赫弗曼树

链式存储
以节点类为单位，每个节点有(左)节点和(右)节点的引用。
顺序储存
按层遍历:从上到下，每层从左到右遍历。将节点按顺序放到数组中
- 对于完全二叉树来说：i的左节点为 2 * i，i的右节点为2 * i + 1
- 若不是完全二叉树要使用上述性质，则空余节点使用null代替后。按序放到数组中

深度优先遍历：一条路走到底的遍历方式
1. 前序遍历：左右的前面插入中，即：中左右
2. 中序遍历：左右的中间插入中，即：左中右
3. 后序遍历：左右的后面插入中，即：左右中
广度优先遍历：按一层或一圈的遍历方式
从上到下，一层一层的从左到右遍历

前序

def 二叉树前序遍历(当前遍历到的节点):
  if 当前遍历到的节点==None:
      return
  print(当前遍历到的节点.value)
  二叉树前序遍历(当前遍历到的节点.左节点)
  二叉树前序遍历(当前遍历到的节点.右节点)

中序

def 二叉树前序遍历(当前遍历到的节点):
  if 当前遍历到的节点==None:
      return
  二叉树前序遍历(当前遍历到的节点.左节点)
  print(当前遍历到的节点.value)
  二叉树前序遍历(当前遍历到的节点.右节点)

后序

def 二叉树前序遍历(当前遍历到的节点):
  if 当前遍历到的节点==None:
      return
  二叉树前序遍历(当前遍历到的节点.左节点)
  二叉树前序遍历(当前遍历到的节点.右节点)
  print(当前遍历到的节点.value)