Using the binary_tree_node, write a recursive function to meet the following spe
ID: 3816353 • Letter: U
Question
Using the binary_tree_node, write a recursive function to meet the following specification. Check as much of the precondition as possible.
template <class Item>
void flip(binary_tree_node<Item>* root_ptr)
// Precondition: root_ptr is the root pointer of a non-empty binary tree.
// Postcondition: The tree is now the mirror image of its original value.
// Example original tree: Example new tree:
// 1 1
// / /
// 2 3 3 2
// / /
// 4 5 5 4
Explanation / Answer
Algorithm – Mirror(tree):
#include<stdio.h>
#include<stdlib.h>
/* A binary tree node in general 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(" Inorder traversal of the constructed tree is ");
inOrder(root);
/* Convert tree to its mirror */
mirror(root);
/* Print inorder traversal of the mirror tree */
printf(" Inorder traversal of the mirror tree is ");
inOrder(root);
getchar();
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.