TreeNode* expand_leaf(TreeNode* node, ItemType x, ItemType y) that returns a new
ID: 3868703 • Letter: T
Question
TreeNode* expand_leaf(TreeNode* node, ItemType x, ItemType y) that returns a new binary tree that is identical to the binary tree T except that every leaf in T now has a left child and a right child whose values are equal to x and y, respectively. For example, invoking expand_leaf (T, 9, 12) on the tree on the left produces the tree on the right. Write a C++ function int height (TreeNode* T) that returns the height of the binary tree T. Write a C++ function bool same_tree(TreeNode* T1, TreeNode* T2) that returns true if binary trees T1 and T2 are exactly the same (same values, same structure), and returns false otherwise. You may assume that values of tree_item_type can be compared by means of the == operator.Explanation / Answer
#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(" 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.