第17章：AVL树进阶

这里有三个围绕AVL树的挑战。解决这些问题以确保你掌握了这些概念。

挑战1：叶子的数量

一棵高度为3的完全平衡树有多少个叶子结点？高度为h的完全平衡树呢？

挑战2：结点的数量

高度为3的完全平衡树有多少个节点？高度为h的完全平衡树呢？

挑战3：树的遍历协议

由于二叉树有许多变种，因此将共享功能归入一个协议是有意义的。遍历方法就是一个很好的候选方案。

创建一个TraversableBinaryNode协议，提供一个默认的遍历方法的实现，这样符合要求的类型就可以免费获得这些方法。让AVLNode符合这个协议。

注意：你需要让AVLNode成为一个最终类，因为该协议会有Self要求。

解决方案

挑战1的解决方案

完全平衡的树是指所有的叶子都在同一层次，而且该层次完全被填满的树。

回顾一下，只有一个根节点的树的高度为零。因此，上面的例子中的树的高度是2。你可以推断，一棵高度为三的树将有八个叶子节点。

由于每个节点都有两个子节点，所以随着高度的增加，叶子节点的数量会增加一倍。你可以用一个简单的方程式来计算叶子结点的数量。

func leafNodes(inTreeOfHeight height: Int) -> Int { 
  Int(pow(2.0, Double(height))) 
}

挑战2的解决方案

由于树是完全平衡的，高度为3的完全平衡的树的节点数可以用以下方法表示。

虽然这肯定会给你正确的答案，但有一个更快的方法。如果你检查一连串高度输入的结果，你会发现节点的总数比下一级的叶子节点的数量少一个。

因此，一个更快的版本是这样的。

func nodes(inTreeOfHeight height: Int) -> Int {
  Int(pow(2.0, Double(height + 1))) - 1
}

挑战3的解决方案

首先，创建以下协议。

然后添加一个协议扩展，为遍历方法提供实现。

接下来，进入AVLNode.swift更新类型声明，加入最后的关键字。

public final class AVLNode<Element>

最后，在playground的底部添加以下内容。

确认你在控制台中得到以下结果。

---

上一章	目录	下一章