极客笔记C++ 根据给定的权重构建一个没有相邻节点具有相同权重的N叉树
N叉树是数据结构和算法中具有众多后代的基本层次结构。构建一个N叉树，并限制相邻节点的权重不能相同，是一个有趣的任务。本文研究了一种系统的方法，从一组权重中构建这样的树。我们将深入探讨完成这个任务所需的基本数据结构和算法，为实践提供详细的指南。由于在调度、决策和优化等领域广泛应用，这种独特的树形结构是DSA中的一个重要思想。
使用的方法
- 深度优先搜索（DFS）方法
-
广度优先搜索（BFS）方法
深度优先搜索（DFS）方法
深度优先搜索技术在DFS方法中被用于遍历给定的权重集合并构建N叉树。在遍历过程中，我们给节点添加权重，并确保相邻节点的权重不相同。该方法利用递归来高效地遍历权重并构建树。
步骤
- 将给定集合中的权重按降序排序。
-
为具有排序后集合的最小权重的空N叉树创建一个根节点。
-
创建一个DFS函数，该函数有两个输入：当前节点和要应用的下一个权重的索引。
-
在DFS函数中检查当前节点的权重是否与其父节点或任何已存在的后代节点的权重相匹配。如果匹配，则继续处理下一个权重并跳过该节点。
-
给当前节点赋予当前权重。
-
对当前节点的每个子节点，递归调用DFS函数，将下一个权重的索引作为参数传递。
示例
#include <iostream>
#include <vector>
#include <algorithm>
struct Node {
int weight;
std::vector<Node*> children;
Node(int w) : weight(w) {}
};
void DFS(Node* current, const std::vector<int>& weights, int&
nextWeightIndex) {
if (nextWeightIndex >= weights.size())
return;
for (Node* child : current->children) {
if (child->weight == weights[nextWeightIndex])
++nextWeightIndex;
}
if (nextWeightIndex < weights.size()) {
Node* newNode = new Node(weights[nextWeightIndex]);
current->children.push_back(newNode);
++nextWeightIndex;
}
for (Node* child : current->children) {
DFS(child, weights, nextWeightIndex);
}
}
int main() {
std::vector<int> weights = {50, 30, 40, 10, 20};
std::sort(weights.begin(), weights.end(), std::greater<int>());
Node* root = new Node(weights[0]);
int nextWeightIndex = 1;
DFS(root, weights, nextWeightIndex);
std::cout << "Tree weights in descending order: ";
std::cout << root->weight << " ";
for (Node* child : root->children) {
std::cout << child->weight << " ";
}
return 0;
}
输出
Tree weights in descending order: 50 40
广度优先搜索（BFS）方法
使用BFS方法构建N-ary树时，使用广度优先搜索算法遍历指定的权重集合。在遍历过程中，我们仔细选择和分配权重，以确保相邻节点具有不同的权重，就像DFS技术一样。
步骤
- 按降序对提供的权重集合进行排序。
-
为具有排序集的最低权重的空N-ary树创建根节点。
-
使用根节点创建BFS队列。
-
从BFS队列的前端出列节点，将排序集合的后续权重应用于它，同时BFS队列仍处于激活状态。
-
当前节点的权重应与任何现有子节点或其父节点的权重匹配。如果是这样，则继续下一个权重并忽略这个权重。
-
对于当前节点，创建子节点并将其添加到BFS队列。
-
为了消耗所有的权重，重复步骤4到6。
示例
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
struct TreeNode {
int weight;
std::vector<TreeNode*> children;
TreeNode(int w) : weight(w) {}
};
TreeNode* createRootNode(std::vector<int>& weights) {
std::sort(weights.begin(), weights.end(), std::greater<int>());
TreeNode* root = new TreeNode(weights.back());
return root;
}
void createBFSQueue(TreeNode* root, std::queue<TreeNode*>& bfsQueue) {
if (root == nullptr) return;
bfsQueue.push(root);
for (TreeNode* child : root->children) {
createBFSQueue(child, bfsQueue);
}
}
void applyWeightsAndCreateOffspring(TreeNode* node, std::vector<int>& weights) {
if (node == nullptr || weights.empty()) return;
std::vector<int> remainingWeights;
for (int weight : weights) {
if (node->weight != weight && std::find_if(node->children.begin(), node->children.end(),
[weight](const TreeNode* child) { return child->weight == weight; }) == node->children.end()) {
remainingWeights.push_back(weight);
}
}
for (int weight : remainingWeights) {
TreeNode* child = new TreeNode(weight);
node->children.push_back(child);
applyWeightsAndCreateOffspring(child, remainingWeights);
}
}
int main() {
std::vector<int> weights = {5, 2, 8, 3, 1};
TreeNode* root = createRootNode(weights);
std::queue<TreeNode*> bfsQueue;
createBFSQueue(root, bfsQueue);
while (!bfsQueue.empty()) {
TreeNode* frontNode = bfsQueue.front();
bfsQueue.pop();
applyWeightsAndCreateOffspring(frontNode, weights);
}
std::queue<TreeNode*> printQueue;
printQueue.push(root);
while (!printQueue.empty()) {
TreeNode* node = printQueue.front();
printQueue.pop();
std::cout << "Node Weight: " << node->weight << ", Children Weights: ";
for (TreeNode* child : node->children) {
std::cout << child->weight << " ";
printQueue.push(child);
}
std::cout << std::endl;
}
return 0;
}
输出
/tmp/MNiyxGtrjS.o
Node Weight: 1, Children Weights: 8 5 3 2
Node Weight: 8, Children Weights: 5 3 2
Node Weight: 5, Children Weights: 8 3 2
Node Weight: 3, Children Weights: 8 5 2
Node Weight: 2, Children Weights: 8 5 3
Node Weight: 5, Children Weights: 3 2
Node Weight: 3, Children Weights: 5 2
Node Weight: 2, Children Weights: 5 3
Node Weight: 8, Children Weights: 3 2
Node Weight: 3, Children Weights: 8 2
Node Weight: 2, Children Weights: 8 3
Node Weight: 8, Children Weights: 5 2
Node Weight: 5, Children Weights: 8 2
Node Weight: 2, Children Weights: 8 5
Node Weight: 8, Children Weights: 5 3
Node Weight: 5, Children Weights: 8 3
Node Weight: 3, Children Weights: 8 5
Node Weight: 3, Children Weights: 2
Node Weight: 2, Children Weights: 3
Node Weight: 5, Children Weights: 2
Node Weight: 2, Children Weights: 5
Node Weight: 5, Children Weights: 3
Node Weight: 3, Children Weights: 5
Node Weight: 3, Children Weights: 2
Node Weight: 2, Children Weights: 3
Node Weight: 8, Children Weights: 2
Node Weight: 2, Children Weights: 8
Node Weight: 8, Children Weights: 3
Node Weight: 3, Children Weights: 8
Node Weight: 5, Children Weights: 2
Node Weight: 2, Children Weights: 5
Node Weight: 8, Children Weights: 2
Node Weight: 2, Children Weights: 8
Node Weight: 8, Children Weights: 5
Node Weight: 5, Children Weights: 8
Node Weight: 5, Children Weights: 3
Node Weight: 3, Children Weights: 5
Node Weight: 8, Children Weights: 3
Node Weight: 3, Children Weights: 8
Node Weight: 8, Children Weights: 5
Node Weight: 5, Children Weights: 8
Node Weight: 2, Children Weights:
Node Weight: 3, Children Weights:
Node Weight: 2, Children Weights:
Node Weight: 5, Children Weights:
Node Weight: 3, Children Weights:
Node Weight: 5, Children Weights:
Node Weight: 2, Children Weights:
Node Weight: 3, Children Weights:
Node Weight: 2, Children Weights:
Node Weight: 8, Children Weights:
Node Weight: 3, Children Weights:
Node Weight: 8, Children Weights:
Node Weight: 2, Children Weights:
Node Weight: 5, Children Weights:
Node Weight: 2, Children Weights:
Node Weight: 8, Children Weights:
Node Weight: 5, Children Weights:
Node Weight: 8, Children Weights:
Node Weight: 3, Children Weights:
Node Weight: 5, Children Weights:
Node Weight: 3, Children Weights:
Node Weight: 8, Children Weights:
Node Weight: 5, Children Weights:
Node Weight: 8, Children Weights:
结论
通过使用数据结构和技术，可以构建一个N叉树，其中没有相邻节点具有相同的权重，这是一个引人入胜的主题。通过使用涉及排序和迭代赋值的系统化技术，我们可以开发一种独特的树结构，具有各种应用，如任务调度、数据组织、决策和优化。理解这个思想使我们能够构建有效的解决方案来解决在探索数据结构和算法的有趣世界中保留N叉树内唯一权重的实际问题。