这是算法理论中的一个简单问题。 它们之间的区别是,在一种情况下,你计算节点的数量,在另一种情况下,计算根节点和具体节点之间最短路径上的边的数量。 哪个是哪个?
当前回答
深度:节点上面有多少条边,这就是节点的深度 高度:节点下面有多少条边,即节点的高度
Node1 // depth = 0 and height = 2 => root node
|
/ \
Node2 Node3 //depth = 1 and height = 1
| |
Node4 Node5 //depth = 2 and height = 0 => leaf node```
其他回答
我了解到深度和高度是节点的属性:
节点深度是指从该节点到树的根节点的边数。根节点的深度为0。 节点的高度是指从该节点到叶节点的最长路径上的边数。叶节点的高度为0。
树的属性:
树的高度是它的根节点的高度,或者等价地,是它最深节点的深度。 树的直径(或宽度)是任意两个叶节点之间的最长路径上的节点数。下面的树直径为6个节点。
Daniel A.A. pelsmaker的回答和Yesh的类比非常棒。我想从hackerrank教程中添加更多。希望这也能有所帮助。
节点的深度(或层次)是它的距离(即。从树的根节点开始。 高度是根节点和最远叶之间的边数。 height(node) = 1 + max(height(node. leftsubtree),height(node. rightsubtree)))。 在阅读下面的示例之前,请记住以下几点。 任何节点的高度都是1。 空子树的高度是-1。 单元素树或叶节点的高度为0。
树的高度和深度是相等的……
但是节点的高度和深度是不相等的,因为…
高度是通过从给定节点遍历到可能最深的叶来计算的。
深度是从根到给定节点.....的遍历计算的
根据Cormen等人。算法简介(附录B.5.3),树T中节点X的深度定义为从T的根节点到X的简单路径的长度(边数),节点Y的高度是从Y到叶子的最长的向下简单路径上的边数。树的高度定义为其根节点的高度。
注意,简单路径是没有重复顶点的路径。
树的高度等于树的最大深度。节点的深度和高度不一定相等。这些概念的说明见Cormen et al.第三版的图B.6。
我有时会遇到要求计算节点(顶点)而不是边的问题,所以如果你不确定是否应该在考试或工作面试中计算节点或边,就要求澄清。
节点的“深度”(或等效的“层数”)是根节点“路径”上的边数
节点的“高度”是指从该节点到叶节点的最长路径上的边数。