树深度和高度有什么区别？

Question

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

Answer 1

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

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

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

树的属性:

• 的高度树将是其根节点的高度,
  或等价地,其最深节点的深度.

• 的直径(或宽度树)是数量节点的任意两个叶节点之间的最长路径上.下面的树有6个节点的直径.

Answer 2

树的高度和深度相等......

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

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

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

Answer 3

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

请注意,简单路径是没有重复顶点的路径.

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

我有时会遇到一个问题,要求人们计算节点(顶点)而不是边缘,所以如果你不确定在考试或求职面试中你应该计算节点或边缘,请要求澄清.

Answer 4

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

Answer 5

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

Answer 6

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

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