二叉树

一、定义

二叉树是一种树结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。换句话说，二叉树是一种有序树，其中每个节点最多有两个子节点，这两个子节点被称为左子节点和右子节点。

二、规则

floor()向下取整函数，ceiling()想上取整函数，忽略四舍五入的运算，直接取整。

1. 每个节点的度最大为2（最多拥有两个子树）
2. 左子树和右子树是有顺序的
3. 即使某节点只有一颗子树也要区分左子树和右子树

非空二叉树的第i层，最多有2^i-1次方个节点 i>=1。

高度为h的二叉树，最多有2^h-1个节点。即通过节点数反推为：log2（n+1）

对于一个非空二叉树，如果叶子节点数为n0，度为2的节点个数为n2，则有n0= n2+1

公式推论：假设二叉树节点个数为n1，则二叉树节点数 n = n0+n1+n2

二叉树的边数（节点的度对应边数，除了根节点外的节点都有一条边）：T=1×n1+2×n2=n-1=n0+n1+n2-1 ---> n2 = n0-1

三、特点

1. 二叉树的唯一性：对于具有相同节点和边的二叉树，其结构是唯一的。即使节点包含相同的数据，它们的排列方式不同也会构成不同的二叉树。
2. 二叉树的平衡性：二叉树的平衡性对于某些操作的效率至关重要。平衡二叉树（如AVL树、红黑树等）能够保持树的高度差较小，从而保证了各种操作的时间复杂度较低。
3. 二叉树的性能分析：二叉树的性能受到树的形状和节点的排列方式的影响。对于一个包含n个节点的二叉树，其高度（或深度）最大为n-1，最小为⌊log₂(n+1)⌋，其中⌊x⌋表示不大于x的最大整数。当二叉树高度接近最小值时，其性能最佳

四、分类

1. 平衡二叉树（Balanced Binary Tree）：一种高度平衡的二叉树，保持了树的高度差较小，从而保证了各种操作的时间复杂度较低。常见的平衡二叉树包括AVL树、红黑树等。

2. 完全二叉树（Perfect Binary Tree）：除了叶子节点外，每个节点都有两个子节点，并且所有叶子节点都位于同一层。完美二叉树的高度为log₂(n+1)，其中n是节点数。

   叶子节点只会出现在最后两层，且最后一层的叶子节点都靠左对齐。

   1. 对于完全二叉树来说，至少有2^(h-1)次方个节点，最多有2^h次方-1个节点（满二叉树）。总结点个数为n的情况下，2^(h-1) <= n<2^h ====> h-1 <= log2(n) < h ====> h = floor(log2(n)) +1
   2. 对于完全二叉树有n各节点，从上到下、从左到右从1开始进行编号，对于任意节点i，如果i=1，它是根节点，如果i>1，他的父节点是floor(i/2)，如果2i<=n，他的左子节点编号为2i，如果2i>n，它无左子节点，如果2i+1<=n,他的右子节点为2i+1，如果2i+1>n,无右子节点
   3. 对于完全二叉树有n各节点，从上到下、从左到右从0开始进行编号，对于任意节点i，如果i=0，它是根节点，如果i>0，他的父节点是floor(i-1/2)，如果2i+1<=n-1，他的左子节点编号为2i+1，如果2i+1>n-1，它无左子节点。如果2i+2<=n-1,他的右子节点为2i+2，如果2i+2>n-1,无右子节点
   4. 如果一颗完全二叉树有n个节点，叶子节点总数：推论：假设叶子节点总数为n0，度为1的节点数为n1，度为2的节点个数为n2。总结点个数n=n0+n1+n2，而且n0=n2+1 ===> n = 2n0+n1-1，完全二叉树n1要么是0，要么是1。如果n为偶数或者n1=1时，叶子节点个数n0=n/2，非叶子节点个数也是n/2；如果n为奇数或者n1=01时，叶子节点个数n0=(n+1)/2，非叶子节点个数(n-1)/2。最终的公式为:no = floor((n+1)/2) 或者 ceiling(n/2) ==> (n+1)/2 ==> (n+1) >>1 向下取整

3. 满二叉树（Full Binary Tree）：除了叶子节点外，每个节点都有两个子节点，所有叶子节点都位于同一层，且所有非叶子节点的度都是2。所有节点的度要么为0，要么为2（必须是真二叉树）。且所有叶子节点都在最后一层

4. 二叉树的度数：节点的度数是指其拥有的子节点的数量。在二叉树中，每个节点的度数最大为2。

部分满二叉树是完全二叉树：如果一个满二叉树的深度为h，且除了第h层外的其他层都是满的，那么它就是一个完全二叉树。换句话说，每个节点都有两个子节点的满二叉树，如果缺少部分叶子节点，则可以变为完全二叉树。

完全二叉树不一定是满二叉树：完全二叉树的最后一层可能并不完全填满，但其余层都是满的，因此它不一定是满二叉树。满二叉树要求每个节点都有两个子节点，而完全二叉树只要求除了最后一层外的其他层都是满的

五、二叉树遍历

5.1 前序遍历

前序遍历是指二叉树的遍历的顺序为：根节点->前序遍历左子树（左子树从上到下全部打印）-> 前序遍历右子树（右子树从下到上全部打印）

应用：树状结构展示（注意左右子树的顺序）

5.2 中序遍历

中序遍历是指二叉树的遍历的顺序为：中序遍历左子树（左子树从下到上全部打印）->根节点-> 中序遍历右子树（右子树从下到上全部打印）

应用：二叉搜索树的中序遍历按升序或者降序处理节点

5.3 后序遍历

后序遍历是指二叉树的遍历的顺序为：后序遍历左子树（左子树从下到上全部打印）-> 后序遍历右子树（右子树从下到上全部打印）->根节点

应用：使用于一些先子后父的操作

5.4 层序遍历

层序遍历是指二叉树的遍历的顺序为：顾名思义，层序遍历是从上往下一层一层的遍历节点，每一层从左到右遍历结果。

应用：计算二叉树的高度。判断一棵树是否为完全二叉树

5.5 前驱节点

概念：中序遍历的前一个节点

5.6 后继节点

概念：中序遍历的后一个节点