Binary Tree

A binary tree is a tree where every node has two or fewer children. The children are usually called…

A binary tree is a tree where every node has two or fewer children. The children are usually called left and right.


class BinaryTreeNode(object):

    def __init__(self, value):
        self.value = value
        self.left  = None
        self.right = None

This lets us build a structure like this:


That particular example is special because every level of the tree is completely full. There are no "gaps." We call this kind of tree "perfect".


Binary trees have a few interesting properties when they're perfect:


Property 1: the number of total nodes on each "level" doubles as we move down the tree.

属性 1:当我们沿着树向下移动时,每个“级别”上的总节点数将增加一倍。

Property 2: the number of nodes on the last level is equal to the sum of the number of nodes on all other levels (plus 1). In other words, about half of our nodes are on the last level.

属性 2:最后一层的节点数等于所有其他层的节点数之和(加1)。 换句话说,大约一半的节点位于最后一层。

Let's call the number of nodes n , and the height of the tree h . h can also be thought of as the "number of levels."

我们称节点数为 n,树的高度为 h,h 也可以认为是“级别数”。

If we had h , how could we calculate n ?

如果我们有 h,我们如何计算 n?

Let's just add up the number of nodes on each level! How many nodes are on each level?


If we zero-index the levels, the number of nodes on the xth level is exactly 2x.

如果我们对层进行零索引,那么第 x 层的节点数正好是 2x

  1. Level 0: 20 nodes,
  2. Level 1: 21 nodes,
  3. Level 2: 22 nodes,
  4. Level 3: 23 nodes,
  5. etc

So our total number of nodes is:


n = 20 + 21 + 22 + 23 + … + 2h-1

Why only up to 2h-1? Notice that we started counting our levels at 0. So if we have h levels in total, the last level is actually the "h-1"-th level. That means the number of nodes on the last level is 2h-1.

为什么只有 2h-1? 请注意,我们从 0 开始计算级别。因此,如果我们总共有 h 个级别,则最后一个级别实际上是第“h-1”个级别。 这意味着最后一级的节点数为 2h-1

But we can simplify. Property 2 tells us that the number of nodes on the last level is (1 more than) half of the total number of nodes, so we can just take the number of nodes on the last level, multiply it by 2, and substract 1 to get the number of nodes overall. We know the number of nodes on the last level is 2h-1, So:

但是我们可以简化。 属性 2 告诉我们,最后一级的节点数是节点总数的一半(多1个),因此我们可以取最后一级的节点数乘以 2,然后将 1 减去获取总体节点数。 我们知道最后一级的节点数为2h-1,因此:

n = 2h-1 * 2 - 1
n = 2h-1 * 21 - 1
n = 2h-1 + 1 - 1
n = 2h - 1

So that's how we can go from h to n . What about the other direction?

这就是我们从 h 到 n 的方式。那另一个方向呢?

We need to bring the h down from the exponent. That's what logs are for!

我们需要把 h 从指数上拿下来,这就是 log 的作用!

First, some quick review. log10(100) simply means, "What power must you raise 10 to in order to get 100?". Which is 2, because 102 = 100.

首先,快速回顾一下。 log10(100) 简单的意思是,“要得到100,你必须取 10 的几次方?”是 2,因为 102 = 100。

We can use logs in algebra to bring variables down from exponents by exploiting the fact that we can simplify log10(102). What power must have raise 10 to in order to get 102? That's easy – it's 2.

我们可以在代数中使用对数,利用可以简化 log10(102) 这一事实,把变量从指数中拿出来。10 的几次方等于 102?很简单,是 2。

So in this case we can take the log2 of both sides:

在这种情况下,我们可以两边取 log2 :

n = 2h - 1
n + 1 = 2h
log2((n + 1)) = log2(2h)
log2(n + 1) = h

So that's the relationship between height and total nodes in a perfect binary tree.


Date: 2020-01-30 Thu 19:34

Author: Jack Liu

Created: 2020-02-08 Sat 21:25