首页 文章

二进制树中节点的高度和深度概念之间的混淆

提问于
浏览 次
1

我一直在研究二叉树，并发现每个其他源都给出了二叉树中节点深度和高度的不同概念 .

我的想法

Height =从给定节点到叶节点的路径的最大长度 . Depth =从给定节点到根节点的边数 .

/*         
         *         1         (1)    level = 1, height = 3, depth = 0
         *        / \ 
         *       2   3       (3)    level = 2, height = 0, depth = 1
         *      / \    
         *     4   5         (5)    level = 3, height = 1, depth = 2
         *        / \ 
         *       6   7       (6, 7) level = 4, height = 0, depth = 3
         */

我已经从这个blog post中得到了这个概念，但是当只有一个节点，即root的高度为 1 时，我很困惑 .

algorithm binary-tree graph-theory

3 回答

  • 0

    嗯，水平只是一个不直观的词，因为我们在视觉表现中看待树木之类的东西 .

    根据这篇博客文章，节点的级别由1定义节点和根之间的连接数 .

    在这种情况下，所有这些级别都有意义 . 7与1相距3个连接 .

    但是，您也有一些不正确的高度 . 请记住，高度是从节点到叶子的最长路径 . 所以A的高度是到E的路径的边数，而不是G.它的高度是3 .

    5
 /  \
6    7

    在该示例中，5具有1行子节点，并且那些子节点是叶节点，因此它的高度为1.但是如果您将6和7视为单独的树本身，则它们的高度为0，因为它们是叶节点 .

    回复于
  • 0

    简单来说，节点的深度是从根到达该节点必须遍历的边数 . 节点的高度是您必须从该节点开始向下遍历以到达最远节点的边数 . 树的高度是其根的高度 .

    回复于
  • 0

    从您链接的帖子：

    Height of node – The height of a node is the number of edges on the longest downward path between that node and a leaf.

    我认为它说根的高度是1，参考单根的例子 .

    在你的例子中，我认为它应该是：

    /*         
     *         1         (1)    level = 1, height = 3, depth = 0
     *        / \ 
     *       2   3       (3)    level = 2, height = 0, depth = 1
     *      / \    
     *     4   5         (5)    level = 3, height = 1, depth = 2
     *        / \ 
     *       6   7       (6, 7) level = 4, height = 0, depth = 3
     */

    edit: Ok you corrected your post, so the relevant point in my post is I think it say the height of the root is 1, refering to the example with the single root.

    回复于

相关问题