二叉树中的树叶数

我是二叉树的初学者，一直在通过算法书工作。我已经了解了BST的各种遍历方法（预订，后期订单等）。二叉树中的树叶数

请问有人能解释一下如何遍历一个BST来计算树叶节点的数量（没有孩子）吗？

非常感谢！

来源

2013-10-24 Has

使用递归方法：对于叶返回1，对于非叶，返回应用于其子级的该方法的总和。 –

使用您列出的任何遍历（预先订购DFS，后期DFS，BFS），并测试您当前访问的节点是否没有子节点。如果是这样，请将计数器增加1. –

谢谢！是否有一个基本的实现，你会推荐PLZ？ – Has

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

我假设你有一个BST，它由Node类型的对象组成。节点具有类型为Node的left和right两个字段，它们是节点的子节点。如果孩子不在场，该字段的值为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); 
}

来源

2013-10-24 15:07:35

伴侣！我读过这么多书并观看在线教程。这是迄今为止我所遇到过的最好的逆转BST的最好解释！非常感谢！ – Has

使用递归方法：

对于叶回报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-24 14:35:42 Oswald

很好措辞;-) +1 –

谢谢你。你已经回答了这个问题。你能不能推荐一个非常基本的实现PLZ？ – Has

非常感谢实施。如果您能用英语解释您在函数countLeafs（BST $ b）中的做法，我将非常感激！ – Has

试试这个

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-26 05:53:01 Nishant

二叉树中的树叶数

回答

相关问题