关于树数据结构的问题，打印每个级别的总和（级别总和=兄弟数据的总和）？

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

然后在你的递归函数中，每当你进入递归时，你可以将 level 参数作为 level + 1 传递，而不是像这样执行 level++ 和 level-- =D ：

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

注意这不仅是干净一点，它还有其他优点。例如，这种方法可以在多线程环境中使用，而另一种则不能，因为它依赖于静态变量。

2 -- 您可能希望使用 typedef 和改变结构的函数进一步封装您的树。如果您想了解更多这方面的信息，请直接询问。不过，这对于您的锻炼来说根本不是必要的。

3 -- 记住函数名称通常以小写字母开头。

这就是我要说的一切，你的代码非常干净！恭喜！

Answer 2

您的代码似乎做得正确。在英语中，您的逻辑是这样的 -

对于您下降到树中的每个级别（左侧和右侧），跟踪您的深度并将data添加到全局总和跟踪变量a.

除非你对你的结构做出重大改变 - 这是唯一的方法（我能想到的）

Answer 3

我会避免使用 level 作为全局变量。在这种特殊情况下，这并不重要，因为没有线程或类似的复杂情况。但养成避免使用全局变量的习惯是有好处的。

除非您必须使用全局变量并且需要小心，否则总是优先使用局部变量而不是全局变量。

我将在方法中添加 level 作为参数，而不是执行 level++ 和 level--，而是简单地将 level+1 传递给方法调用。

Answer 4

我认为你的代码很好。

作为替代方案，您可以使用 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;
                }

            }
    }