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

这是一个来自algorithm理论的简单问题。 它们之间的区别在于，在一种情况下，您可以统计根节点和具体节点之间最短path上的节点数量和其他数量的边界。 哪个是哪个？

Answer 1

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

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

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

树的属性：

• 树的高度将是其根节点的高度，
  或者等同于其最深节点的深度。

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

Answer 2

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

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

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

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

Answer 3

根据Cormen et al。 algorithm介绍（附录B.5.3）中，树T中节点X的深度被定义为从T到X的根节点的简单path（边的数量）的长度。节点Y的高度是从Y到叶子最长的向下简单path上的边数。 树的高度被定义为其根节点的高度。

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

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

我有时会看到一些问题，要求人们计算节点（顶点）而不是边缘，所以如果您不确定在考试或面试时是否应该计算节点或边缘，请要求澄清。

Answer 4

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

Answer 5

理解这些概念的另一种方法如下：深度：在根的位置画一条水平线，并把这条线作为地面。 所以根的深度是0，所有的子节点都是向下的，所以每一个节点的深度都是+ 1。

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

Answer 6

我想发表这篇文章，因为我是一名本科生，越来越多的人使用OpenDSA和其他开放源码的教科书。 从最高评价的答案看来，高度和深度被教的方式已经从一代人变成了另一代，我发布这个，所以每个人都知道这种差异现在存在，并希望不会造成任何错误程式！ 谢谢。

从OpenDSA数据结构和algorithm书 ：

如果n ₁ ，n ₂ ，…，n _k是树中的一个节点序列，使得n _i是n _i + 1的父节点，1 <= i <k，那么这个序列称为从n ₁到n _k 。 path的长度是k-1。 如果存在从节点R到节点M的path，则R是M的祖先，并且M是R的后代。因此，树中的所有节点都是树的根的后代，而根是祖先的所有节点。 树中的节点M的深度是从树的根到M的path的长度。树的高度比树中最深的节点的深度大1。 深度d的所有节点都在树中的级别d上。 根是0级的唯一节点，深度为0。

图7.2.1：二叉树 节点A是根。 节点B和C是A的孩子。 节点B和D一起形成一个子树。 节点B有两个孩子：其左边的孩子是空树，右边的孩子是D.节点A，C和E是G的祖先。节点D，E和F组成树的第二级; 节点A在等级0处。从A到C到E到G的边形成长度为3的path。节点D，G，H和I是叶子。 节点A，B，C，E和F是内部节点。 我的深度是3.这棵树的高度是4。