大连微网站,制作公司网页多钱,可以在线做护理题的网站,wordpress块引用美化数据结构算法题#xff08;15 分#xff0c;8 7#xff09; 1. 比较一棵二叉树的终端节点到根节点的路径长度#xff0c;路径长度为关键字之和#xff0c;输出路径长度最短的终端节点。 输入#xff1a;第一行输入一个整数 n, 表示结点的个数#xff0c;第二行输入二叉… 数据结构算法题15 分8 7 1. 比较一棵二叉树的终端节点到根节点的路径长度路径长度为关键字之和输出路径长度最短的终端节点。 输入第一行输入一个整数 n, 表示结点的个数第二行输入二叉树的中序遍历序列第三行输入二叉树的后序遍历序列。 输出路径长度最短的叶子节点的关键字。 用例 输入 7 3 2 1 4 5 7 6 3 1 2 5 6 7 4 输出 1 示例代码 #include stdio.h
#include stdlib.h// 定义二叉树节点结构
struct TreeNode {int key;struct TreeNode *left;struct TreeNode *right;
};// 构建二叉树
static struct TreeNode *BuildTree(int *inorder, int *postorder, int inStart, int inEnd, int postStart, int postEnd)
{// 终止条件中序遍历或后序遍历的起始位置超过结束位置if ((inStart inEnd) || (postStart postEnd)) {return NULL;}// 创建根节点struct TreeNode *root (struct TreeNode *)malloc(sizeof(struct TreeNode));if (!root) {return NULL; // 内存分配失败}// 根据后序遍历确定根节点值root-key postorder[postEnd];// 在中序遍历中找到根节点的位置int rootIndex;for (rootIndex inStart; rootIndex inEnd; rootIndex) {if (inorder[rootIndex] root-key) {break;}}// 计算左子树和右子树的节点数量int leftSize rootIndex - inStart;int rightSize inEnd - rootIndex;// 递归构建左子树和右子树root-left BuildTree(inorder, postorder, inStart, rootIndex - 1, postStart, postStart leftSize - 1);root-right BuildTree(inorder, postorder, rootIndex 1, inEnd, postEnd - rightSize, postEnd - 1);return root;
}// 计算从叶子节点到根节点的路径长度
static int CalculatePathLength(struct TreeNode *root)
{if (root NULL) {return 0;}// 递归计算左子树和右子树的路径长度int leftPath CalculatePathLength(root-left);int rightPath CalculatePathLength(root-right);// 返回当前节点值与左右子树中较短路径的和return root-key ((leftPath rightPath) ? rightPath : leftPath);
}// 找到路径长度最短的终端节点
static void FindShortestPathLeaf(struct TreeNode *root, int *shortestPath, int *shortestLeaf)
{if (root NULL) {return;}// 当前节点为叶子节点时if ((root-left NULL) (root-right NULL)) {// 计算当前路径长度int pathLength CalculatePathLength(root);// 更新最短路径和对应的叶子节点值if (*shortestPath -1 || pathLength *shortestPath) {*shortestPath pathLength;*shortestLeaf root-key;}}// 递归查找左右子树FindShortestPathLeaf(root-left, shortestPath, shortestLeaf);FindShortestPathLeaf(root-right, shortestPath, shortestLeaf);
}int main()
{int n;printf(Enter the number of nodes: );scanf_s(%d, n);int *inorder (int *)malloc(n * sizeof(int));int *postorder (int *)malloc(n * sizeof(int));if (!inorder || !postorder) {return -1; // 内存分配失败}// 输入中序遍历序列printf(Enter the inorder traversal sequence: );for (int i 0; i n; i) {scanf_s(%d, inorder[i]);}// 输入后序遍历序列printf(Enter the postorder traversal sequence: );for (int i 0; i n; i) {scanf_s(%d, postorder[i]);}// 构建二叉树struct TreeNode *root BuildTree(inorder, postorder, 0, n - 1, 0, n - 1);int shortestPath -1;int shortestLeaf -1;// 寻找路径长度最短的终端节点FindShortestPathLeaf(root, shortestPath, shortestLeaf);// 输出结果printf(The terminal node with the shortest path length is: %d\n, shortestLeaf);// 释放动态分配的内存free(inorder);free(postorder);return 0;
} 时间复杂度分析 构建二叉树 (BuildTree 函数) 在每次递归调用中都需要在 inorder 数组中找到根节点的位置这部分的时间复杂度是 O(n)其中 n 是节点的总数。 总体时间复杂度为 O(n log n)因为每个节点都需要在中序遍历数组中进行查找。 计算从叶子节点到根节点的路径长度 (CalculatePathLength 函数) 对于每个节点都需要递归计算其左右子树的路径长度总体时间复杂度是 O(n)其中 n 是节点的总数。 找到路径长度最短的终端节点 (FindShortestPathLeaf 函数) 在每个终端节点处都需要计算路径长度总体时间复杂度是 O(n)其中 n 是节点的总数。 主函数 (main 函数) 输入数组的读取和动态内存分配的时间复杂度是 O(n)。 最终调用 BuildTree、CalculatePathLength、FindShortestPathLeaf 函数因此主函数的总体时间复杂度是 O(n log n)。 总体时间复杂度 O(n log n) 空间复杂度分析 递归栈空间 (BuildTree 函数) 由于是递归实现每次递归调用都需要在栈上保存当前递归状态。最坏情况下递归栈的深度是二叉树的高度而二叉树的高度最坏情况下可以达到 n每个节点只有一个子节点形成的斜树。因此递归栈空间的最坏情况空间复杂度是 O(n)。 递归栈空间 (CalculatePathLength 函数) 由于是递归实现每次递归调用都需要在栈上保存当前递归状态。最坏情况下递归栈的深度是二叉树的高度而二叉树的高度最坏情况下可以达到 n。因此递归栈空间的最坏情况空间复杂度是 O(n)。 递归栈空间 (FindShortestPathLeaf 函数) 由于是递归实现每次递归调用都需要在栈上保存当前递归状态。最坏情况下递归栈的深度是二叉树的高度而二叉树的高度最坏情况下可以达到 n。因此递归栈空间的最坏情况空间复杂度是 O(n)。 动态分配的堆空间 每个节点都需要动态分配内存总体空间复杂度是 O(n)其中 n 是节点的总数。 其他变量和数组 除递归栈和动态分配的堆空间外程序中使用了一些整型变量和输入数组。这部分的空间复杂度是 O(1)。 总体空间复杂度 O(n) 输出示例 2. 在 n 个数中查询 k 个指定的数要求最少存储 示例代码 #include stdio.h
#include stdlib.h// 交换数组中两个元素的值
static void Swap(int *a, int *b)
{int temp *a;*a *b;*b temp;
}// 最小堆调整
static void Heapify(int arr[], int n, int i)
{int largest i; // 初始化最大值为根节点int left 2 * i 1; // 左子节点int right 2 * i 2; // 右子节点// 如果左子节点大于根节点if (left n arr[left] arr[largest]) {largest left;}// 如果右子节点大于最大值if (right n arr[right] arr[largest]) {largest right;}// 如果最大值不是根节点if (largest ! i) {Swap(arr[i], arr[largest]);// 递归调整受影响的子树Heapify(arr, n, largest);}
}// 构建最小堆
static void BuildHeap(int arr[], int n)
{// 构建堆重新排列数组for (int i n / 2 - 1; i 0; i--) {Heapify(arr, n, i);}
}// 堆排序
static void HeapSort(int arr[], int n)
{// 构建最大堆BuildHeap(arr, n);// 依次从堆中取出元素for (int i n - 1; i 0; i--) {// 将当前根节点移至末尾Swap(arr[0], arr[i]);// 在减小的堆上调用最大堆调整Heapify(arr, i, 0);}
}// 二分查找
static int BinarySearch(int *array, int low, int high, int target)
{while (low high) {int mid low (high - low) / 2;if (array[mid] target) {return mid 1; // 位置从1开始} else if (array[mid] target) {low mid 1;} else {high mid - 1;}}return 0; // 未找到
}int main()
{int n;// 输入 nprintf(Enter the number of elements (n): );scanf_s(%d, n);// 输入 n 个数printf(Enter %d numbers:\n, n);int *array (int *)malloc(n * sizeof(int));if (array NULL) {fprintf(stderr, Memory allocation failed\n);return 1;}for (int i 0; i n; i) {scanf_s(%d, array[i]);}// 使用最小堆排序HeapSort(array, n);// 输出排序后的数组printf(Sorted array:\n);for (int i 0; i n; i) {printf(%d , array[i]);}// 输入 kint k;printf(\nEnter the number of elements to search (k): );scanf_s(%d, k);// 输入 k 个数printf(Enter %d numbers to search:\n, k);for (int i 0; i k; i) {int searchNumber;scanf_s(%d, searchNumber);// 使用二分查找在有序数组中查找位置int position BinarySearch(array, 0, n - 1, searchNumber);if (position) {printf(%d , position);} else {printf(Not Found );}}// 释放动态分配的内存free(array);return 0;
} 时间复杂度分析 堆排序的时间复杂度 构建堆 时间复杂度为 O(n)。对每个非叶子节点进行堆调整而非叶子节点的数量是 n/2其中 n 是元素的总数。 排序 每次将最大值放到数组末尾然后对剩余的部分进行堆调整。堆调整的时间复杂度是 O(log n)而总共需要进行 n 次调整。因此排序的时间复杂度为 O(n log n)。 综合起来堆排序的时间复杂度为 O(n n log n) O(n log n)。 二分查找的时间复杂度 二分查找的时间复杂度为 O(k log n)其中 n 是数组的长度k 是要搜索的元素数量。每一次都将搜索范围缩小一半直到找到目标值或者搜索范围为空。由于 k n可以将其表示为 O(n log n)。 综合起来整个程序的时间复杂度主要由堆排序决定为 O(n log n)。 空间复杂度分析 堆排序的空间复杂度 堆排序是原地排序算法不需要额外的空间来存储数据结构只需要常数级别的辅助空间。因此堆排序的空间复杂度为O(1)。 二分查找的空间复杂度 二分查找的空间复杂度也是常数级别的为O(1)。 输入数组的空间复杂度 在堆排序前程序使用了一个大小为 n 的整数数组 (array) 来存储输入的 n 个数。因此这部分的空间复杂度为 O(n)。 其他变量的空间复杂度 除了输入数组外程序使用了一些常数级别的辅助变量如循环中的索引和临时变量。这些额外变量的空间复杂度可以被认为是 O(1)。 综合起来整个程序的空间复杂度为 O(n)其中 n 是输入的数组大小。 输出示例
