C语言实现计算树的深度的方法

C语言实现计算树的深度的方法

计算树的深度是树的常见操作之一，它是指从根节点到叶子节点的最长路径上的节点数。本文将介绍如何使用C语言实现计算树的深度的方法。

1. 递归法

递归法是树的常见遍历方法，计算树的深度也可以使用递归法来实现。递归法的思想是将树的每个子树的深度计算出来，然后取最大值加1，即为整棵树的深度。

具体实现方法如下：

int maxDepth(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);
    return max(leftDepth, rightDepth) + 1;
}

解释一下代码：

1. 如果给定的根节点指针为NULL，则返回0，因为空树的深度为0；
2. 否则，递归计算左子树和右子树的深度，得到leftDepth和rightDepth；
3. 将leftDepth和rightDepth中的较大值加1，即为整棵树的深度。

2. 迭代法

除了递归法，我们还可以使用迭代法来计算树的深度。迭代法的基本思路是用队列来保存每一层的节点，并对每一层的节点进行遍历。每遍历一层，深度加1。遍历完最后一层，即为整棵树的深度。

具体实现方法如下：

int maxDepth(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    int depth = 0;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        depth++;
        int len = q.size();
        for (int i = 0; i < len; i++) {
            TreeNode* node = q.front();
            q.pop();
            if (node->left != NULL) {
                q.push(node->left);
            }
            if(node->right != NULL) {
                q.push(node->right);
            }
        }
    }
    return depth;
}

解释一下代码：

1. 如果给定的根节点指针为NULL，则返回0，因为空树的深度为0；
2. 否则，定义一个整数变量depth，用来保存树的深度；
3. 定义一个队列q，用来保存每一层的节点；
4. 将根节点加入队列中，并将depth加1；
5. 当队列不为空时，循环计算每一层的节点，并遍历它们的子节点；
6. 当遍历完当前层的所有节点后，将depth加1，指向下一层；
7. 最后返回depth，即为整棵树的深度。

3. 示例说明

示例1

以下是一棵二叉树：

    3
   / \
  9  20
    /  \
   15   7

使用递归法计算树的深度：

int maxDepth(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);
    return max(leftDepth, rightDepth) + 1;
}

输出结果：

3

使用迭代法计算树的深度：

int maxDepth(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    int depth = 0;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        depth++;
        int len = q.size();
        for (int i = 0; i < len; i++) {
            TreeNode* node = q.front();
            q.pop();
            if (node->left != NULL) {
                q.push(node->left);
            }
            if(node->right != NULL) {
                q.push(node->right);
            }
        }
    }
    return depth;
}

输出结果：

3

示例2

以下是一棵普通树：

       1
     / | \
    2  3  4
   / \
  5   6

使用递归法计算树的深度：

int maxDepth(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    int maxDep = 0;
    for (TreeNode* child : root->children) {
        int dep = maxDepth(child);
        if (dep > maxDep) {
            maxDep = dep;
        }
    }
    return maxDep + 1;
}

输出结果：

3

使用迭代法计算树的深度：

int maxDepth(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    int depth = 0;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        depth++;
        int len = q.size();
        for (int i = 0; i < len; i++) {
            TreeNode* node = q.front();
            q.pop();
            for (TreeNode* child : node->children) {
                if (child != NULL) {
                    q.push(child);
                }
            }
        }
    }
    return depth;
}

输出结果：

3

以上就是C语言实现计算树的深度的方法的详细讲解！