二叉树（一）

树、二叉树、二叉查找树、平衡二叉树、红黑树、递归树

一、树

1. 树的常用概念
   节点：树中的每个元素称为节点
   父子关系：相邻两节点的连线，称为父子关系
   根节点：没有父节点的节点
   叶子节点：没有子节点的节点
   父节点：指向子节点的节点
   子节点：被父节点指向的节点
   兄弟节点：具有相同父节点的多个节点称为兄弟节点关系
   节点的高度：节点到叶子节点的最长路径所包含的边数
   节点的深度：根节点到节点的路径所包含的边数
   节点的层数：节点的深度+1（根节点的层数是1）
   树的高度：等于根节点的高度

   
   image.png
   image.png

二、二叉树

1. 什么是二叉树？
   每个节点最多只有2个子节点的树，这两个节点分别是左子节点和右子节点。
2. 什么是满二叉树？
   有一种二叉树，除了叶子节点外，每个节点都有左右两个子节点，这种二叉树叫做满二叉树。
3. 什么是完全二叉树？
   有一种二叉树，叶子节点都在最底下两层，最后一层叶子节都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫做完全二叉树。

三、完全二叉树的存储

1. 链式存储
   每个节点由3个字段，其中一个存储数据，另外两个是指向左右子节点的指针。我们只要拎住根节点，就可以通过左右子节点的指针，把整棵树都串起来。这种存储方式比较常用，大部分二叉树代码都是通过这种方式实现的。

   
   image.png

2. 顺序存储
   用数组来存储，对于完全二叉树，如果节点X存储在数组中的下标为i，那么它的左子节点的存储下标为2i，右子节点的下标为2i+1，反过来，下标i/2位置存储的就是该节点的父节点。注意，根节点存储在下标为1的位置。完全二叉树用数组来存储时最省内存的方式。
   

   image.png

3. 二叉树的遍历

   
   image.png

• 前序遍历：对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。

递推公式：
preOrder(r) = print r->preOrder(r->left)->preOrder(r->right)

• 中序遍历：对于树中的任意节点来说，先打印它的左子树，然后再打印它的本身，最后打印它的右子树。

递推公式：
inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)

• 后序遍历：对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印它本身。

递推公式：
postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r

void preOrder(Node* root) {
  if (root == null) return;
  print root // 此处为伪代码，表示打印root节点
  preOrder(root->left);
  preOrder(root->right);
}

void inOrder(Node* root) {
  if (root == null) return;
  inOrder(root->left);
  print root // 此处为伪代码，表示打印root节点
  inOrder(root->right);
}

void postOrder(Node* root) {
  if (root == null) return;
  postOrder(root->left);
  postOrder(root->right);
  print root // 此处为伪代码，表示打印root节点
}

• 时间复杂度：3种遍历方式中，每个节点最多会被访问2次，所以时间复杂度是O(n)。

三、思考

1. 二叉树有哪几种存储方式？什么样的二叉树适合用数组来存储？
2. 给定一组数据，比如1，3，5，6，9，10.你来算算，可以构建出多少种不同的二叉树？
3. 我们讲了三种二叉树的遍历方式，前、中、后序。实际上，还有另一种遍历方式，也就是按层遍历，你知道如何实现吗？
4. 如何用循环实现二叉树的遍历？
5. 有了这么高效的散列表，使用二叉树的地方是不是都可以替换成散列表呢？有6. 没有哪些地方是散列表做不了，必须要用二叉树来做的呢？
6. 二叉查找树的特点有哪些？
7. 二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要9. 小于这个节点的值，而右子树节点的值都大于这个节点的值。
8. 二叉查找树的查找、插入、删除操作、快速地查找最大节点和最小节点、快速地查找前驱节点和后继节点的代码实现。
9. 二叉查找树为什么也叫作二叉排序树？
10. 二叉查找树支持重复数据的吗？
11. 分析下二叉查找树的时间复杂度？
12. 中序遍历二叉查找树，可以输出有序的数据序列，时间复杂度是 O(n)，非常高效。因此，二叉查找树也叫作二叉排序树。
13. 如何通过编程，求出一棵给定二叉树的确切高度呢？
14. 为什么要有"平衡二叉查找树"，什么是“平衡二叉查找树”？AVL 树是什么？
15. 如何定义一棵"红黑树"？"红黑树"的特点？
16. 红黑树与平衡二叉树(AVL 树)的区别？
17. 为什么说红黑树是“近似平衡”的？
18. 红黑树的高度怎么计算？
19. 红黑树的应用场景？
20. 动态数据结构支持动态地数据插入、删除、查找操作，除了红黑树，我们前面还学习过哪些呢？能对比一下各自的优势、劣势，以及应用场景吗？
21. 红黑树的插入操作的平衡调整、删除操作的平衡调整，红黑树的实现、左旋、右旋
22. 利用递归树分析归并排序、快速排序、斐波那契数列、全排列的时间复杂度
23. 1 个细胞的生命周期是 3 小时，1 小时分裂一次。求 n 小时后，容器内有多少细胞？请你用已经学过的递归时间复杂度的分析方法，分析一下这个递归问题的时间复杂度。