3

我是二叉树的初学者，并且一直在学习算法书。我已经了解了 BST 的各种遍历方法（预购、后购等）。

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

非常感谢！

4

3 回答 3

6

使用递归方法：

  • 对于叶子返回 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;
  }
}
于 2013-10-24T14:35:42.870 回答
5

不同的遍历方法会导致不同的算法（尽管对于像这样的简单问题，所有 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)应该是整棵树的叶子数。

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

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

In-order 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);
}
于 2013-10-24T15:07:35.227 回答
0

尝试这个

int countLeafNodes(BTNode node) { 
if (node == null)
        return 0;
    if (node.getLeftChild() == null && node.getRightChild() == null
            && node.getParent() != null)//this is a leaf, no left or right child
        return 1;
    else
        return countLeafNodes(node.getLeftChild())
                + countLeafNodes(node.getRightChild());
}

递归计算左右子树的叶节点并返回总计数

于 2013-10-26T05:53:01.333 回答