algorithm - 二叉树中的叶子数

Question

我是二叉树的初学者，一直在努力学习算法书。我了解了 BST 的各种遍历方法(前序、后序等)。

有人可以解释一下如何遍历 BST 来计算叶子节点(没有子节点)的数量吗？

非常感谢!

Answer 1

使用递归方法:

• 对于叶子返回1。
• 对于非叶节点，返回应用于其子节点的该方法的总和。

PHP 示例:

class BST {
  public $left;  // The substree containing the smaller entries
  public $right; // The substree containing the larger entries
  public $data;  // The value that is stored in the node
}

function countLeafs(BST $b) {
  // Test whether children exist ...
  if ($b->left || $b->right) {
    // ... yes, the left or the right child exists. It's not a leaf.
    // Return the sum of calling countLeafs() on all children.
    return ($b->left  ? countLeafs($b->left)  : 0)
         + ($b->right ? countLeafs($b->right) : 0);
  } else {
    // ... no, it's a leaf
    return 1;
  }
}