当前位置： 首页 > news >正文

华为OD机试 - 生成哈夫曼树（Python/JS/C/C++ 2024 D卷 100分）

news 2024/10/22 9:43:01

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新。

一、题目描述

给定长度为 n 的无序的数字数组，每个数字代表二叉树的叶子节点的权值，数字数组的值均大于等于 1 。

请完成一个函数，根据输入的数字数组，生成哈夫曼树，并将哈夫曼树按照中序遍历输出。

为了保证输出的二叉树中序遍历结果统一，增加以下限制:

在树节点中，左节点权值小于等于右节点权值，根节点权值为左右节点权值之和。
当左右节点权值相同时，左子树高度高度小于等于右子树。
注意: 所有用例保证有效，并能生成哈夫曼树提醒:哈夫曼树又称最优二叉树，是一种带权路径长度最短的一叉树。

所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为 0 层，叶结点到根结点的路径长度为叶结点的层数)。

二、输入描述

例如：由叶子节点 5 15 40 30 10 生成的最优二叉树如下图所示，该树的最短带权路径长度为 40∗1+30∗2+15∗3+5∗4+10∗4=205。

在这里插入图片描述

三、输出描述

输出一个哈夫曼的中序遍历数组，数值间以空格分隔。

四、测试用例

1、输入

5
5 15 40 30 10

2、输出

40 100 30 60 15 30 5 15 10

3、说明

根据输入，生成哈夫曼树，按照中序遍历返回。所有节点中，左节点权值小于等于右节点权值之和。当左右节点权值相同时左子树高度小于右子树。

五、解题思路

1、构建哈夫曼树

  1. 定义节点类：首先，我们需要一个节点类HuffmanNode，用于表示哈夫曼树的节点，其中包含权值、左子节点、右子节点。
  2. 初始化节点列表：使用给定的数组创建节点列表，每个数值对应一个节点。
  3. 构建哈夫曼树：
    • 排序：按权值将节点列表排序。
    • 合并节点：每次取出最小的两个节点，合成一个新的节点，其权值是这两个节点权值的和，左子节点是两者中较小的，右子节点是较大的（若相同，则根据高度决定，这里可以用深度属性比较）。
    • 更新列表：将新节点添加到列表中，并重新排序。
    • 重复：继续合并，直到列表中只剩下一个节点，这个节点是哈夫曼树的根节点。

2、中序遍历

对构建好的哈夫曼树进行中序遍历（左-根-右），并收集遍历到的节点的权值。

六、Python算法源码

import heapqclass HuffmanNode:def __init__(self, weight):self.weight = weight  # 节点权值self.height = 1       # 节点高度，叶子节点高度为1self.left = None      # 左子节点self.right = None     # 右子节点def __lt__(self, other):# 定义小于运算符，用于优先队列比较if self.weight != other.weight:return self.weight < other.weightelse:return self.height < other.heightdef build_huffman_tree(weights):# 创建最小堆heap = []for weight in weights:heapq.heappush(heap, HuffmanNode(weight))# 循环合并节点直到堆中只剩一个节点while len(heap) > 1:left = heapq.heappop(heap)   # 取出权值最小的节点right = heapq.heappop(heap)  # 取出第二小的节点parent = HuffmanNode(left.weight + right.weight)  # 创建父节点# 确保左子节点权值小于等于右子节点权值if left.weight < right.weight:parent.left = leftparent.right = rightelif left.weight > right.weight:parent.left = rightparent.right = leftelse:# 权值相等，比较高度if left.height <= right.height:parent.left = leftparent.right = rightelse:parent.left = rightparent.right = left# 更新父节点的高度parent.height = max(left.height, right.height) + 1heapq.heappush(heap, parent)  # 将父节点加入堆中return heap[0] if heap else None  # 返回根节点def inorder_traversal(node, result):if node:inorder_traversal(node.left, result)    # 遍历左子树result.append(node.weight)              # 访问当前节点inorder_traversal(node.right, result)   # 遍历右子树def main():import sysinput = sys.stdin.readdata = input().split()n = int(data[0])weights = list(map(int, data[1:n+1]))root = build_huffman_tree(weights)inorder_result = []inorder_traversal(root, inorder_result)print(' '.join(map(str, inorder_result)))if __name__ == "__main__":main()

七、JavaScript算法源码

class HuffmanNode {constructor(weight) {this.weight = weight; // 节点权值this.height = 1;      // 节点高度，叶子节点高度为1this.left = null;     // 左子节点this.right = null;    // 右子节点}
}// 定义最小堆
class MinHeap {constructor() {this.heap = [];}// 插入节点push(node) {this.heap.push(node);this.bubbleUp(this.heap.length - 1);}// 取出最小节点pop() {if (this.heap.length === 0) return null;const min = this.heap[0];const end = this.heap.pop();if (this.heap.length > 0) {this.heap[0] = end;this.bubbleDown(0);}return min;}size() {return this.heap.length;}// 上浮操作bubbleUp(index) {while (index > 0) {const parentIdx = Math.floor((index - 1) / 2);if (this.compare(this.heap[index], this.heap[parentIdx]) < 0) {[this.heap[index], this.heap[parentIdx]] = [this.heap[parentIdx], this.heap[index]];index = parentIdx;} else {break;}}}// 下沉操作bubbleDown(index) {const length = this.heap.length;while (true) {let left = 2 * index + 1;let right = 2 * index + 2;let smallest = index;if (left < length && this.compare(this.heap[left], this.heap[smallest]) < 0) {smallest = left;}if (right < length && this.compare(this.heap[right], this.heap[smallest]) < 0) {smallest = right;}if (smallest !== index) {[this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];index = smallest;} else {break;}}}// 比较函数，首先按权值，权值相同按高度compare(a, b) {if (a.weight !== b.weight) {return a.weight - b.weight;} else {return a.height - b.height;}}
}function buildHuffmanTree(weights) {const heap = new MinHeap();// 将所有叶子节点加入堆中for (let weight of weights) {heap.push(new HuffmanNode(weight));}// 循环合并节点直到堆中只剩一个节点while (heap.size() > 1) {const left = heap.pop();const right = heap.pop();const parent = new HuffmanNode(left.weight + right.weight);// 确保左子节点权值小于等于右子节点权值if (left.weight < right.weight) {parent.left = left;parent.right = right;} else if (left.weight > right.weight) {parent.left = right;parent.right = left;} else {// 权值相等，比较高度if (left.height <= right.height) {parent.left = left;parent.right = right;} else {parent.left = right;parent.right = left;}}// 更新父节点的高度parent.height = Math.max(left.height, right.height) + 1;heap.push(parent);}return heap.pop();
}function inorderTraversal(node, result) {if (node !== null) {inorderTraversal(node.left, result);    // 遍历左子树result.push(node.weight);               // 访问当前节点inorderTraversal(node.right, result);   // 遍历右子树}
}function main() {const fs = require('fs');const input = fs.readFileSync('/dev/stdin', 'utf8').trim().split(/\s+/);const n = parseInt(input[0]);const weights = input.slice(1, n + 1).map(Number);const root = buildHuffmanTree(weights);const inorderResult = [];inorderTraversal(root, inorderResult);console.log(inorderResult.join(' '));
}main();

八、C算法源码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 定义哈夫曼树节点结构
typedef struct HuffmanNode {int weight;               // 节点权值int height;               // 节点高度，叶子节点高度为1struct HuffmanNode* left; // 左子节点struct HuffmanNode* right;// 右子节点
} HuffmanNode;// 定义最小堆结构
typedef struct MinHeap {HuffmanNode** array; // 节点数组int size;            // 当前堆的大小int capacity;        // 堆的容量
} MinHeap;// 创建新节点
HuffmanNode* createNode(int weight) {HuffmanNode* node = (HuffmanNode*)malloc(sizeof(HuffmanNode));node->weight = weight;node->height = 1;node->left = NULL;node->right = NULL;return node;
}// 创建最小堆
MinHeap* createMinHeap(int capacity) {MinHeap* heap = (MinHeap*)malloc(sizeof(MinHeap));heap->size = 0;heap->capacity = capacity;heap->array = (HuffmanNode**)malloc(capacity * sizeof(HuffmanNode*));return heap;
}// 交换两个节点
void swapNodes(HuffmanNode** a, HuffmanNode** b) {HuffmanNode* temp = *a;*a = *b;*b = temp;
}// 比较两个节点，返回负数a < b, 0相等，正数a > b
int compare(HuffmanNode* a, HuffmanNode* b) {if (a->weight != b->weight)return a->weight - b->weight;elsereturn a->height - b->height;
}// 上浮操作
void heapifyUp(MinHeap* heap, int idx) {while (idx > 0) {int parent = (idx - 1) / 2;if (compare(heap->array[idx], heap->array[parent]) < 0) {swapNodes(&heap->array[idx], &heap->array[parent]);idx = parent;} else {break;}}
}// 下沉操作
void heapifyDown(MinHeap* heap, int idx) {int smallest = idx;while (1) {int left = 2 * idx + 1;int right = 2 * idx + 2;if (left < heap->size && compare(heap->array[left], heap->array[smallest]) < 0)smallest = left;if (right < heap->size && compare(heap->array[right], heap->array[smallest]) < 0)smallest = right;if (smallest != idx) {swapNodes(&heap->array[idx], &heap->array[smallest]);idx = smallest;} else {break;}}
}// 插入节点到堆中
void insertHeap(MinHeap* heap, HuffmanNode* node) {heap->array[heap->size] = node;heapifyUp(heap, heap->size);heap->size += 1;
}// 取出堆顶节点
HuffmanNode* extractMin(MinHeap* heap) {if (heap->size == 0)return NULL;HuffmanNode* min = heap->array[0];heap->array[0] = heap->array[heap->size - 1];heap->size -= 1;heapifyDown(heap, 0);return min;
}// 构建哈夫曼树
HuffmanNode* buildHuffmanTree(int* weights, int n) {MinHeap* heap = createMinHeap(n);// 将所有叶子节点加入堆中for (int i = 0; i < n; i++) {insertHeap(heap, createNode(weights[i]));}// 循环合并节点直到堆中只剩一个节点while (heap->size > 1) {HuffmanNode* left = extractMin(heap);HuffmanNode* right = extractMin(heap);HuffmanNode* parent = createNode(left->weight + right->weight);// 确保左子节点权值小于等于右子节点权值if (left->weight < right->weight) {parent->left = left;parent->right = right;} else if (left->weight > right->weight) {parent->left = right;parent->right = left;} else {// 权值相等，比较高度if (left->height <= right->height) {parent->left = left;parent->right = right;} else {parent->left = right;parent->right = left;}}// 更新父节点的高度parent->height = (left->height > right->height ? left->height : right->height) + 1;insertHeap(heap, parent);}HuffmanNode* root = extractMin(heap);free(heap->array);free(heap);return root;
}// 中序遍历
void inorderTraversal(HuffmanNode* node, int* result, int* index) {if (node != NULL) {inorderTraversal(node->left, result, index);   // 遍历左子树result[(*index)++] = node->weight;             // 访问当前节点inorderTraversal(node->right, result, index);  // 遍历右子树}
}int main() {int n;scanf("%d", &n);int weights[n];for (int i = 0; i < n; i++) {scanf("%d", &weights[i]);}HuffmanNode* root = buildHuffmanTree(weights, n);int* inorderResult = (int*)malloc(n * 2 * sizeof(int)); // 最大节点数为2n-1int index = 0;inorderTraversal(root, inorderResult, &index);for (int i = 0; i < index; i++) {printf("%d", inorderResult[i]);if (i != index -1) printf(" ");}printf("\n");free(inorderResult);return 0;
}

九、C++算法源码

#include <bits/stdc++.h>
using namespace std;// 定义哈夫曼树节点结构
struct HuffmanNode {int weight;               // 节点权值int height;               // 节点高度，叶子节点高度为1HuffmanNode* left;        // 左子节点HuffmanNode* right;       // 右子节点HuffmanNode(int w) : weight(w), height(1), left(nullptr), right(nullptr) {}
};// 比较器，用于优先队列
struct Compare {bool operator()(HuffmanNode* a, HuffmanNode* b) {if (a->weight != b->weight)return a->weight > b->weight; // 权值升序elsereturn a->height > b->height; // 高度升序}
};// 构建哈夫曼树
HuffmanNode* buildHuffmanTree(vector<int>& weights) {priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq;// 将所有叶子节点加入优先队列for(auto w : weights) {pq.push(new HuffmanNode(w));}// 循环合并节点直到队列中只剩一个节点while(pq.size() > 1) {HuffmanNode* left = pq.top(); pq.pop();HuffmanNode* right = pq.top(); pq.pop();HuffmanNode* parent = new HuffmanNode(left->weight + right->weight);// 确保左子节点权值小于等于右子节点权值if(left->weight < right->weight) {parent->left = left;parent->right = right;}else if(left->weight > right->weight) {parent->left = right;parent->right = left;}else {// 权值相等，比较高度if(left->height <= right->height) {parent->left = left;parent->right = right;}else {parent->left = right;parent->right = left;}}// 更新父节点的高度parent->height = max(left->height, right->height) + 1;pq.push(parent);}return pq.top();
}// 中序遍历
void inorderTraversal(HuffmanNode* node, vector<int>& result) {if(node != nullptr) {inorderTraversal(node->left, result);    // 遍历左子树result.push_back(node->weight);          // 访问当前节点inorderTraversal(node->right, result);   // 遍历右子树}
}int main(){int n;cin >> n;vector<int> weights(n);for(int &w : weights){cin >> w;}HuffmanNode* root = buildHuffmanTree(weights);vector<int> inorderResult;inorderTraversal(root, inorderResult);for(int i=0;i<inorderResult.size();i++){cout << inorderResult[i];if(i != inorderResult.size()-1) cout << " ";}cout << "\n";return 0;
}

🏆下一篇：华为OD机试真题 - 简易内存池（Python/JS/C/C++ 2024 E卷 200分）

🏆本文收录于，华为OD机试真题（Python/JS/C/C++）

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新。

在这里插入图片描述


http://www.mrgr.cn/news/55784.html

相关文章：

  • 新的类Rufus应用可带来简单的Windows 11 24H2安装旁路
  • 【详解】下载MySql安装教程（帮助数据库下载）
  • Linux运维篇-误操作已经做了pv的磁盘导致pv异常
  • 《Redis实战》note-8 构建简单的社交网站
  • ＜项目代码＞YOLOv8路面病害识别＜目标检测＞
  • 【文心智能体 | AI大师工坊】如何使用智能体插件，完成一款购物类智能体的开发，来体验一下我的智能体『科技君Tom』
  • 快快收藏！学习 Python 最常访问的10个网站
  • MyBatis-Plus中FieldFill理解与应用
  • 编程题 7-22 龟兔赛跑【PAT】
  • C++游戏开发：从基础到进阶
  • JavaWeb——Maven（6/8）：依赖管理-依赖传递 （介绍、直接依赖与间接依赖、演示、排除依赖）
  • Java 分页实战详解
  • 保研推荐信模板
  • Unity地面检测、跳跃
  • 低功耗4G模组的小秘密:RSA算法示例驾到，通通闪开...
  • 一分钟运行DBT入门示例项目(Jaffle Shop)
  • 新的类Rufus应用可带来简单的Windows 11 24H2安装旁路
  • 【07】z检验
  • Redis在实践的关键点
  • autMan框架对接飞书机器人
  • Golang | Leetcode Golang题解之第500题键盘行
  • Flutter Container容器组件实战案例
  • 精选录屏软件下载工具：记录精彩每一刻
  • 基于leaflet-polygon.fillPattern的面状对象图片填充实现
  • SQL CHECK 约束：确保数据完整性的关键
  • 【星闪技术】WS63E模块实时显示当前环境温湿度