二叉树中的叶子数量

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;
  }
}

Answer 2

不同的遍历方法会导致不同的算法（尽管对于像这样的简单问题，所有 DFS 变体或多或少都相同）。

我假设您有一个由类型为 的对象组成的 BST Node。一个节点有两个字段left和righttype Node，它们是节点的子节点。如果孩子不存在，则该字段的值为null。整个树由对根的引用引用，称为root。在Java中：

class Node {
    public Node left;
    public Node right;
}

Node root;

DFS 最容易通过递归实现：定义一个方法

int numberOfLeafs(Node node)

它返回以 为根的子树中的叶子数node。当然，numberOfLeafs(root)应该产生整棵树的叶子数。

如前所述，在这里区分前序、内序和后序遍历确实是人为的，但无论如何我还是要这样做：

预购DFS：先处理当前节点，再处理子节点

int numberOfLeafs(Node node) {
    int result = 0;
    if (node.left == null && node.right == null)
        result += 1;
    if (node.left != null)
        result += numberOfLeafs(node.left)
    if (node.right != null)
        result += numberOfLeafs(node.right)
    return result;
}

中序DFS：首先处理左孩子，然后是当前节点，然后是右孩子

int numberOfLeafs(Node node) {
    int result = 0;
    if (node.left != null)
        result += numberOfLeafs(node.left)
    if (node.left == null && node.right == null)
        result += 1;
    if (node.right != null)
        result += numberOfLeafs(node.right)
    return result;
}

后序DFS：先处理子节点，再处理当前节点

int numberOfLeafs(Node node) {
    int result = 0;
    if (node.left != null)
        result += numberOfLeafs(node.left)
    if (node.right != null)
        result += numberOfLeafs(node.right)
    if (node.left == null && node.right == null)
        result += 1;
    return result;
}

对于BFS，您通常使用带有队列的简单循环，在其中添加未访问的顶点。我现在假设我有一个类Queue，我可以add在最后take结点，从前面结点：

Queue queue = new Queue();
queue.add(root);
int numberOfLeafs = 0;
while (!queue.empty) {
    // take an unhandled node from the queue
    Node node = queue.take();

    if (node.left == null && node.right == null)
        numberOfLeafs += 1;
    if (node.left != null)
        queue.add(node.left);
    if (node.right != null)
        queue.add(node.right);
}