Количество листьев в двоичном дереве

Question

Я начинаю с бинарных деревьев и прокладываю себе путь через книгу алгоритмов. Я узнал о различных методах обхода BST (предварительный заказ, почтовый заказ и т. Д.).

Не могли бы вы объяснить, как можно пересечь BST, чтобы подсчитать количество узлов, которые являются листьями (без детей), пожалуйста?

Большое спасибо!

Answer 1

Различные методы обхода может привести к различным алгоритмам (хотя для простой задачи, как это, все варианты DFS более или менее то же самое).

Я предполагаю, что у вас есть BST, который состоит из объектов типа Node. У узла есть два поля left и right типа Node, которые являются дочерними узлами узла. Если ребенка нет, значение этого поля равно null. На все дерево ссылается ссылка на корень, называемый root. В Java:

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

Node root; 

ДФС проще всего реализовать с помощью рекурсии: определить метод

int numberOfLeafs(Node node) 

, которая возвращает количество листьев в поддереве с корнем по node. Конечно, numberOfLeafs(root) должно давать количество листьев всего дерева.

Как уже говорилось, это действительно искусственно различать, сессионной и пост порядка обхода здесь, но я собираюсь сделать это в любом случае:

Предзаказ ДФС: Первая сделка с текущий узел, а затем вместе с детьми

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

В заказ ДФС: Первая сделка с левым ребенком, то с текущим узлом, а затем с правым ребенком

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

после заказа ДФС: Первая сделка с детьми, то с текущим узлом

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

Answer 2

Используйте рекурсивный метод:

• Для листа возвращения 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 3

попробовать это

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

рекурсивно подсчитывает листовыми узлы для левого и правого вспомогательные деревья и возвращает общее количество