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

我了解到深度和高度是 结点 :

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

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

A的性质 树 :

• 这个 高度 一棵树的根节点的高度,
  或者等效地,它最深节点的深度。

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

树的高度和深度相等…

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

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

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

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

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

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

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

简单回答:
深度:
1。 树 : 边数/弧数 从树的根节点到叶节点称为树的深度。
2。 结点 : 边数/弧数 从根节点到该节点称为该节点的深度。

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

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

我想写这篇文章是因为我是一个本科的cs学生,而且我们越来越多地使用opendsa和其他开源教科书。从最高分的答案来看,人们学习高度和深度的方式从一代人到下一代人都发生了变化,我发布这篇文章是为了让每个人都意识到这种差异现在已经存在,希望不会在任何程序中引起错误!谢谢。

从 OpenDSA Data Structures & Algos book :

如果n _一 ,n _二 ,…,n _K 树中的节点序列 那个n _我 是n的父母 _我 +1:1<=i<k,则此序列 称为n的路径 _一 n _K . 这条路的长度是k1。 如果存在从节点r到节点m的路径,则r是 m,m是r的后代。因此,树中的所有节点都是 树根的后代,而树根是 所有节点。 树中节点m的深度是 从树根到m的路径。树的高度是 比树上最深节点的深度还要深。 深度d的所有节点 在树的D层。根节点是级别0的唯一节点,并且 它的深度是0。

图7.2.1:二叉树。节点A是根节点。节点b和c是 A的孩子们。节点b和d一起构成子树。Node B有 两个孩子:左边的孩子是空树,右边的孩子是 d.节点a、c和e是g.节点d、e和f的祖先 构成树的级别2;节点A位于级别0。从一个 到C到E到G形成一条长度为3的路径。节点D、G、H和I 是树叶。节点A、B、C、E和F是内部节点。深度 我是3岁。这棵树的高度是4。