rotate.c

```

#include  #include  struct Node { int val; struct Node * left; struct Node * right; }; struct Node * create_node(int val); void destroy_tree(struct Node * root); void display_inorder(struct Node * root); void display_preorder(struct Node * root); void display_right_child(struct Node * root); struct Node * create_test_tree(); struct Node * rotate(struct Node * root) { return NULL; } void main() { struct Node * root=create_test_tree(); printf("Pre-order list: "); display_preorder(root); printf(" "); printf("In-order list: "); display_inorder(root); printf(" "); printf("List of right children: "); display_right_child(root); printf(" "); printf("Start rotating: "); struct Node * p= rotate(root); while (p!=NULL) { root=p; printf("List of right children after rotation: "); display_right_child(root); printf(" "); p= rotate(root); } printf("Done rotating "); printf("Pre-order list: "); display_preorder(root); printf(" "); printf("In-order list: "); display_inorder(root); printf(" "); destroy_tree(root); } struct Node * create_test_tree() { struct Node * p1 = create_node(1); struct Node * p2 = create_node(2); struct Node * p3 = create_node(3); struct Node * p4 = create_node(4); struct Node * p5 = create_node(5); struct Node * p6 = create_node(6); struct Node * p7 = create_node(7); struct Node * p8 = create_node(8); struct Node * p9 = create_node(9); struct Node * p10 = create_node(10); p1->right=p2; p2->right=p3; p4->left=p1; p4->right=p7; p5->right=p6; p7->left=p5; p7->right=p9; p9->left=p8; p9->right=p10; return p4; } void display_right_child(struct Node * root) { if (root==NULL) return; printf(" %2d",root->val); display_right_child(root->right); } void display_preorder(struct Node * root) { if (root==NULL) return; printf(" %2d",root->val); display_preorder(root->left); display_preorder(root->right); } void display_inorder(struct Node * root) { if (root==NULL) return; display_inorder(root->left); printf(" %2d",root->val); display_inorder(root->right); } void destroy_tree(struct Node * root) { if (root==NULL) return; destroy_tree(root->left); destroy_tree(root->right); free(root); } struct Node * create_node(int val) { struct Node * p = (struct Node *) malloc(sizeof(struct Node)); p->left=NULL; p->right=NULL; p->val = val; return p; } ```

Problem 4 [ 2pt]. This problem is about right-rotations in a binary tree: Note that in the left figure, node X1 is called "right-rotatable" because we can do a right-rotation through it. Also, note that nodes with a left child are right-rotatable. Attached is a C program rotate.c. It has the function: struct Node * rotate(struct Node * root); where root is of a binary tree, and it is assumed that the tree is not empty. The function will search for a right-rotatable node, and returns NULL if it can't find one (i.e., none of the nodes in the tree has a left child). On the other hand, if it can find one then it does a single right-rotation, then return the root of the tree. The following is the tree that is used for testing: The program will repeatedly find right-rotatable nodes, and right-rotate the nodes, until it can't do it anymore. It will result in the following tree