数据结构中的二叉树和树的特性


在本节中,我们将看到一棵二叉树数据结构的一些重要特性。假设我们有一棵这样的二叉树。

一些特性如下 −

  • 第 l 层的最大节点数将是 2l1 。这里的层是根到节点的路径上的节点数,包括根节点本身。我们认为根的层是 1。
  • 高度为 h 的二叉树中存在的最大节点数是 2h1 。这里的 height 是根到叶路径上的最大节点数。我们认为一个节点的树的高度是 1。
  • 在有 n 个节点的二叉树中,可能的最小高度或最小层数为log2n+1 。如果我们认为叶子节点的高度为 0,那么该公式将为 log2n+11
  • 有 L 个叶子的二叉树至少有 log2L+1 个层
  • 如果二叉树有 0 个或 2 个子节点,那么叶子节点的数量总是比有两个子节点的节点多一个。

N.B. 由于二叉树是一棵树,它具有图论中树的所有特性。

更新日期: 2019 年 8 月 27 日

4K+ 次浏览

开启你的 职业生涯

完成课程,获得认证

开始学习
广告