EC01-计算二叉树的度¶

代码实现¶

方法一：操作型（使用指针参数）¶

C
// 函数 func：计算二叉树中节点的最大度数（树的度）
// 参数：p - 二叉树的根节点指针，max_degree - 指向最大度数的指针
void func(BiTree p, int *max_degree) {
    // 递归终止条件：如果当前节点为空，则返回
    if (p != NULL) {
        int degree; // 用于存储当前节点的度数

        // 根据子节点情况计算当前节点的度数
        if (p->lchild && p->rchild) {
            // 如果左右子树都存在，度数为 2
            degree = 2;
        } else if (p->lchild || p->rchild) {
            // 如果只有左子树或只有右子树，度数为 1
            degree = 1;
        } else {
            // 如果没有子树，度数为 0
            degree = 0;
        }

        // 更新最大度数
        if (degree > *max_degree) {
            *max_degree = degree;
        }

        // 递归处理左子树
        func(p->lchild, max_degree);

        // 递归处理右子树
        func(p->rchild, max_degree);
    }
}

方法二：计算型（使用返回值）¶

C
// 函数 func：计算二叉树的度，返回树的最大度数
// 参数：p - 二叉树的根节点指针
// 返回值：树的度（节点的最大度数）
int func(BiTree p) {
    // 基础情况：空节点或叶子节点
    if (p == NULL || (!p->lchild && !p->rchild)) {
        return 0;
    }

    // 如果当前节点有两个子节点，度数为 2
    if (p->lchild && p->rchild) {
        // 递归计算左右子树的度数
        int left_degree = func(p->lchild);
        int right_degree = func(p->rchild);

        // 当前节点度数为 2，与子树度数比较取最大值
        int max_subtree_degree = (left_degree > right_degree) ? left_degree : right_degree;
        return (2 > max_subtree_degree) ? 2 : max_subtree_degree;
    }

    // 如果当前节点只有一个子节点，度数为 1
    if (p->lchild || p->rchild) {
        // 递归计算左右子树的度数
        int left_degree = func(p->lchild);
        int right_degree = func(p->rchild);

        // 当前节点度数为 1，与子树度数比较取最大值
        int max_subtree_degree = (left_degree > right_degree) ? left_degree : right_degree;
        return (max_subtree_degree > 1) ? max_subtree_degree : 1;
    }

    // 理论上不会到达这里，但为了语法完整性
    return 0;
}

两种方法对比分析¶

1. 设计思想差异¶

特征	操作型	计算型
数据传递方式	通过指针参数传递结果	通过函数返回值传递结果
状态维护	外部变量维护全局状态	递归返回值维护状态
代码风格	过程式，副作用明显	函数式，无副作用

2. 调用方式差异¶

C
// 操作型调用示例
int max_degree = 0;
func(root, &max_degree);
printf("树的度为：%d\n", max_degree);

// 计算型调用示例
int tree_degree = func(root);
printf("树的度为：%d\n", tree_degree);

代码逻辑解析¶

操作型方法分析¶

遍历策略：前序遍历（根-左-右）
度数计算：
0度：无子节点（叶子节点）
1度：只有一个子节点
2度：有两个子节点
最大值维护：通过指针参数实时更新全局最大值

计算型方法分析¶

递归思路：
当前节点的度数
左子树的最大度数
右子树的最大度数
三者取最大值
边界处理：
空节点：度数为 0
叶子节点：度数为 0
返回策略：每层递归返回该子树的最大度数

时间复杂度分析¶

两种方法的时间复杂度均为 O(n)¶

节点访问次数：每种方法都需要访问二叉树中的每个节点 exactly 一次
每次操作复杂度：度数计算和比较操作都是 O(1)
递归调用开销：每次递归调用的额外开销为 O(1)

空间复杂度分析¶

操作型方法：O(n)¶

递归栈空间：最坏情况下（退化为链表）递归深度为 O(n)
额外变量空间：只使用常量级别的局部变量 O(1)
总体空间复杂度：O(n)

计算型方法：O(n)¶

递归栈空间：同样最坏情况下递归深度为 O(n)
局部变量空间：每层递归使用常量级别的变量 O(1)
总体空间复杂度：O(n)

较难理解部分的说明¶

1. 计算型方法的逻辑处理¶

C
// 关键逻辑解释
if (p->lchild && p->rchild)
    return 2;  // 当前节点度数为 2，但还需要考虑子树
// 实际应该是：
int left_degree = func(p->lchild);
int right_degree = func(p->rchild);
int max_subtree_degree = max(left_degree, right_degree);
return max(2, max_subtree_degree);

2. 图解说明¶

假设二叉树结构如下：

Text Only
1 2 3 4 5 6 7	`A // 度数 = 2 / \ B C // B度数 = 1, C度数 = 2 / / \ D E F // D度数 = 0, E度数 = 1, F度数 = 0 / G // G度数 = 0`

操作型执行过程：

Text Only

1
2
3

访问顺序：A(2) → B(1) → D(0) → B(1) → A(2) → C(2) → E(1) → G(0) → E(1) → C(2) → F(1) → G(0) → F(1) → C(2) → A(2)
最大值变化：0→2→2→2→2→2→2→2→2→2→2→2→2→2→2
最终结果：2

计算型执行过程：

Text Only

func(G) = 0 (叶子)
func(F) = max(1, max(func(NULL), func(G))) = max(1, 0) = 1
func(E) = max(1, max(func(NULL), func(G))) = max(1, 0) = 1
func(D) = 0 (叶子)
func(B) = max(1, max(func(D), func(NULL))) = max(1, 0) = 1
func(C) = max(2, max(func(E), func(F))) = max(2, 1) = 2
func(A) = max(2, max(func(B), func(C))) = max(2, 2) = 2

延伸知识点¶

1. 完整测试示例¶

C
// 二叉树节点定义
typedef struct BiTreeNode {
    int data;
    struct BiTreeNode *lchild, *rchild;
} BiTreeNode, *BiTree;

// 构建测试树
BiTree createTestTree() {
    // 构建上面示例的树结构
    BiTree root = (BiTree)malloc(sizeof(BiTreeNode));
    root->data = 'A';
    // ... 构建完整树结构
    return root;
}

2. 优化版本¶

C
// 早期终止优化
int funcOptimized(BiTree p) {
    if (p == NULL) return 0;

    // 如果已经找到度数为2的节点，可以优化
    int current_degree = 0;
    if (p->lchild && p->rchild) {
        current_degree = 2;
    } else if (p->lchild || p->rchild) {
        current_degree = 1;
    }

    // 如果当前就是最大值，且不需要递归检查子树
    if (current_degree == 2) {
        return 2; // 但为了完整性，还是需要检查子树
    }

    int left_max = funcOptimized(p->lchild);
    int right_max = funcOptimized(p->rchild);

    return max(current_degree, max(left_max, right_max));
}

3. 非递归实现¶

C
// 使用栈的迭代实现
int funcIterative(BiTree root) {
    if (root == NULL) return 0;

    int max_degree = 0;
    Stack* stack = createStack();
    push(stack, root);

    while (!isEmpty(stack)) {
        BiTree node = pop(stack);
        int degree = 0;

        if (node->lchild && node->rchild) {
            degree = 2;
        } else if (node->lchild || node->rchild) {
            degree = 1;
        }

        if (degree > max_degree) {
            max_degree = degree;
        }

        if (node->rchild) push(stack, node->rchild);
        if (node->lchild) push(stack, node->lchild);
    }

    return max_degree;
}

4. 广义树的度计算¶

C
// 多叉树的度计算
typedef struct MultiTreeNode {
    int data;
    int child_count;
    struct MultiTreeNode** children;
} MultiTreeNode;

int getMultiTreeDegree(MultiTreeNode* root) {
    if (root == NULL) return 0;

    // 当前节点的度数
    int current_degree = root->child_count;

    // 递归计算所有子树的最大度数
    int max_child_degree = 0;
    for (int i = 0; i < root->child_count; i++) {
        int child_degree = getMultiTreeDegree(root->children[i]);
        if (child_degree > max_child_degree) {
            max_child_degree = child_degree;
        }
    }

    return (current_degree > max_child_degree) ? current_degree : max_child_degree;
}

5. 实际应用场景¶

网络拓扑分析：路由器连接度分析
社交网络：用户好友关系复杂度
文件系统：目录分支复杂度
组织架构：管理层级宽度分析

这两种方法体现了递归算法设计中的两种经典模式：状态传递和结果返回，是理解递归思维的重要案例。