这是算法理论中的一个简单问题。 它们之间的区别是,在一种情况下,你计算节点的数量,在另一种情况下,计算根节点和具体节点之间最短路径上的边的数量。 哪个是哪个?


当前回答

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

摘自OpenDSA数据结构和算法书:

If n1, n2,...,nk is a sequence of nodes in the tree such that ni is the parent of ni+1 for 1<=i<k, then this sequence is called a path from n1 to nk. The length of the path is k−1. If there is a path from node R to node M, then R is an ancestor of M, and M is a descendant of R. Thus, all nodes in the tree are descendants of the root of the tree, while the root is the ancestor of all nodes. The depth of a node M in the tree is the length of the path from the root of the tree to M. The height of a tree is one more than the depth of the deepest node in the tree. All nodes of depth d are at level d in the tree. The root is the only node at level 0, and its depth is 0. Figure 7.2.1: A binary tree. Node A is the root. Nodes B and C are A's children. Nodes B and D together form a subtree. Node B has two children: Its left child is the empty tree and its right child is D. Nodes A, C, and E are ancestors of G. Nodes D, E, and F make up level 2 of the tree; node A is at level 0. The edges from A to C to E to G form a path of length 3. Nodes D, G, H, and I are leaves. Nodes A, B, C, E, and F are internal nodes. The depth of I is 3. The height of this tree is 4.

其他回答

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

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

深度:


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

高度:


节点的高度是从该节点到树中最深节点的路径长度。树的高度是树中从根节点到最深节点的路径长度。(例如:上面例子中的树的高度是4(计算边,而不是节点))。 只有一个节点的树高度为零。

要了解更多关于树的基础知识,请访问:树的介绍和属性

树的整体深度等于树的高度,树的级别也一样,但如果对于特定的节点高度不等于深度,因为深度的定义表明从根节点到该节点的最长路径,对于高度,它是从该节点到叶节点。

总体树,D=H=L 但D可能不等于H。

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

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

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

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

另一种理解这些概念的方式如下: 深度:在根位置画一条水平线,并将这条线作为地面。所以根结点的深度是0,它所有的子结点都向下增长所以每一层结点的深度都是+ 1。

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