完全二叉树与满二叉树：定义与区别

在计算机科学中，二叉树是一种常见的树形数据结构，其中每个节点最多有两个子节点：通常称为左子节点和右子节点。根据节点的完整程度，二叉树可以分为完全二叉树和满二叉树。

一、完全二叉树

完全二叉树是指除最后一层外，其他层的节点数达到最大，且最后一层的节点尽可能集中在左侧的二叉树。这种类型的二叉树的特点是，对于给定的节点数，其深度最小。

二、满二叉树

满二叉树则是指除最后一层外，其他各层的节点数都达到最大，且最后一层的节点数达到最大。也就是说，满二叉树的每一层都完全填满，没有任何空位。满二叉树的特点是，其深度等于节点数。

三、主要区别

1. 节点利用情况：在满二叉树中，所有节点都得到充分利用，每一层都完全填满。而在完全二叉树中，可能存在未被使用的节点。
2. 深度与节点数的关系：对于满二叉树，其深度等于节点数。而对于完全二叉树，其深度最小，小于或等于节点数。
3. 空间效率：由于完全二叉树可能存在未使用的节点，因此在某些情况下，其空间效率更高。

四、计算二叉树的深度

计算二叉树的深度可以使用递归的方法。基本思路是从根节点开始，递归地访问左子节点和右子节点，并分别计算它们的深度。当到达叶子节点时，返回1（因为叶子节点本身没有子节点）。最后，将左右子树的深度相加，再加1（加上根节点的深度）。

在Python中，可以使用如下的代码实现：

```python
def depth(node):
if node is None: # 叶子节点为空
return 1
else:
left_depth = depth(node.left) # 递归计算左子树的深度
right_depth = depth(node.right) # 递归计算右子树的深度
return max(left_depth, right_depth) + 1 # 返回左右子树深度的最大值加1