354

这是算法理论中的一个简单问题。
它们之间的区别在于，在一种情况下，您计算根节点和具体节点之间最短路径上的节点数量和其他数量的边。
哪个是哪个？

4

10 回答 10

848

我了解到深度和高度是节点的属性：

  • 节点的深度是从节点到树根节点的边数。
    根节点的深度为 0。

  • 节点的高度是从节点到叶子的最长路径上的边数。
    叶节点的高度为 0。

树的属性：

  • 树的高度将是它的根节点的高度，
    或者等效地，它的最深节点的深度。

  • 树的直径（或宽度）是任意两个叶节点之间最长路径上的节点数。下面的树的直径为 6 个节点。

一棵树，每个节点的高度和深度

于 2010-04-08T21:52:13.893 回答
52

一棵树的高度和深度是相等的...

但是节点的高度和深度不相等，因为...

高度是通过从给定节点遍历到可能最深的叶子来计算的。

深度是从根到给定节点的遍历计算出来的.....

于 2014-09-14T16:12:39.733 回答
18

根据 Cormen 等人的说法。算法介绍（附录 B.5.3），树 T 中节点 X 的深度定义为从 T 的根节点到 X 的简单路径的长度（边数）。节点 Y 的高度为从 Y 到叶子的最长向下简单路径上的边数。树的高度定义为其根节点的高度。

请注意，简单路径是没有重复顶点的路径。

树的高度等于树的最大深度。节点的深度和节点的高度不一定相等。参见 Cormen 等人第 3 版的图 B.6。用于说明这些概念。

我有时会看到要求计算节点（顶点）而不是边的问题，因此如果您不确定在考试或求职面试期间是否应该计算节点或边，请要求澄清。

于 2012-01-02T20:42:18.300 回答
8

我知道这很奇怪，但 Leetcode 也根据路径中的节点数来定义深度。所以在这种情况下，深度应该从 1 开始（总是计算根）而不是 0。如果有人像我一样有同样的困惑。

于 2020-12-21T00:34:26.770 回答
6

简单答案：
深度：
1.树：从树的根节点到叶节点的 边/弧的数量称为树的深度。
2.节点：从根节点到该节点的边/弧的数量称为该节点的深度。

于 2013-05-22T06:27:54.573 回答
3

理解这些概念的另一种方法如下： 深度：在根位置画一条水平线，并将这条线视为地面。所以根的深度为0，它的所有子节点都向下增长，因此每一级节点的当前深度+1。

高度：相同的水平线，但这次地面位置是外部节点，即树的叶子，向上计数。

于 2017-02-09T16:14:05.217 回答
3

我想发表这篇文章是因为我是一名 CS 本科生，而且我们越来越多地使用 OpenDSA 和其他开源教科书。从最高评价的答案看来，教授高度和深度的方式已经从一代到下一代发生了变化，我发布这个是为了让每个人都知道这种差异现在存在，希望不会导致任何错误程式！谢谢。

来自OpenDSA 数据结构和算法书：

如果 n 1 , n 2 ,...,n k是树中的一个节点序列，使得 n i是 n i +1 的父节点，因为 1<=i<k，那么这个序列称为从 n 开始的路径1到 n k。路径的长度为 k-1。如果存在从节点 R 到节点 M 的路径，则 R 是 M 的祖先，M 是 R 的后代。因此，树中的所有节点都是树根的后代，而根是祖先的所有节点。树中节点 M 的深度是从树的根到 M 的路径长度。树的高度比树中最深节点的深度大一。深度为 d 的所有节点都位于树中的第 d 层。根是唯一处于级别 0 的节点，其深度为 0。

图 7.2.1

图 7.2.1：二叉树。节点 A 是根。节点 B 和 C 是 A 的子节点。节点 B 和 D 一起形成一个子树。节点 B 有两个孩子：它的左孩子是空树，右孩子是 D。节点 A、C 和 E 是 G 的祖先。节点 D、E 和 F 构成树的第 2 层；节点 A 位于级别 0。从 A 到 C 到 E 到 G 的边形成长度为 3 的路径。节点 D、G、H 和 I 是叶子。节点 A、B、C、E 和 F 是内部节点。I 的深度是 3。这棵树的高度是 4。

于 2017-04-13T07:34:15.907 回答
2

Daniel AA Pelsmaeker 和 Yesh 类比的答案非常好。我想从hackerrank教程中添加更多内容。希望它也有帮助。

  • 节点的深度（或级别）是它与树根节点的距离（即没有边）。
  • 高度是根节点和最远叶子之间的边数。
  • 高度（节点）= 1 + 最大值（高度（节点.leftSubtree），高度（节点.rightSubtree））。
    在阅读前面的示例之前，请记住以下几点。
  • 任何节点的高度都是 1。
  • 空子树的高度为-1。
  • 单元素树或叶节点的高度为 0。
    计算树高的示例
于 2020-06-28T06:21:28.097 回答
0

节点的“深度”（或等效的“级别数”）是从根节点开始的“路径”上的边数

节点的“高度”是从节点到叶节点的最长路径上的边数。

于 2020-12-08T17:17:46.523 回答
-1

树的总深度等于树的高度，并且树的级别也相同，但是如果对于特定节点，高度不等于深度，因为深度的定义表明从根节点开始的最长路径到那个节点，在高度的情况下，它是从那个节点到叶节点。

整体树，D=H=L 但对于一个节点 D=L 但 D 可能不等于 H。

于 2021-06-03T13:11:35.827 回答