C++ Tree Algorithms: From Reconstruction to Minimum Spanning Trees
Rebuild a Tree from Preorder and Inorder Traversals
Description
This C++ code reconstructs a binary tree given its preorder and inorder traversal sequences. It utilizes an unordered map to store the indices of elements in the inorder sequence for efficient lookup during the reconstruction process. The code then performs a postorder traversal of the reconstructed tree and prints the node values.
Code
#include
#include
using namespace std;int idx = 0;
unordered_map idxtable;
string preord, inord;typedef struct treeNode {
char value;
struct treeNode *right;
struct treeNode *left;
} TreeNode;TreeNode *Add(int l, int r) {
if (!(r - l)) return nullptr;
TreeNode *NewNode = new TreeNode; idx++;
NewNode->value = preord[idx - 1];
if (r - l == 1) return NewNode;
int tmp = idxtable[preord[idx - 1]];
NewNode->left = Add(l, tmp);
NewNode->right = Add(tmp + 1, r);
return NewNode;
}void postorderTraversal(TreeNode *root) {
if (root == nullptr) return;
postorderTraversal(root->left);
postorderTraversal(root->right);
cout << root->value;
}int main(void) {
cin >> preord >> inord;
for (int i = 0; i < preord.size(); i++) idxtable[inord[i]] = i;
TreeNode *root = Add(0, preord.size());
postorderTraversal(root);
cout << '\n';
}
Minimum Spanning Tree using Manhattan Distance
Description
This C++ code calculates the minimum spanning tree (MST) of a set of points in a 2D plane using Prim’s algorithm with Manhattan distance as the edge weight. It utilizes a priority queue to efficiently select the next edge with the minimum weight to add to the MST. The code takes the number of points and their coordinates as input and outputs the total cost of the MST.
Code
#include
#include
#include
#include
#include
using namespace std;struct Point {
int x, y;
Point(int _x, int _y) : x(_x), y(_y) {}
};int manhattan_distance(const Point& p1, const Point& p2) {
return abs(p1.x - p2.x) + abs(p1.y - p2.y);
}int minimum_spanning_tree(const vector& points) {
int total_cost = 0;
unordered_set visited;
priority_queue, vector>, greater>> pq;
pq.push({0, 0});
while (!pq.empty()) {
pair top_item = pq.top();
int cost = top_item.first;
int idx = top_item.second;
pq.pop();
if (visited.find(idx) != visited.end()) continue;
visited.insert(idx);
total_cost += cost;
for (int i = 0; i < points.size(); i++) {
if (visited.find(i) != visited.end()) continue;
int next_cost = manhattan_distance(points[idx], points[i]);
pq.push({next_cost, i});
}
}
return total_cost;
}int main(void) {
int N;
cin >> N;
vector points;
for (int i = 0; i < N; i++) {
int x, y;
cin >> x >> y;
points.emplace_back(x, y);
}
cout << minimum_spanning_tree(points) << '\n';
}
Constructing a Binary Search Tree from Preorder Traversal
Description
This C++ code constructs a binary search tree (BST) from its preorder traversal sequence. It first sorts the input sequence to obtain the inorder traversal sequence, as the inorder traversal of a BST yields a sorted sequence. Then, it utilizes an unordered map to store the indices of elements in the inorder sequence for efficient lookup during the BST construction process. Finally, the code performs a postorder traversal of the constructed BST and prints the node values.
Code
#include
#include
#include
using namespace std;int idx = 0, ANSidx = 0, N;
unordered_map idxtable;
int preord[10000], inord[10000];typedef struct treeNode {
int value;
struct treeNode *right;
struct treeNode *left;
} TreeNode;TreeNode *Add(int l, int r) {
if (!(r - l)) return nullptr;
TreeNode *NewNode = new TreeNode; idx++;
NewNode->value = preord[idx - 1];
if (r - l == 1) return NewNode;
int tmp = idxtable[preord[idx - 1]];
NewNode->left = Add(l, tmp);
NewNode->right = Add(tmp + 1, r);
return NewNode;
}void postorderTraversal(TreeNode *root) {
if (root == nullptr) return;
postorderTraversal(root->left);
postorderTraversal(root->right);
cout << root->value;
if (ANSidx < N - 1) cout << ' ';
ANSidx++;
}int main(void) {
cin >> N;
for (int i = 0; i < N; i++) {
cin >> preord[i];
inord[i] = preord[i];
}
sort(inord, inord + N);
for (int i = 0; i < N; i++) idxtable[inord[i]] = i;
TreeNode *root = Add(0, N);
postorderTraversal(root);
cout << '\n';
}
Tree Validation
Description
This C++ code determines if a given graph is a valid tree. It takes pairs of integers as input, representing edges in the graph. The code uses Depth First Search (DFS) to traverse the graph from an arbitrary starting node. It checks if the graph has exactly one fewer edge than the number of nodes and if all nodes are visited during the DFS traversal. If both conditions are met, the graph is a valid tree.
Code
#include
#include
#include
#include
using namespace std;map> graph;
set visited;void dfs(int node) {
visited.insert(node);
for (auto i : graph[node]) {
if (!visited.count(i)) dfs(i);
}
}int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(0);
int a, b, N = 0;
while (cin >> a >> b) {
if (a == 0 && b == 0) break;
graph[a].push_back(b);
graph[b].push_back(a);
N++;
}
dfs(graph.begin()->first);
int nodeCount = graph.size();
if (((N == nodeCount - 1) && (visited.size() == nodeCount)) || N == 0) cout << "True\n";
else cout << "False\n";
}
Apple Tree Balancing
Description
This C++ code calculates the minimum number of apples to move between nodes in a tree to ensure each node (except the root) has exactly one apple more than its parent. The code represents the tree using an adjacency list and stores the initial number of apples on each node. It performs a Depth First Search (DFS) traversal to calculate the difference between the desired and actual number of apples on each node and its subtree. The absolute sum of these differences represents the minimum number of apples to move.
Code
#include
#include
using namespace std;vector graph[100005];
int val[100005];
int ans = 0;int f(int node, int p) {
for (auto &ch : graph[node]) {
if (ch != p) {
val[node] += f(ch, node);
}
}
ans += abs(val[node] - 1);
return val[node] - 1;
}int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, v, u, d;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> v >> u >> d;
val[v] = u;
while (d--) {
cin >> u;
graph[v].push_back(u);
graph[u].push_back(v);
}
}
f(v, v);
cout << ans << '\n';
}