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

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

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

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

树的属性：

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

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

https://i.stack.imgur.com/8yPi9.png

---

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

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

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

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

---

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

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

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

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

---

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

---

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

---

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

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

---

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

从 OpenDSA Data Structures & Algos book：

如果 n1, n2,...,nk 是树中的节点序列，使得 ni 是 1<=i

---

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

节点的深度（或级别）是它与树根节点的距离（即没有边）。

高度是根节点和最远叶子之间的边数。

高度（节点）= 1 + 最大值（高度（节点.leftSubtree），高度（节点.rightSubtree））。在阅读前面的示例之前，请记住以下几点。

任何节点的高度都是 1。

空子树的高度为-1。

单元素树或叶节点的高度为 0。

---

深度：

树中节点的深度是从根到节点的路径长度。树的深度是树中所有节点中的最大深度。

https://i.stack.imgur.com/aBbeM.jpg

高度：

节点的高度是从该节点到树中最深节点的路径长度。树的高度是从根节点到树中最深节点的路径长度。 （例如：上例中树的高度是四（计算边，而不是节点））。只有一个节点的树的高度为零。

有关树木基础知识的更多参考，请访问：INTRODUCTION AND PROPERTIES OF TREES

---

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

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

---

深度：节点上方有多少条边，即节点的深度高度：节点下方有多少条边，即节点的高度

 Node1 // depth = 0 and height = 2 => root node
  |
 / \
Node2 Node3 //depth = 1 and height = 1
|     |
Node4 Node5  //depth = 2 and height = 0  => leaf node```

---

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

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

---