检查二叉树任意深度的节点数是否等于树的高度

Question

我正在尝试执行一个函数来检查二叉树任意深度的节点数是否等于树的高度。这是代码：

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

/* STRUCTURE */

/* Structure of a binary tree */
typedef struct el {
    int info;
    struct el *left;    //Left child
    struct el *right;   //Right child
} node;

typedef node    *TREE;

/* Function that creates a binary tree */
TREE create_node(int x) {
    /* Allocates the node in the heap */
    TREE new = malloc(sizeof(node));

    new -> info = x;
    new -> left = NULL;
    new -> right = NULL;

    return new;
}

/* Function that finds the height of a binary tree */
int tree_height(TREE t) {
    /* If the tree is empty */
    if (t == NULL) {
        return 0;
    }

    /* Checks the subtrees */
    int left_height = tree_height(t -> left);
    int right_height = tree_height(t -> right);

    return 1 + (left_height > right_height ? left_height : right_height);
}

/* Auxiliary function that helps count the number of nodes at a certain depth */
int count_nodes_at_depth(TREE t, int target_depth, int current_depth) {
    /* If the tree is empty */
    if (t == NULL) {
        return 0;
    }

    /* If we're at the desired depth */
    if (current_depth == target_depth) {
        return 1;
    }

    /* Checks the subtrees */
    return count_nodes_at_depth(t -> left, target_depth, current_depth + 1) + count_nodes_at_depth(t -> right, target_depth, current_depth + 1);
}

/* Main function that helps to verify if the number of nodes at any depth is the same as the tree height */
int check_depth_nodes_equal_height(TREE t) {
    /* Calcola l'altezza dell'albero */
    int altezza = tree_height(t);

    for (int depth = 0; depth < altezza; depth++) {
        int nodes_at_depth = count_nodes_at_depth(t, depth, 0);

        /* If the number of nodes isn't the same as the tree height */
        if (nodes_at_depth != altezza) {
            return 0;
        }
    }

    /* If the condition's true for any depth */
    return 1;
}

int main() {
    /* Create the tree */
    TREE root = create_node(1);
    root -> left = create_node(2);
    root -> right = create_node(3);
    root -> left -> left = create_node(4);
    root -> left -> right = create_node(5);
    root -> right -> left = create_node(6);
    root -> right -> right = create_node(7);

    /* Find the tree height */
    int altezza = tree_height(root);
    printf("The tree height is: %d\n\n", altezza);

    /* Call the function */
    if (check_depth_nodes_equal_height(root)) {
        printf("The number of nodes at any depth is the same as the tree height\n");
    }
    else {
        printf("The number of nodes at any depth is NOT the same as the tree height\n");
    }
}

唯一给我带来麻烦的两个函数是 count_nodes_at_depth 和 check_depth_nodes_equal_height，因为无论我如何修改主函数中的二进制文件，它总是说节点数不等于树高

我尝试在 count_nodes_at_depth 中添加一个计数器来跟踪该特定深度的节点数量，但它似乎根本没有改变结果。我还尝试修改二叉树的结构，看看它是否是主函数中存在的情况所独有的，但这没有什么区别。

Answer 1

鉴于

count_nodes_at_depth

有效，让我们看看

check_depth_nodes_equal_height

:

int check_depth_nodes_equal_height(TREE t) {
    /* Calcola l'altezza dell'albero */
    int altezza = tree_height(t);

    for (int depth = 0; depth < altezza; depth++) {
        int nodes_at_depth = count_nodes_at_depth(t, depth, 0);

        /* If the number of nodes isn't the same as the tree height */
        if (nodes_at_depth != altezza) {
            return 0;
        }
    }

    /* If the condition's true for any depth */
    return 1;
}

一旦发现树的深度不等于高度，该函数的逻辑就会停止。这与函数的描述不符，该函数声称执行完全相反的操作，如果找到匹配则返回 true。

如所写，只有当所有级别都满足此条件时，您的函数才会返回 true。幸运的是，修复方法很简单。

int check_depth_nodes_equal_height(TREE t) {
    int altezza = tree_height(t);

    for (int depth = 0; depth < altezza; depth++) {
        int nodes_at_depth = count_nodes_at_depth(t, depth, 0);

        if (nodes_at_depth == altezza) {
            return 1;
        }
    }

    return 0;
}