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

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

一些特性如下 −

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

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

更新日期： 2019 年 8 月 27 日

4K+ 次浏览

开启你的 职业生涯

完成课程，获得认证

开始学习
广告