二叉树的深度和高度有什么区别

在计算二叉树的相关数据时，常见的指标有深度和高度。尽管两者有一定的联系，但是它们又有不同的定义和计算方式。本文将从多个角度分析二叉树的深度和高度有什么区别。

一、定义

深度是指从二叉树的根节点到最远叶子节点的路径上的节点数目。例如，下图中二叉树的深度是3。

```

A

/ \

B C

/ \

D E

```

高度是指从二叉树的叶子节点到根节点的路径上的节点数目。例如，上图中二叉树的高度是2。

二、计算方式

1、深度的计算

深度的计算方式是通过递归遍历得到的。具体而言，我们可以通过如下代码计算出二叉树的深度。

``` python

def max_depth(root):

if root is None:

return 0

left_depth = max_depth(root.left)

right_depth = max_depth(root.right)

return max(left_depth, right_depth) + 1

```

在这里，我们分别递归计算二叉树左右子树的深度，然后找到其中较大的那一个，并加上1即可得到整棵树的深度。

2、高度的计算

高度的计算方式同样是通过递归遍历得到的。具体而言，我们可以通过如下代码计算出二叉树的高度。

``` python

def height(root):

if root is None:

return 0

left_height = height(root.left)

right_height = height(root.right)

return max(left_height, right_height) + 1

```

不同于深度的计算方式，这里我们是从下往上计算出每个节点相对于叶子节点的高度，并递归返回上一层。因此，在计算出二叉树左右子树的高度后，我们取其中较大的那一个，并加上1即可得到整棵树的高度。

三、应用场景

1、深度的应用场景

深度常用于判断一棵二叉树是否平衡，以及在二分搜索的时候判断搜索的深度，从而避免搜索无效节点。

2、高度的应用场景

高度常用于确定平衡二叉树的最小深度，从而在插入或删除节点后重新平衡树的结构。

四、深度和高度的联系

尽管深度和高度有不同的定义和计算方式，但它们之间是有联系的。

首先，对于一棵非空二叉树而言，它的高度一定大于等于1，深度一定大于等于1。而当它只有根节点时，它的高度和深度都为1。

其次，在满二叉树和完全二叉树中，深度和高度是相等的。因为在这两种情况下，从根节点到最远叶子节点的路径不可能存在空缺。

最后，在斜树、左斜树和右斜树中，深度和高度是不同的。在左斜树中，深度等于高度；在右斜树中，深度等于高度；而在斜树中，深度为节点数减1，高度为1。

综上所述，深度和高度是二叉树中常见的指标，具有不同的应用和计算方式，但它们之间存在联系。在实际应用中，我们需要根据具体的需求来选择使用深度还是高度。