Вопрос о древовидной структуре данных: выведите сумму каждого уровня (сумма уровня = сумма данных родных элементов)?

Question

Ниже я написал кусок кода, чтобы ответить на этот вопрос.Не могли бы вы сказать мне 1) если вы обнаружите какие-либо дефекты в моем коде 2) любое другое лучшее решение ?

Вопрос: Вопрос поДревовидная структура данных, выводить сумму каждого уровня (сумма уровня = сумма данных братьев и сестер)?

struct tree{
             int data;
             struct *left;
             struct *right;
 };

Прототип API равен void EachLevelSum (struct tree * root);

Мой ответ

void EachLevelSum(struct tree *root )
{
     static int level=0;
     static int a[100] = {0}; // I am assuming , at MAX 100 levels in tree

     if( root == NULL )
     {
           return;
     }
     else
     {
           a[level += root->data;

           level++;
           EachLevelSum(root->left);
           level--;      

           level++;
           EachLevelSum(root->right);
           level--;      

           if( level == 0 )
           {
               int i;
               for( i=0; i<100 && a[i]!=0 ; i++)
               {
                   printf("\n level: %d sum = %d", i,  a[i] );
               }

           }
     }

}

Answer 1

Я думаю, это очень хорошо! Однако я могу сказать одну или две вещи, которые могут помочь вам улучшить это.

1 - Использование статических переменных. Это не запрещено, но вам следует избегать этого. Теперь, как бы вы, учитывая, что ваше решение является рекурсивным по природе, и вам нужны общие данные между вызовами?

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

void eachLevelSum(struct tree*);
static void eachLevelSumRecursive(struct tree*, int level, int* results);

А потом, что-то вроде:

void eachLevelSum(struct tree* t) {
    int results[100];
    eachLevelSumRecursive(t, 0, results);

    return;
}

Тогда в вашей рекурсивной функции, когда бы вы ни входили в рекурсию, вы можете передать параметр уровня как уровень + 1 вместо того, чтобы делать уровень ++ и уровень-- = D, как это:

eachLevelSumRecursive(t->left, level + 1, results);
eachLevelSumRecursive(t->right, level + 1, results);

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

2 - Вы можете захотеть дополнительно инкапсулировать свое дерево, используя typedefs и функции, которые изменяют структуру. Если вы хотите больше информации об этом, спросите. Это совсем не обязательно для вашей тренировки.

3 - Помните, что имена функций обычно начинаются со строчных букв.

И это все, что я должен сказать, ваш код довольно чистый! Поздравляем!

Answer 2

Я думаю, твой код хорош.

В качестве альтернативы вы можете использовать поиск BFS: http://en.wikipedia.org/wiki/Breadth-first_search. Вот пример кода C #

    class Tree
    {
        public int data;
        public Tree Left;
        public Tree Right;


            static int[] levels = new int[100];

            static void EachLevelSum(Tree root)
            {
                // keeps track of each tree node's level
                Dictionary<Tree, int> treeLevels = new Dictionary<Tree,int>();
                treeLevels.Add(root, 0);

                // Do a BFS search and update the level of each node
                Queue<Tree> trees = new Queue<Tree>();
                trees.Enqueue(root);

                while (trees.Count != 0)
                {
                    Tree node = trees.Dequeue();
                    int level = treeLevels[node];
                    if (node.Left != null)
                    {
                        treeLevels.Add(node.Left, level + 1);
                        trees.Enqueue(node.Left);
                    }
                    if (node.Right != null)
                    {
                        treeLevels.Add(node.Right, level + 1);
                        trees.Enqueue(node.Right);
                    }
                }
                foreach (Tree node in treeLevels.Keys)
                {
                    int level = treeLevels[node];
                    levels[level] += node.data;
                }

            }
    }

Answer 3

Ваш код, кажется, делает это правильно.На английском ваша логика гласит:

Для каждого уровня, который вы спускаете в дерево (как левого, так и правого), отслеживайте свою глубину и добавляйте data к глобальной переменной отслеживания суммы a.

Если вы не внесете существенные изменения в свою структуру - это единственный способ сделать это (о чем я могу думать)

Answer 4

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

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

Я бы добавил уровень в качестве аргумента в методе, и вместо того, чтобы делать уровень ++ и уровень--, я просто передам уровень + 1 вызову метода.