資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學從給定權重構建一個沒有相鄰節點權重相同的 N 元樹
N 元樹是資料結構和演算法 (DSA) 中具有許多子節點的基本分層結構。構建一個 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 元樹時，使用廣度優先搜尋演算法遍歷給定的權重集合。與 DFS 方法類似，我們在遍歷過程中仔細選擇並分配權重，以確保相鄰節點具有不同的權重。
演算法
將給定集合中的權重按降序排序。
為一個空的 N 元樹建立一個根節點，其權重為排序集合中的最小權重。
使用根節點建立 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 元樹中保持獨特的權重至關重要。
更新於：2023年8月4日
75 次瀏覽
廣告