17.`AVL`树的挑战¶

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

挑战1：叶子的数量¶

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

挑战2：结点的数量¶

一棵高度为3的完全平衡树有多少个nodes？高度为h的完全平衡树呢？

挑战3：一个树形遍历协议¶

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

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

Note

你需要把AVLNode变成一个最终类，因为该协议会有Self的要求。

解决方案¶

挑战1的解决方案¶

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

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

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

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

挑战2的解决方案¶

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

func nodes(inTreeOfHeight height: Int) -> Int {
  var totalHeight = 0
  for currentHeight in 0...height {
    totalHeight += Int(pow(2.0, Double(currentHeight)))
  }
  return totalHeight
}

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

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

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

挑战3的解决方案¶

首先，创建以下协议：

protocol TraversableBinaryNode {

  associatedtype Element
  var value: Element { get }
  var leftChild: Self? { get }
  var rightChild: Self? { get }
  func traverseInOrder(visit: (Element) -> Void)
  func traversePreOrder(visit: (Element) -> Void)
  func traversePostOrder(visit: (Element) -> Void)
}

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

extension TraversableBinaryNode {

  func traverseInOrder(visit: (Element) -> Void) {
    leftChild?.traverseInOrder(visit: visit)
    visit(value)
    rightChild?.traverseInOrder(visit: visit)
  }

  func traversePreOrder(visit: (Element) -> Void) {
    visit(value)
    leftChild?.traversePreOrder(visit: visit)
    rightChild?.traversePreOrder(visit: visit)
  }

  func traversePostOrder(visit: (Element) -> Void) {
    leftChild?.traversePostOrder(visit: visit)
    rightChild?.traversePostOrder(visit: visit)
    visit(value)
  }
}

接下来，进入AVLNode.swift更新类型声明，加入final关键字：

public final class AVLNode<Element>

最后，在Playground的底部添加以下内容：

extension AVLNode: TraversableBinaryNode {}

example(of: "using TraversableBinaryNode") {
  var tree = AVLTree<Int>()
  for i in 0..<15 {
    tree.insert(i)
  }
  tree.root?.traverseInOrder { print($0) }
}

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

---Example of: using TraversableBinaryNode---
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14

17.AVL树的挑战¶