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

我了解到depth和height是节点的属性:

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

• 一个节点的height是指从该节点到叶的最长路径上的边数。
  叶节点的高度为0。

树的属性:

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

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

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

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

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

我有时会遇到要求计算节点(顶点)而不是边的问题，所以如果你不确定是否应该在考试或工作面试中计算节点或边，就要求澄清。

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

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

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

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

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

我想写这篇文章是因为我是一名计算机专业的本科生，我们越来越多地使用OpenDSA和其他开源教科书。从评分最高的答案来看，似乎教高度和深度的方式一代一代都在改变，我把这篇文章贴出来是为了让每个人都意识到这种差异现在是存在的，希望不会在任何程序中导致错误!谢谢。

从OpenDSA数据结构&算法的书:

If n₁, n₂，…，n_k是树中的节点序列 n_我是1<=i<k的n_我+1的父元素，那么这个序列 称为从n₁到n_k的路径。路径长度为k−1。 如果存在从节点R到节点M的路径，则R是的祖先 M是r的后代，因此，树中的所有节点都是 树根是树的后代，而树根是树的祖先 所有节点。树中节点M的深度等于节点M的长度 从树的根到m的路径。树的高度是1 大于树中最深节点的深度。所有深度为d的节点 在树的d层。根节点是级别为0的唯一节点，并且 深度为0

.

图7.2.1:二叉树。节点A是根节点。节点B和节点C为 一个的孩子。节点B和D一起构成一个子树。节点B已 它的左子元素是空树，右子元素是空树 D.节点A、C、E是g的祖先 构成树的第2层;节点A为0级。来自A的边 到C到E到G形成一条长度为3的路径。节点D、G、H、I 是树叶。节点A、B、C、E、F为内部节点。深度 I的值是3。这个树的高度是4

Daniel A.A. pelsmaker的回答和Yesh的类比非常棒。我想从hackerrank教程中添加更多。希望这也能有所帮助。

• 节点的深度(或层次)是它的距离(即。从树的根节点开始。
• 高度是根节点和最远叶之间的边数。
<李> height(node) = 1 + max(height(node. leftsubtree)，height(node. rightsubtree))。
在阅读下面的示例之前，请记住以下几点
• 任何节点的高度都是1。
• 空子树的高度是-1。
• 单个元素树或叶节点的高度为0。
  李 < / >

节点的“深度”(或等效的“层数”)是根节点“路径”上的边数

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

我知道这很奇怪，但是Leetcode也根据路径上的节点数量来定义深度。因此，在这种情况下，深度应该从1开始(总是计算根)，而不是0。以防有人和我一样有同样的困惑。

树的整体深度等于树的高度，树的级别也是如此，但如果对于特定的节点高度不等于深度，因为深度的定义指出从根节点到该节点的最长路径，在高度的情况下，它是从该节点到叶节点。

整体树，D=H=L 但是D可能不等于h。

深度:节点上面有多少条边，即节点的深度
Height:节点下面有多少条边，即节点的高度

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

1. 深度:

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

2. 高度:

有关树基础知识的更多参考，请访问:树木的介绍和性质

节点的深度是指从树的根节点到该节点的路径中存在的边数。

节点的高度是连接该节点到叶节点的最长路径中存在的边数。