我是二叉树的初学者,一直在努力学习算法书。我了解了 BST 的各种遍历方法(前序、后序等)。
有人可以解释一下如何遍历 BST 来计算叶子节点(没有子节点)的数量吗?
非常感谢!
最佳答案
使用递归方法:
- 对于叶子返回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;
}
}
关于algorithm - 二叉树中的叶子数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19568800/