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

Question

Я отправляю новый вопрос с моим кодом. Я пытаюсь сосчитать неконечные узлы двоичного дерева поиска. Я создаю не листовой метод, а затем пытаюсь вызвать его в тестовом классе. Кто-нибудь может мне помочь? Вот код:

public class BST {
    private Node<Integer> root;

    public BST() {
        root = null;
    }

    public boolean insert(Integer i) {
        Node<Integer> parent = root, child = root;
        boolean gLeft = false;

        while (child != null && i.compareTo(child.data) != 0) {
            parent = child;
            if (i.compareTo(child.data) < 0) {
                child = child.left;
                gLeft = true;
            } else {
                child = child.right;
                gLeft = false;
            }
        }

        if (child != null)
            return false;
        else {
            Node<Integer> leaf = new Node<Integer>(i);
            if (parent == null)
                root = leaf;
            else if (gLeft)
                parent.left = leaf;
            else
                parent.right = leaf;
            return true;
        }
    }

    public boolean find(Integer i) {
        Node<Integer> n = root;
        boolean found = false;

        while (n != null && !found) {
            int comp = i.compareTo(n.data);
            if (comp == 0)
                found = true;
            else if (comp < 0)
                n = n.left;
            else
                n = n.right;
        }

        return found;
    }

    public int nonleaf() {
        int count = 0;
        Node<Integer> parent = root;

        if (parent == null)
            return 0;
        if (parent.left == null && parent.right == null)
            return 1;
    }

}

class Node<T> {
    T data;
    Node<T> left, right;

    Node(T o) {
        data = o;
        left = right = null;
    }
}

Answer 1

Вы можете использовать следующую функцию для подсчета количества неконечных узлов двоичного дерева.

int countNonLeafNodes(Node root)
{ 
    if (root == null || (root.left == null &&  
                         root.right == null)) 
        return 0; 
    return 1 + countNonLeafNodes(root.left) +  
               countNonLeafNodes(root.right); 
}

Answer 2

Если вас интересует только количество неконечных узлов, вы можете пройти по дереву один раз и сохранить один счет. всякий раз, когда вы сталкиваетесь с таким узлом, что он имеет счетчик приращений левого или правого узла.