【c++】计算树的深度和节点数

在C语言中，计算给定树的层数（深度）和节点总数通常需要使用递归方法。首先，我们需要定义树的节点结构。这里假设我们处理的是一棵二叉树，每个节点有两个子节点（左子节点和右子节点）。

下面是一个简单的二叉树节点的结构定义以及计算树的层数（深度）和节点总数的函数实现：

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

// 定义二叉树节点结构体
typedef struct TreeNode {
    int value; // 节点存储的值，根据实际情况可以改变类型
    struct TreeNode *left; // 指向左子节点的指针
    struct TreeNode *right; // 指向右子节点的指针
} TreeNode;

// 函数声明
int maxDepth(TreeNode* root);
int countNodes(TreeNode* root);

// 计算树的最大深度（层数）
int maxDepth(TreeNode* root) {
    if (root == NULL) {
        return 0; // 空树的深度为0
    }
    int leftDepth = maxDepth(root->left); // 计算左子树的深度
    int rightDepth = maxDepth(root->right); // 计算右子树的深度
    return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1; // 当前树的深度为较大的子树深度加1
}

// 计算树的节点总数
int countNodes(TreeNode* root) {
    if (root == NULL) {
        return 0; // 空树没有节点
    }
    return countNodes(root->left) + countNodes(root->right) + 1; // 总数等于左子树节点数加右子树节点数再加1（当前节点）
}

// 创建新节点
TreeNode* createNode(int value) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    if (!newNode) {
        return NULL;
    }
    newNode->value = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 函数声明
void freeTree(TreeNode* root);

// 释放树的内存
void freeTree(TreeNode* root) {
    if (root == NULL) {
        return; // 空指针不需要处理
    }
    freeTree(root->left); // 递归释放左子树
    freeTree(root->right); // 递归释放右子树
    free(root); // 释放当前节点
}

// 主函数示例
int main() {
    // 创建示例树
    //         1
    //       /   \
    //      2     3
    //     / \   /
    //    4   5 6
    TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->left = createNode(6);

    printf("Tree Depth: %d\n", maxDepth(root));
    printf("Total Nodes: %d\n", countNodes(root));

    // 释放内存
    freeTree(root);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

这段代码首先定义了二叉树节点的结构体TreeNode，然后实现了两个关键函数：maxDepth用于计算树的最大深度（层数），而countNodes用于计算树的节点总数。这两个函数都采用了递归的方式来进行计算。

要将计算树深度和总节点数的功能合并到一个函数中，我们可以定义一个辅助结构来同时存储这两个值
首先，定义一个结构体来存储树的深度和节点总数：

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

typedef struct TreeNode {
    int value;
    struct TreeNode *left, *right;
} TreeNode;

typedef struct TreeInfo {
    int depth;
    int numNodes;
} TreeInfo;
1
2
3
4
5
6
7
8
9
10
11
12

然后，实现一个递归函数来计算深度和节点总数：

TreeInfo calculateTreeInfo(TreeNode* root) {
    TreeInfo info = {0, 0}; // 初始化深度和节点数为0
    if (root == NULL) {
        return info; // 如果当前节点为空，返回深度和节点数都为0的结构
    }

    // 递归计算左右子树的信息
    TreeInfo leftInfo = calculateTreeInfo(root->left);
    TreeInfo rightInfo = calculateTreeInfo(root->right);

    // 当前节点的深度是左右子树深度的最大值加1
    info.depth = (leftInfo.depth > rightInfo.depth ? leftInfo.depth : rightInfo.depth) + 1;
    // 节点总数是左右子树节点数之和加上当前节点（1）
    info.numNodes = leftInfo.numNodes + rightInfo.numNodes + 1;

    return info; // 返回包含当前节点信息的结构
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17