Как подсчитать количество правильных детей в двоичном дереве?

Question

Как подсчитать количество правильных детей в двоичном дереве?

Это означает, что я хочу, чтобы дети были отмечены как справа.

Ex.

(Left | Right) 

     F(Root)  
    G | H  
T U | I J 

Правильные дети будут U, H и J.

Что бы алгоритм, чтобы найти их.

Answer 1

int count(Tree *r){ 
    if(r == NULL) return 0; 
    int num_l=0, num_r=0; 
    if(r->left != NULL) 
     num_l = count(r->left); 
    if(r->right != NULL) 
     num_r = count(r->right)+1; 
    return num_l+num_r 
} 

Answer 2

В рекурсивном подходе

Вы бы вызвать функцию для обхода вашего дерева, для текущего узла, вам необходимо: проверить, если текущий узел имеет правильный ребенок (то увеличивает счетчик), а затем вызвать функция рекурсивно для правого узла. проверьте, остался ли текущий узел дочерним, вызовите функцию рекурсивно для левого узла.

Это должно сработать.

Answer 3

Вы можете сделать это рекурсивно как:

• Если дерево не существует, нет R детей.
• Если дерево существует, то # R дети = # R дети в R-поддереве + # R детьми в L-поддереве

.

int countRChildren(Node *root) { 
     if(!root) // tree does not exist. 
      return 0; 

     // tree exists...now see if R node exits or not. 
     if(root->right) // right node exist 

      // return 1 + # of R children in L/R subtree. 
      return 1 + countRChildren(root->right) + countRChildren(root->left); 

     else // right nodes does not exist. 
      // total count of R children will come from left subtree. 
      return countRChildren(root->left); 
    } 

Answer 4

Простой обход дерева (то есть порядок по порядку), а для каждого узла - +1, если у него есть правильный ребенок.

Пример (не пытался скомпилировать и проверить его):

int countRightChildren(Node root) 
{ 
    if (root == null) return 0; 
    int selfCount = (root.getRightChild() != null) ? 1 : 0; 
    return selfCount + countRightChildren(root.getLeftChild()) + countRightChildren(root.getRightChild()); 
} 

Answer 5

Это включает, как я строить-структуру

struct Item 
{ 
    int info; 
    struct Item* right; 
    struct Item* left; 
}; 
typedef struct Item* Node; 

int countRightSons(Node tree) 
{ 
    if(!tree) 
    return 0; 
    if(tree->right != NULL) 
    return 1 + countRightSons(tree->right) + countRightSons(tree->left); 
    return countRightSons(tree->left); 
}