二叉树中每个级别上的节点的平均值得到错误的结果

Question

我是初学者，我正在尝试使用 BFS 算法编写代码，return 用 C 语言计算二叉树中每一层节点的平均值。我没有得到正确的结果，我做错了什么？在这种情况下，我得到的结果是 4,66667，即除根节点之外的所有节点除以 6。我不明白为什么会产生这个结果。我很抱歉我的英语不好。这是代码：

#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
     int val;
     struct TreeNode *left;
     struct TreeNode *right;
};

typedef struct Node {
    struct TreeNode *node;
    struct Node *next;
} NODE;

typedef struct queue {
    struct Node *front;
    struct Node *rear;
    int length;
} QUEUE;


struct TreeNode* createTree(int value) {


  struct TreeNode *newNode = (struct TreeNode *)malloc(sizeof(struct TreeNode));
   newNode->val = value;
   newNode->left = NULL;
   newNode->right = NULL;

  return newNode;
}

struct TreeNode* insertLeft(struct TreeNode* root, int value) {

  root->left = createTree(value);
  return root->left;
}

struct TreeNode* insertRight(struct TreeNode* root ,int value) {

  root->right= createTree(value);
  return root->left;
}

QUEUE *initialize_queue() {
    QUEUE *q = (QUEUE *)malloc(sizeof(QUEUE));
    q->front = NULL;
    q->rear = NULL;
    q->length = 0;
    return q;
}

void enqueue(QUEUE *q, struct TreeNode *root) {
    NODE *new_node = (NODE *)malloc(sizeof(NODE));
    new_node -> node = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    new_node->node = root;
    new_node->node->left = root->left;
    new_node->node->right = root->right;
    new_node->node->val = root->val;
    new_node->next = NULL;

    if(q->front == NULL && q->rear == NULL) {
        q->front = q-> rear = new_node;
    } else {
        q->rear->next = new_node;
        q->rear = new_node;
    }
    q->length++;
}


struct Node *dequeue(QUEUE *q) {

    struct Node *temp = q->front;

    if(q->front == NULL) {
        return NULL;
    } else {
        q->front = q->front->next;
        if(q->front == NULL) {
            q->rear = NULL;
        }
    }
    q->length--;
    return temp;
}

int get_height(struct TreeNode *root) {
    if(root == NULL) {
        return 0;
    }

    int left = get_height(root->left);
    int right = get_height(root->right);

    if(left > right)
        return (left + 1);
    else
    return (right+1);
}
void averageOfLevels(struct TreeNode* root){


  int Size = get_height(root);
   float result = 0;

    QUEUE *q = initialize_queue();
    enqueue(q, root );

    while(q->length) {

              long int sum = 0, count = 0;

            for(int i = 0; i < Size ; i++) {

            struct Node *temp = dequeue(q);
            sum += temp->node->val;
            count++;
            if(temp->node->left != NULL) {
                 enqueue(q, temp->node->left);
            }
            else if(temp->node->right != NULL) {
                 enqueue(q, temp->node->right);
            }
        }

      result = sum*1.0 / count;

         }
   printf("%lf", result);
 }
void free_tree(struct TreeNode* root) {

    struct TreeNode* temp = root;
    if (!temp)
        return;
    free_tree(temp->left);
    free_tree(temp->right);
    if (!temp->left && !temp->right) {
        free(temp);
        return;
    }
}
int main( ) {

     struct TreeNode* root = NULL;

        root = createTree(2);
        insertLeft(root,4);
        insertRight(root,6);
        insertLeft(root->left, 8);
        insertRight(root->right, 10);

       averageOfLevels(root);

       free_tree(root);

}

Answer 1

您的代码的问题出在 averageOfLevels 函数中。如果有一个可用的左侧节点，else if 会导致右侧节点的 none 永远排队，并且您平均 2 + 4 + 8 给您 4,66666 这也恰好是总和除根节点以外的所有内容除以 6。

for 循环也不需要，它会导致程序崩溃，因为当 else if 更改为 if 时，您会得到 Size * 2 - 1 （在您的示例数据的情况下）要查看的节点总数，但是 for 循环导致队列出队 Size 次而不检查是否还有任何东西要出队导致您如果节点数不是 Size

的倍数，则尝试访问 NULL 指针

averageOfLevels 应更改为此，然后一切正常。

void averageOfLevels(struct TreeNode* root){

    float result = 0;

    QUEUE *q = initialize_queue();
    enqueue(q, root );

    long int sum = 0, count = 0;

    while(q->length) {

        struct Node *temp = dequeue(q);
        sum += temp->node->val;
        count++;

        if(temp->node->left != NULL) {
            enqueue(q, temp->node->left);
        }
        if(temp->node->right != NULL) {
            enqueue(q, temp->node->right);
        }

        result = sum*1.0 / count;

    }

    printf("%lf", result);
}

它也将对性能有很大帮助，因为您不必使用 get_height()

Answer 2

你的算法大部分是合理的，但在两个关键时刻失败了。

在将任何给定节点推入树中时，它没有正确处理任何给定节点的两个 children。有一个放错地方的 else，根本不应该放在那里。
即使您修复了 (1)，它也不会集中也不会报告 per-level 平均值的顶点。相反，它基本上找到整棵树中所有节点的单个平均值。
这不是破坏交易的问题，但您的队列效率极低，因为它不必要地复制了节点。它不需要做任何这些。它可以直接使用树中的节点指针作为 QUEUE objects.

node

此外，不需要get_height。您应该通过将树的级别合并到 QUEUE objects 保存指向树节点的指针来跟踪您正在处理的树的级别当您第一次将根推送到队列中时，初始级别存储在旁边节点指针为零 (0)。从那时起，当您弹出项目以处理它们并将它们的 children 推入队列时，那些 children 将获得 just-popped parent 级别 + 1。只有当active queue top reported level is greater than the one you are currently processing 你停止求和，计算平均值，并报告该级别。然后，将总和重置为零，增加 now-processing 级别值，然后继续。重复此过程直到队列过期，此时报告最后一个级别并且您已完成算法。

经过额外的修改，结果如下。这只是执行此操作的几种方法之一，但它相当容易理解，并且非常 space 高效：

#include <stdio.h>
#include <stdlib.h>

struct TreeNode
{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

typedef struct Node
{
    struct TreeNode const *node;
    struct Node *next;
    int level;
} NODE;

typedef struct queue
{
    struct Node *front;
    struct Node *rear;

} QUEUE;

struct TreeNode *createTree(int value)
{
    struct TreeNode *newNode = malloc(sizeof *newNode);
    newNode->val = value;
    newNode->left = newNode->right = NULL;
    return newNode;
}

struct TreeNode *insertLeft(struct TreeNode *root, int value)
{
    root->left = createTree(value);
    return root->left;
}

struct TreeNode *insertRight(struct TreeNode *root, int value)
{
    root->right = createTree(value);
    return root->left;
}

QUEUE initialize_queue()
{
    QUEUE q = { NULL, NULL };
    return q;
}

void enqueue(QUEUE *q, struct TreeNode const *root, int level)
{
    NODE *new_node = malloc(sizeof *new_node);
    new_node->node = root;
    new_node->level = level;
    new_node->next = NULL;

    if (q->front == NULL)
    {
        q->front = new_node;
    }
    else
    {
        q->rear->next = new_node;
    }
    q->rear = new_node;
}

struct Node *dequeue(QUEUE *q)
{
    if (q->front == NULL)
        return NULL;

    struct Node *temp = q->front;
    q->front = q->front->next;
    if (q->front == NULL)
    {
        q->rear = NULL;
    }

    return temp;
}


void averageOfLevels(struct TreeNode const *root)
{
    if (!root)
        return;

    long int sum = 0, count = 0;
    int level = 0;

    QUEUE q = initialize_queue();
    enqueue(&q, root, level);

    while (q.front)
    {
        struct Node *top = dequeue(&q);
        if (top->level > level)
        {
            if(count > 0)
            {
                double avg = (double)sum / count;
                printf("Level %d : %f\n", level, avg);
            }

            sum = 0;
            count = 0;
            ++level;
        }

        sum += top->node->val;
        ++count;

        if (top->node->left)
            enqueue(&q, top->node->left, level+1);

        if (top->node->right)
            enqueue(&q, top->node->right, level+1);
    }

    // report last level 
    if (count > 0)
    {
        double avg = (double)sum / count;
        printf("Level %d : %f\n", level, avg);
    }
}

void free_tree(struct TreeNode *root)
{
    struct TreeNode *temp = root;
    if (!temp)
        return;
    free_tree(temp->left);
    free_tree(temp->right);
    if (!temp->left && !temp->right)
    {
        free(temp);
        return;
    }
}

int main()
{
    struct TreeNode *root = NULL;

    root = createTree(2);
    insertLeft(root, 4);
    insertRight(root, 6);
    insertLeft(root->left, 8);
    insertRight(root->right, 10);
    averageOfLevels(root);
    free_tree(root);
}

输出

Level 0 : 2.000000
Level 1 : 5.000000
Level 2 : 9.000000

我怀疑那才是你真正想要的。如果你想从报告中排除根节点，你当然可以，但我把它留给你作为练习。同样，如何将结果累积到一个数组中并将它们返回给调用者。现在这个例子只是将它们报告给控制台。

二叉树中每个级别上的节点的平均值得到错误的结果

Average of the nodes on each level in binary tree getting the wrong result

c

breadth-first-search