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

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

Сделайте простой обход по дереву (т.е. по порядку размещения, по порядку), и для каждого узла сделайте +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 3

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

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

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

Answer 4

Это включает в себя, как я строю структуру

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

Answer 5

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

• Если дерево не существует, нет R детей.
• Если дерево существует, то # R children = # 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);
    }