2022年 11月 9日

Python树

1. 概念

  • Python树:体现父子关系:连接相邻节点的关系
1.1 节点
  • 节点:树中每一个元素
  • 父节点
  • 子节点
  • 兄弟节点:父节点是同一个节点的节点
  • 根节点:没有父节点的节点
  • 叶子节点:没有子节点的节点
1.2 其他
  • 节点的高度(Hight):从底层算起,叶子节点到节点的最长路径/边数,计数起点是0
  • 节点的深度(Depth):从顶层算起,根节点到节点的最长路径/边数,技术起点是0
  • 节点的层数(Level):从顶层算起,根结点到节点的最长路径/边数 + 1 或 所有节点的个数,计数起点是1

2. 分类

  • 二叉树:每个节点最多有两个节点(可以是0,1, 2,不能是3,4…)

  • 满二叉树:除了叶子节点,每个节点都有左右两个子节点的二叉树

  • 完全二叉树:从树的根节点算起,从上至下,从左至右依次填满节点形成的二叉树

  • 二叉查找树:

  • 平衡二叉查找树:

  • 红黑树

  • 递归树

3. 存储

  • 基于指针或者引用的二叉链式存储法
  • 基于数组的顺序存储法

4. 操作

  • 二叉树遍历:递归
  • 前序遍历:根节点 左子树 右子树 子树中顺序一样
  • 中序遍历:左子树 根节点 右子树
  • 后序遍历:左子树 右子树 根节点

5. 应用场景

BFS, DFS, 迭代