I have the following implementation to mirror the binary tree.
#include<stdio.h>
#include<stdlib.h>
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
/* Change a tree so that the roles of the left and
right pointers are swapped at every node.
So the tree...
4
/ \
2 5
/ \
1 3
is changed to...
4
/ \
5 2
/ \
3 1
*/
void mirror(struct node* node)
{
if (node==NULL)
return;
else
{
struct node* temp;
/* do the subtrees */
mirror(node->left);
mirror(node->right);
/* swap the pointers in this node */
temp = node->left;
node->left = node->right;
node->right = temp;
}
}
/* Helper function to test mirror(). Given a binary
search tree, print out its data elements in
increasing sorted order.*/
void inOrder(struct node* node)
{
if (node == NULL)
return;
inOrder(node->left);
printf("%d ", node->data);
inOrder(node->right);
}
/* Driver program to test mirror() */
int main()
{
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
/* Print inorder traversal of the input tree */
printf("\n Inorder traversal of the constructed tree is \n");
inOrder(root);
/* Convert tree to its mirror */
mirror(root);
/* Print inorder traversal of the mirror tree */
printf("\n Inorder traversal of the mirror tree is \n");
inOrder(root);
getchar();
return 0;
}
I am talking about the following line:
struct node* node = (struct node*)
malloc(sizeof(struct node));
I have intermediate knowledge of c/c++ but I am quite afraid of pointers. Even after several tries I have never been able to get pointers. I avoid them as far as possible but when come to implementing data structures like trees there is no other options. Why are we using malloc and sizeof here? Also why are we casting (struct node*)?