#include <iostream>
using namespace std;
// Define a Node structure for the binary tree
typedef struct Node
{
int data; // Data to be stored in the node
int tag; // Tag to keep track of the link inversion
struct Node *left; // Pointer to the left child
struct Node *right; // Pointer to the right child
} Node;
// Function to create a new node with the given data
Node *creatnewNode(int data)
{
Node *newNode = new Node;
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// Function to visit a node and print its data
void visit_pres(int data)
{
cout << data << " ";
}
// Function to perform link inversion in an inorder binary tree
int link_inversion_inorder_binarytree(Node *pres)
{
// Print the message indicating the type of traversal
cout << "Link Inversion Inorder:-" << endl;
// Initialize pointers to keep track of the previous and temporary nodes
Node *prev, *tmp;
prev = NULL; // Initialize the previous pointer to NULL
int flag = 0; // Flag to keep track of the direction of traversal
if (pres == NULL) // If the tree is empty, return 0
{
return 0;
}
// Loop until the previous node is NULL and flag is 2
do
{
// If the left child exists and flag is 0, move to the left child
if (pres->left != NULL && flag == 0)
{
tmp = pres->left;
pres->left = prev;
pres->tag = 0;
prev = pres;
pres = tmp;
flag = 0;
}
else
{
// If flag is not 2, print the data of the current node
if (flag != 2)
{
visit_pres(pres->data);
}
// If the previous node is NULL and the right child is also NULL, set flag to 2
if (prev == NULL && pres->right == NULL)
{
flag = 2;
}
// If the right child exists and flag is not 2, move to the right child
if (pres->right != NULL && flag != 2)
{
tmp = pres->right;
pres->right = prev;
pres->tag = 1;
prev = pres;
pres = tmp;
flag = 0;
}
// If the previous node exists and its tag is 0, move to the left child of the previous node
else if (prev != NULL && prev->tag == 0)
{
tmp = prev->left;
prev->left = pres;
pres = prev;
prev = tmp;
flag = 1;
}
// If the previous node exists and its tag is 1, move to the right child of the previous node
else if (prev != NULL && prev->tag == 1)
{
tmp = prev->right;
prev->right = pres;
pres = prev;
prev = tmp;
flag = 2;
}
}
} while (prev != NULL || flag != 2); // Continue the loop until the previous node is NULL and flag is 2
cout << endl;
}
// Function to perform link inversion in a preorder binary tree
int link_inversion_preorder_binarytree(Node *pres)
{
// Print the message indicating the type of traversal
cout << "Link Inversion Preorder:-" << endl;
// Initialize pointers to keep track of the previous and temporary nodes
Node *prev, *tmp;
prev = NULL; // Initialize the previous pointer to NULL
int flag = 0; // Flag to keep track of the direction of traversal
if (pres == NULL) // If the tree is empty, return 0
{
return 0;
}
// Loop until the previous node is NULL and flag is 2
do
{
// If flag is 0, print the data of the current node
if (flag == 0)
{
visit_pres(pres->data);
}
// If the left child exists and flag is 0, move to the left child
if (pres->left != NULL && flag == 0)
{
tmp = pres->left;
pres->left = prev;
pres->tag = 0;
prev = pres;
pres = tmp;
flag = 0;
}
else
{
// If the right child exists and flag is not 2, move to the right child
if (pres->right != NULL && flag != 2)
{
tmp = pres->right;
pres->right = prev;
pres->tag = 1;
prev = pres;
pres = tmp;
flag = 0;
}
// If the previous node exists and its tag is 0, move to the left child of the previous node
else if (prev != NULL && prev->tag == 0)
{
// If the previous node is NULL and both left and right children of the current node are NULL, set flag to 2
if (prev == NULL && pres->left == NULL && pres->right == NULL)
{
flag = 2;
}
else
{
flag = 1;
}
tmp = prev->left;
prev->left = pres;
pres = prev;
prev = tmp;
}
// If the previous node exists and its tag is 1, move to the right child of the previous node
else if (prev != NULL && prev->tag == 1)
{
tmp = prev->right;
prev->right = pres;
pres = prev;
prev = tmp;
flag = 2;
}
}
} while (prev != NULL || flag != 2); // Continue the loop until the previous node is NULL and flag is 2
cout << endl;
}
// Function to perform link inversion in a postorder binary tree
int link_inversion_postorder_binarytree(Node *pres)
{
// Print the message indicating the type of traversal
cout << "Link Inversion Postorder:-" << endl;
// Initialize pointers to keep track of the previous and temporary nodes
Node *prev, *tmp;
prev = NULL; // Initialize the previous pointer to NULL
int flag = 0; // Flag to keep track of the direction of traversal
if (pres == NULL) // If the tree is empty, return 0
{
return 0;
}
// Loop until the previous node is NULL and flag is 2
do
{
// If the left child exists and flag is 0, move to the left child
if (pres->left != NULL && flag == 0)
{
tmp = pres->left;
pres->left = prev;
pres->tag = 0;
prev = pres;
pres = tmp;
flag = 0;
}
else
{
// If the right child exists and flag is not 2, move to the right child
if (pres->right != NULL && flag != 2)
{
tmp = pres->right;
pres->right = prev;
pres->tag = 1;
prev = pres;
pres = tmp;
flag = 0;
}
// If the previous node exists and its tag is 0, move to the left child of the previous node
else if (prev != NULL && prev->tag == 0)
{
tmp = prev->left;
prev->left = pres;
pres = prev;
prev = tmp;
flag = 1;
}
// If the previous node exists and its tag is 1, move to the right child of the previous node
else if (prev != NULL && prev->tag == 1)
{
tmp = prev->right;
prev->right = pres;
pres = prev;
prev = tmp;
flag = 2;
}
}
// If flag is 2 or both left and right children of the current node are NULL and flag is 0, print the data of the current node
if (flag == 2 || (pres->right == NULL && flag == 1) || (pres->left == NULL && pres->right == NULL && flag == 0))
{
visit_pres(pres->data);
flag = 2;
}
} while (prev != NULL || flag != 2); // Continue the loop until the previous node is NULL and flag is 2
cout << endl;
}
int main()
{
// Create the binary tree
Node *pres = NULL;
pres = creatnewNode(5);
pres->left = creatnewNode(7);
pres->right = creatnewNode(11);
pres->left->left = creatnewNode(2);
pres->left->right = creatnewNode(3);
pres->left->right->left = creatnewNode(12);
pres->right->right = creatnewNode(1);
// Perform link inversion for inorder traversal
link_inversion_inorder_binarytree(pres);
// Perform link inversion for preorder traversal
link_inversion_preorder_binarytree(pres);
// Perform link inversion for postorder traversal
link_inversion_postorder_binarytree(pres);
return 0;
}
Comments
Post a Comment