193030

Invert a binary tree // net

Nov 28th, 2020
689
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. /* A node contains the value, left and right pointers */
  5. struct Node
  6. {
  7.     int data;
  8.     struct Node* left;
  9.     struct Node* right;
  10. };
  11.  
  12. /* Creates a new node */
  13. struct Node* newNode(int data)
  14. {
  15.     Node* node = new Node;
  16.     node->data = data;
  17.     node->left = NULL;
  18.     node->right = NULL;
  19.    
  20.     return(node);
  21. }
  22.  
  23. void invert(struct Node* node)
  24. {
  25.     if (node == NULL)
  26.         return;
  27.     else
  28.     {
  29.         struct Node* temp;
  30.        
  31.         /* recursive calls */
  32.         invert(node->left);
  33.         invert(node->right);
  34.    
  35.         /* swap the pointers in this node */
  36.         temp     = node->left;
  37.         node->left = node->right;
  38.         node->right = temp;
  39.     }
  40. }
  41.  
  42. /* print InOrder binary tree traversal.*/
  43. void print_tree(struct Node* node)
  44. {
  45.     if (node == NULL)
  46.         return;
  47.    
  48.     print_tree(node->left);
  49.     cout << node->data << " ";
  50.     print_tree(node->right);
  51. }
  52.  
  53.  
  54. int main()
  55. {
  56.     struct Node *root = newNode(2);
  57.     root->left = newNode(1);
  58.     root->right = newNode(4);
  59.     root->right->left = newNode(3);
  60.     root->right->right = newNode(5);
  61.    
  62.     cout << "Inorder traversal of the constructed"
  63.         << " tree is" << endl;
  64.     print_tree(root);
  65.    
  66.     /* Invert the tree */
  67.     invert(root);
  68.    
  69.     cout << endl;
  70.  
  71.     cout << "Inorder traversal of the inverted tree"
  72.         << " is \n";
  73.     print_tree(root);
  74.    
  75.     return 0;
  76. }
RAW Paste Data