Threading a Binary Tree in Pre-order and Post-order
a. Problem Analysis
We need to implement pre-order threading of a binary tree. Threading is a method that converts null pointer fields in a binary linked list into pointers pointing to the predecessor or successor node of the current node in a specific traversal order (pre-order, in-order, or post-order). This allows us to start traversal from any node in the specified order, not just the root node.
b. Algorithm Design
Our algorithm first creates a binary tree and then threads it. The threading process is implemented via a recursive function that traverses each node and checks whether its left or right child exists. If a child is absent, the corresponding left/right pointer is set to point to the predecessor/successor node. Finally, an in-order traversal is performed to verify the success of the threading.
Here is the threading code snippet:
// Function to create threads
void createThread(Node* p) {
if (p == NULL) { // If the node is null, return directly
return;
}
createThread(p->left); // Recursively process the left subtree
if (!p->left) { // If the left child is null, set the left pointer to the predecessor and mark the left thread flag as 1
p->left = pre;
p->ltag = 1;
}
if (pre && !pre->right) { // If the predecessor's right child is null, set its right pointer to the current node and mark the right thread flag as 1
pre->right = p;
pre->rtag = 1;
}
pre = p; // Update the predecessor node
createThread(p->right); // Recursively process the right subtree
}
c. Data Structure Design
We use a struct to represent a binary tree node, which includes a data field and two pointer fields pointing to the left and right children. Additionally, we add two flag fields to indicate whether the left and right pointers have been threaded.
Here is the data structure code snippet:
// Struct definition for a binary tree node
struct Node {
int data; // Node data
Node* left; // Left child
Node* right; // Right child
int ltag, rtag; // Left and right thread flags
};
d. Debugging Process
First, we create a binary tree and thread it. Then, we perform an in-order traversal to check whether the threading is successful. If the traversal result matches the expected output, we consider the threading successful.
Here is the debugging code snippet:
int main() {
// Create a binary tree
Node n1, n2, n3, n4, n5;
n1 = {1, &n2, &n3, 0, 0};
n2 = {2, &n4, &n5, 0, 0};
n3 = {3, NULL, NULL, 0, 0};
n4 = {4, NULL, NULL, 0, 0};
n5 = {5, NULL, NULL, 0, 0};
// Thread the binary tree
createThread(&n1);
// Perform in-order traversal of the threaded binary tree
inOrder(&n1);
return 0;
}
e. Output Result
The program’s output should be the in-order traversal result of the binary tree. In our example, the expected output is 4 2 5 1 3. The in-order traversal of the created binary tree should yield this sequence.
f. Source Code
#include<iostream>
using namespace std;
// Struct definition for a binary tree node
struct Node {
int data; // Node data
Node* left; // Left child
Node* right; // Right child
int ltag, rtag; // Left and right thread flags
};
// Global variable pre to store the predecessor node
Node* pre = NULL;
// Function to create threads
void createThread(Node* p) {
if (p == NULL) { // If the node is null, return directly
return;
}
createThread(p->left); // Recursively process the left subtree
if (!p->left) { // If the left child is null, set the left pointer to the predecessor and mark the left thread flag as 1
p->left = pre;
p->ltag = 1;
}
if (pre && !pre->right) { // If the predecessor's right child is null, set its right pointer to the current node and mark the right thread flag as 1
pre->right = p;
pre->rtag = 1;
}
pre = p; // Update the predecessor node
createThread(p->right); // Recursively process the right subtree
}
// Function for in-order traversal of a threaded binary tree
void inOrder(Node* p) {
while (p) {
while (!p->ltag) { // Find the leftmost node
p = p->left;
}
cout << p->data << " "; // Output node data
while (p->rtag) { // If the right pointer is a thread, jump directly to the successor node
p = p->right;
cout << p->data << " ";
}
p = p->right; // Process the right subtree
}
}
int main() {
// Create a binary tree
Node n1, n2, n3, n4, n5;
n1 = {1, &n2, &n3, 0, 0};
n2 = {2, &n4, &n5, 0, 0};
n3 = {3, NULL, NULL, 0, 0};
n4 = {4, NULL, NULL, 0, 0};
n5 = {5, NULL, NULL, 0, 0};
// Thread the binary tree
createThread(&n1);
// Perform in-order traversal of the threaded binary tree
inOrder(&n1);
return 0;
}
Adjacency Matrix and Adjacency List Storage for Graphs
a. Problem Analysis
Our goal is to implement adjacency matrix and adjacency list storage for graphs in C++. This involves two different data structures: arrays (for adjacency matrices) and linked lists (for adjacency lists).
b. Algorithm Design
Adjacency Matrix
We use a 2D array adj[MAX][MAX] to store the adjacency matrix of the graph. Each element adj[i][j] indicates whether an edge exists from node i to node j. If it exists, adj[i][j] = 1; otherwise, adj[i][j] = 0.
for (i = 1; i <= max_edges; i++) {
cin >> origin >> destin;
if ((origin == -1) && (destin == -1))
break;
if (origin >= n || destin >= n || origin < 0 || destin < 0) {
i--;
} else {
adj[origin][destin] = 1;
}
}
Adjacency List
We use an array of linked lists list<int> *adj to store the adjacency list of the graph. Each element adj[i] is a linked list containing all nodes adjacent to node i.
void Graph::addEdge(int v, int w) {
adj[v].push_back(w);
}
c. Data Structure Design
Adjacency Matrix
We use a 2D array int adj[MAX][MAX] to store the adjacency matrix. MAX is the maximum number of nodes in the graph.
Adjacency List
We use an array of linked lists list<int> *adj to store the adjacency list. V is the number of nodes in the graph.
d. Debugging Process
During implementation and debugging, we first ensured that the input edges are valid. If an edge is invalid (e.g., referencing a non-existent node), we prompt the user to re-enter it.
When adding edges to the adjacency matrix or adjacency list, we included error checks to prevent out-of-bounds array or list accesses.
e. Output Result
Finally, we can print the adjacency matrix or adjacency list to verify the correctness of our code. For the adjacency list, we traverse each node’s linked list and print all adjacent nodes.
void Graph::printGraph() {
for (int v = 0; v < V; v++) {
cout << "\n Adjacency list of vertex " << v << "\n head ";
for (auto x : adj[v])
cout << "-> " << x;
printf("\n");
}
}
f. Source Code
Adjacency Matrix Storage
#include<iostream>
#define MAX 20
using namespace std;
int adj[MAX][MAX];
int n;
void create_graph() {
int i, max_edges, origin, destin;
cout << "Enter number of nodes : ";
cin >> n;
max_edges = n * (n - 1);
for (i = 1; i <= max_edges; i++) {
cout << "Enter edge " << i << " (-1 -1 to quit) : ";
cin >> origin >> destin;
if ((origin == -1) && (destin == -1))
break;
if (origin >= n || destin >= n || origin < 0 || destin < 0) {
cout << "Invalid edge!\n";
i--;
} else {
adj[origin][destin] = 1;
}
}
}
Adjacency List Storage
#include<iostream>
#include<list>
using namespace std;
class Graph {
int V;
list<int> *adj;
public:
Graph(int V);
void addEdge(int v, int w);
void printGraph();
};
Graph::Graph(int V) {
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w) {
adj[v].push_back(w);
}
void Graph::printGraph() {
for (int v = 0; v < V; v++) {
cout << "\n Adjacency list of vertex " << v << "\n head ";
for (auto x : adj[v])
cout << "-> " << x;
printf("\n");
}
}
When will I have a drink and discuss the details again?