计算二叉树的带权路径长度¶

代码实现¶

层序遍历¶

C
// 方法一：层次遍历（广度优先搜索）计算二叉树的带权路径长度
int func(BiTree bt) {
    BiTree que[maxsize];           // 队列，用于层次遍历
    int front = 0, rear = 0;       // 队列的头指针和尾指针
    int wpl = 0;                   // 带权路径长度
    int last = 1;                  // 当前层的最后一个节点在队列中的位置
    int level = 0;                 // 当前层数（根节点在第0层）

    // 如果二叉树不为空
    if (bt != NULL) {
        que[++rear] = bt;          // 将根节点入队

        // 层次遍历循环
        while (front != rear) {
            bt = que[++front];     // 出队一个节点

            // 如果是叶子节点，计算其对WPL的贡献
            if (!bt->lchild && !bt->rchild) {
                wpl += level * (bt->data);  // WPL += 深度 × 权值
            }

            // 将左右子节点入队
            if (bt->lchild != NULL) {
                que[++rear] = bt->lchild;
            }
            if (bt->rchild != NULL) {
                que[++rear] = bt->rchild;
            }

            // 如果当前层处理完毕，进入下一层
            if (front == last) {
                level++;           // 层数加1
                last = rear;       // 更新下一层的最后一个节点位置
            }
        }
    }

    return wpl;  // 返回带权路径长度
}

递归遍历¶

C
// 方法二：递归遍历计算二叉树的带权路径长度
void func(BiTree bt, int *deep, int *wpl) {
    // 递归终止条件：如果当前节点为空，则返回
    if (bt != NULL) {
        ++(*deep);  // 进入当前节点，深度加1

        // 如果是叶子节点，计算其对WPL的贡献
        if (!bt->lchild && !bt->rchild) {
            *wpl += (bt->data) * (*deep - 1);  // WPL += 权值 × 深度
        }

        // 递归处理左右子树
        func(bt->lchild, deep, wpl);
        func(bt->rchild, deep, wpl);

        --(*deep);  // 离开当前节点，深度减1（回溯）
    }
}

算法原理详解¶

1. 带权路径长度（WPL）定义¶

路径长度：从树根到某个节点的路径上的分支数
带权路径长度：节点的权值 × 该节点的路径长度
树的带权路径长度：所有叶子节点的带权路径长度之和

在二叉树中，带权路径长度（WPL）是指：

所有叶子节点的 权值 × 到根节点的路径长度 之和。

设一棵二叉树有 \(n\) 个叶子节点，每个叶子节点的权值为 \(w_i\)，从根到该叶子的路径长度（边数）为 \(l_i\)，则：

\[ \text{WPL} = \sum_{i=1}^{n} w_i \times l_i \]

\(w_i\)：第 \(i\) 个叶子节点的权值（如字符出现频率）
\(l_i\)：从根到该叶子的路径长度（即经过的边数）

2. 方法一：层次遍历思想¶

使用广度优先搜索（BFS）： - 通过队列实现层次遍历 - 记录每一层的节点范围 - 对每个叶子节点计算其深度 × 权值

3. 方法二：递归遍历思想¶

使用深度优先搜索（DFS）： - 通过递归实现前序遍历 - 动态维护当前节点的深度 - 对每个叶子节点计算其权值 × 深度

时间复杂度分析¶

1. 方法一（层次遍历）¶

需要访问每个节点 exactly 一次
每次访问的操作都是常数时间
时间复杂度：O(n)

2. 方法二（递归遍历）¶

同样需要访问每个节点 exactly 一次
每次访问的操作都是常数时间
时间复杂度：O(n)

空间复杂度分析¶

1. 方法一（层次遍历）¶

队列空间：最坏情况下队列中存储所有叶子节点
完全二叉树：O(n/2) ≈ O(n)
最坏情况：O(n)
其他变量：O(1)
总体空间复杂度：O(n)

2. 方法二（递归遍历）¶

递归调用栈：递归深度等于树的高度
平衡树：O(log n)
退化树：O(n)
参数传递：O(1)
总体空间复杂度：O(h)，其中 h 是树的高度

较难理解部分的说明¶

1. 层次遍历中的层控制机制¶

C
// 关键变量解释
int last = 1;    // 当前层的最后一个节点在队列中的位置
int level = 0;   // 当前层数

// 层切换逻辑
if (front == last) {  // 当前层处理完毕
    level++;          // 进入下一层
    last = rear;      // 下一层的最后一个节点位置
}

图解说明：

Text Only

        A(1)         // 第0层，last=1
       / \
      B(2) C(3)      // 第1层，last=3
     / \
    D(4) E(5)        // 第2层，last=5

处理过程：
front=0,rear=1,last=1,level=0 → 处理A
front=1,rear=3,last=1,level=0 → 处理B,C
front=1,rear=3,last=1,level=0 → front==last，level=1,last=3
front=3,rear=5,last=3,level=1 → 处理D,E
front=3,rear=5,last=3,level=1 → front==last，level=2,last=5

2. 递归方法中的深度管理¶

C
void func(BiTree bt, int *deep, int *wpl) {
    if (bt != NULL) {
        ++(*deep);           // 进入节点，深度+1
        // ... 处理节点
        func(bt->lchild, deep, wpl);   // 递归左子树
        func(bt->rchild, deep, wpl);   // 递归右子树
        --(*deep);           // 离开节点，深度-1（回溯）
    }
}

执行过程示例：

Text Only

        A(3)
       / \
      B(2) C(1)
     /
    D(4)

调用序列：
func(A, &deep=0, &wpl=0)
  → ++deep=1
  → func(B, &deep=1, &wpl=0)
    → ++deep=2
    → func(D, &deep=2, &wpl=0)
      → ++deep=3
      → D是叶子：wpl += 4×(3-1) = 8
      → --deep=2
    → func(NULL, &deep=2, &wpl=8) → 返回
    → --deep=1
  → func(C, &deep=1, &wpl=8)
    → ++deep=2
    → C是叶子：wpl += 1×(2-1) = 9
    → --deep=1
  → --deep=0
最终WPL = 9

完整使用示例¶

C
// 使用方法一
int wpl1 = func(root);

// 使用方法二
int wpl2 = 0;
int depth = 0;
func(root, &depth, &wpl2);

// 两种方法结果应该相同
assert(wpl1 == wpl2);

延伸知识点¶

1. 哈夫曼树与WPL¶

C
// 哈夫曼树的构建就是为了最小化WPL
typedef struct {
    int weight;
    int parent, lchild, rchild;
} HuffmanNode;

// 构建哈夫曼树使得WPL最小
HuffmanTree createHuffmanTree(int weights[], int n) {
    // 实现哈夫曼编码算法
    // 最终树的WPL就是最小的带权路径长度
}

2. 改进版本 - 返回详细信息¶

C
typedef struct {
    int totalWPL;
    int leafCount;
    int maxDepth;
    int minDepth;
} WPLInfo;

WPLInfo calculateWPLDetailed(BiTree root) {
    WPLInfo info = {0, 0, 0, INT_MAX};
    calculateWPLHelper(root, 0, &info);
    return info;
}

void calculateWPLHelper(BiTree node, int depth, WPLInfo* info) {
    if (node == NULL) return;

    if (!node->lchild && !node->rchild) {
        // 叶子节点
        info->totalWPL += node->data * depth;
        info->leafCount++;
        info->maxDepth = max(info->maxDepth, depth);
        info->minDepth = min(info->minDepth, depth);
    } else {
        // 内部节点
        calculateWPLHelper(node->lchild, depth + 1, info);
        calculateWPLHelper(node->rchild, depth + 1, info);
    }
}

3. 非递归版本（使用栈）¶

C
int calculateWPLIterative(BiTree root) {
    if (root == NULL) return 0;

    typedef struct {
        BiTree node;
        int depth;
    } StackNode;

    StackNode stack[maxsize];
    int top = -1;
    int wpl = 0;

    stack[++top] = (StackNode){root, 0};

    while (top >= 0) {
        StackNode current = stack[top--];

        if (!current.node->lchild && !current.node->rchild) {
            wpl += current.node->data * current.depth;
        }

        if (current.node->rchild) {
            stack[++top] = (StackNode){current.node->rchild, current.depth + 1};
        }
        if (current.node->lchild) {
            stack[++top] = (StackNode){current.node->lchild, current.depth + 1};
        }
    }

    return wpl;
}

4. 应用场景¶

数据压缩：哈夫曼编码中WPL代表平均编码长度
决策树评估：评估决策树的平均查找成本
文件系统优化：优化目录结构的访问效率
网络路由：计算网络中数据传输的平均路径成本

5. 性能对比¶

方法	时间复杂度	空间复杂度	优点	缺点
层次遍历	O(n)	O(n)	直观易懂，便于调试	空间开销大
递归遍历	O(n)	O(h)	空间效率高	可能栈溢出

这两种方法都体现了树遍历的经典思想，层次遍历适合需要按层处理的场景，递归遍历适合深度优先的场景。