用C语言计算二叉树深度和结点个数的方法判断满二叉树

在C语言中，计算二叉树的深度和节点个数涉及到递归算法，对于满二叉树特别需要注意其特性。满二叉树的特点是每一层都被完全填充，除了最后一层外，所有节点都尽可能地向左靠拢。

1. 计算二叉树深度：
- 使用递归方法可以轻松实现。对于一棵二叉树，如果根节点存在，则深度等于根节点所在的层数加一；如果根节点为空，深度为0。递归函数的基本形式如下：

     int tree_depth(struct TreeNode* root) {
         if (root == NULL) return 0;
         else return 1 + tree_depth(root->left);
     }

2. 计算二叉树节点个数：
- 对于任意非空节点，它要么有左孩子，要么有右孩子，所以总节点数 = 左孩子的节点数 + 右孩子的节点数 + 1（根节点）。同样使用递归：

     int count_nodes(struct TreeNode* root) {
         if (root == NULL) return 0;
         else return 1 + count_nodes(root->left) + count_nodes(root->right);
     }

3. 判断是否为满二叉树：
- 验证每个节点都有两个子节点（除非是叶子节点），并且所有内部节点都在同一层。可以遍历并记录每层的最大节点数，然后检查最后是否有剩余的节点位置未填满。

   bool is_full_binary_tree(struct TreeNode* root) {
       queue<int> q; // 使用队列辅助计算层次
       int last_level = -1;
       int nodes_count = 0;

       q.push(root);
       while (!q.empty()) {
           int level_size = q.size();
           if (level_size > last_level + 1) return false; // 检查层间差距
           last_level = level_size;
           for (int i = 0; i < level_size; ++i) {
               struct TreeNode* node = q.front(); q.pop();
               if (node->left && node->right) nodes_count += 2;
               else nodes_count++;
               if (node->left) q.push(node->left);
               if (node->right) q.push(node->right);
           }
       }
       return nodes_count == (1 << (last_level + 1)) - 1; // 根据满二叉树节点公式验证
   }