Files

tree

Name		Name	Last commit message	Last commit date
parent directory ..
demo_binary_tree_1.cpp		demo_binary_tree_1.cpp
demo_binary_tree_2.c		demo_binary_tree_2.c
demo_rooted_tree_1.cpp		demo_rooted_tree_1.cpp
demo_tree_walk_1.cpp		demo_tree_walk_1.cpp
readme.md		readme.md

readme.md

树(Tree)

- "树"这种数据很像现实生活中的“树”，这里的每个元素我们叫做“节点”
- 用来连线相邻节点之间的关系，我们叫做“父子关系”
- A节点就是B节点的父节点，B节点是A节点的‘子节点’
- B，C，D这三个节点的父节点是同一个节点，所以它们是兄弟节点
- 把没有父节点的节点叫做根节点，也图中的E
- 把没有子节点的节点叫做叶子节点或者叶节点，比如图中的G,H, I, J, K, L
高度(Height)，深度(Depth)，层(Level)
- 概述
  - 节点的高度：节点到叶子节点的最长路径（边数）
  - 节点的深度：根节点到这个节点所经历的边的个数
  - 节点的层数：节点的深度 + 1
  - 树的高度：根节点的高度
- 高度
  - 其实就是从下往上度量，比如我们要度量第10层楼的高度，第13层楼的高度，起点都是地面
  - 所以，树这种数据结构的高度也是一样，从最底层开始计数，并且计数的起点都是0
- 深度
  - 从上往下度量。比如水中与的深度，是从水平面开始度量
  - 所有，树这种数据结构的深度也是类似的，从根节点开始度量，并且计数起点也是0
- 层数
  - 与深度类似,不过，计数起点是1，也就是根节点的位于第1层

二叉树(Binary Tree)

概述
- 每个节点最多有两个“叉”，也就是两个子节点，分别是左子节点和右子节点
- 满二叉树
  - 图中编号2的二叉树。叶子节点全都在最底层
  - 除了叶子节点之外，每个节点都有左右两个子节点，这种二叉树叫做满二叉树
- 完全二叉树
  - 编号3的二叉树，叶子节点都在最底下两层，最后一层的叶子节点都靠左
  - 并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫做完全二叉树
二叉树存储方式
- 链表存储法
  - 每个节点都有三个字段，其中一个存储数据，另外两个是指向左右子节点指针
  - 我们只要拎住根节点，就可以通过左右子节点的指针，把整棵树都串起来
  - 大部分二叉树代码都是通过这种结构实现的
- 顺序存储法
  - 把根节点存储在下标i = 1的位置，那左子节点存储在下标 2 * i = 2 的位置，右子节点存储在 2 * i + 1 = 3 的位置
  - 以此类推，B节点的左子节点存储在 2 * i = 2 * 2 = 4的位置，右子节点存储在 2 * i + 1 = 2 * 2 + 1 = 5的位置
- 为什么偏偏把最后一层的叶子节点靠左排列的叫做完全二叉树？
  - 从上图看出，一颗完全二叉树，仅仅“浪费”了一个下标为0的存储位置，如果非完全二叉树，则会浪费比较多的数组存储空间

二叉树遍历

前序遍历
- 对于树中任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的左子树
中序遍历
- 对于树中任意节点来说，先打印它的左子树，然后再打印它本省，最后打印它的右子树
后序遍历
- 对于树中任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身
时间复杂度
- 从上图可以看出，每个节点最多会被访问两次，所以遍历操作的时间复杂度，跟节点的个数n成正比，也就是时间复杂度: O(n)
代码展示

参考资料

卡特兰数 — 计数的映射方法的伟大胜利