Подсчет левых дочерних узлов в дереве

Я должен реализовать рекурсивный метод, который подсчитывает количество левых дочерних узлов дерева. Мой код до сих пор:

private int countLeftNodes(IntTreeNode node){
    int c = 0;
    if (node != null){
        c = 1 + countLeftNodes(node.left);
        countLeftNodes(node.right);
    }

    return c;
}

Он возвращает число, намного меньшее, чем должно быть. У меня такое ощущение, что мой обход отключен, потому что он, кажется, считает только самые левые дочерние узлы, а затем завершается. Когда я вызываю этот метод для IntTree размера 16, я должен получить 8 левых дочерних узлов, 7 правых дочерних узлов и один корень, но вместо этого я получаю 4 левых дочерних узла.


java nodes data-structures tree
person Shane    schedule 21.03.2011    source источник
comment
Вы не добавляете левые узлы правого дочернего элемента.   -  person Zimbabao    schedule 21.03.2011

Ответы (4)


arrow_upward
9
arrow_downward

Вы никогда не считаете левые узлы в правом дереве.

private int countLeftNodes(IntTreeNode node)
{
    int c = 0;
    if (node.left != null)
    {
        c += 1 + countLeftNodes(node.left);
    }
    if(node.right != null)
    {
        c += countLeftNodes(node.right);
    }

    return c;
}
person Endophage    schedule 21.03.2011
comment
Я пробовал это, однако он возвращает количество узлов во всем дереве. - person Shane; 21.03.2011
comment
Да, я понимаю, почему, одну минуту я исправлю - person Endophage; 21.03.2011
comment
@Шейн теперь должен работать. В основном он смотрит вперед и добавляет один, если левый дочерний элемент не равен нулю. - person Endophage; 21.03.2011
comment
Вы можете добавить проверку, чтобы увидеть, является ли сам узел нулевым, чтобы учесть случай нулевого корневого узла. - person Endophage; 21.03.2011
comment
о! Да, я вижу это сейчас. Как же я не мог подумать об этом раньше! Большое спасибо! - person Shane; 21.03.2011
comment
@Shane хорошо хорошо :) Каждому нужно немного времени, чтобы получить рекурсию. - person Endophage; 21.03.2011
comment
@Shane: здесь, в stackoverflow, вы можете пометить ответ как принятый, щелкнув правую отметку рядом с ответом. - person codaddict; 21.03.2011

arrow_upward
3
arrow_downward

Чтобы подсчитать левые дочерние узлы, вы можете сделать:

private int countLeftNodes(IntTreeNode node) {

    // no tree no left-child nodes      
    if(node == null) {
       return 0;
    }

    // left-child count of current node.
    int c = 0;

    // does the current node have a left-child ?
    if (node.left != null){
      c = 1;
    }

    // return left-child count of current node +
    // left-child count of left and right subtrees
    return c + countLeftNodes(node.left) + countLeftNodes(node.right);
}
person codaddict    schedule 21.03.2011

arrow_upward
0
arrow_downward

проще всего проверить это в родителях.

private int countLeftNodes(IntTreeNode node){

    int c = 0;
    if(node.left != null)
    {
        c++; 
        c+= countLeftNodes(node.left)
    }
    if(node.right != null)
    {
        c+= countLeftNodes(node.right);
    }

    return c;
}
person Zak    schedule 21.03.2011

arrow_upward
0
arrow_downward

Мой любимый стиль при использовании рекурсии — использовать какую-то функцию-оболочку, в которой основной метод вызывает другой, выполняющий черновую работу:

private int countLeftNodes(IntTreeNode node){
   int totalCount = reallyCountLeftNodes(IntTreeNode node, 0); 
   return totalCount;
}

private int reallyCountLeftNodes(IntTreeNode n, Int sum){
    if (n.left == NULL && n.right == NULL){  //check if we've hit rock bottom
        return sum;
    } else if (n.left == NULL) { //if the node's left is nil, go right
        reallyCountLeftNodes(n.right, sum++);   
    } else {
        reallyCountLeftNodes(n.left, sum++);  // Going as far left as possible!
    }
}

Обратите внимание, как основная функция вызывает другую. Я нахожу этот стиль более чистым и понятным. Кроме того, вторая функция имеет переменную count, которую вы можете использовать.

person Matthew    schedule 24.03.2011