fork download
copy 
  1. /* C++ program to convert a Binary Tree to Threaded Tree */
  2. #include <iostream>
  3. #include <queue>
  4. using namespace std;
  5.  
  6. /* Structure of a node in threaded binary tree */
  7. struct Node
  8. {
  9.     int key;
  10.     Node *left, *right;
  11.  
  12.     // Used to indicate whether the right pointer is a normal
  13.     // right pointer or a pointer to inorder successor.
  14.     bool isThreaded;
  15. };
  16.  
  17. // Helper function to put the Nodes in inorder into queue
  18. void populateQueue(Node *root, std::queue <Node *> *q)
  19. {
  20.     if (root == NULL) return;
  21.     if (root->left)
  22.         populateQueue(root->left, q);
  23.     q->push(root);
  24.     if (root->right)
  25.         populateQueue(root->right, q);
  26. }
  27.  
  28. // Function to traverse queue, and make tree threaded
  29. void createThreadedUtil(Node *root, std::queue <Node *> *q)
  30. {
  31. 	while(!q->empty()) {
  32. 		Node* cur = q->front();
  33. 		q->pop();
  34. 		if(!cur->right) {
  35. 			cur->right = q->empty() ? NULL : q->front();
  36. 			cur->isThreaded = true;
  37. 		} 
  38. 	}
  39. }
  40.  
  41. // This function uses populateQueue() and
  42. // createThreadedUtil() to convert a given binary tree
  43. // to threaded tree.
  44. void createThreaded(Node *root)
  45. {
  46.     // Create a queue to store inorder traversal
  47.     std::queue <Node *> q;
  48.  
  49.     // Store inorder traversal in queue
  50.     populateQueue(root, &q);
  51.  
  52.     // Link NULL right pointers to inorder successor
  53.     createThreadedUtil(root, &q);
  54. }
  55.  
  56. // A utility function to find leftmost node in a binary
  57. // tree rooted with 'root'. This function is used in inOrder()
  58. Node *leftMost(Node *root)
  59. {
  60.     while (root != NULL && root->left != NULL)
  61.         root = root->left;
  62.     return root;
  63. }
  64.  
  65. // Function to do inorder traversal of a threadded binary tree
  66. void inOrder(Node *root)
  67. {
  68.     if (root == NULL) return;
  69.  
  70.     // Find the leftmost node in Binary Tree
  71.     Node *cur = leftMost(root);
  72.  
  73.     while (cur != NULL)
  74.     {
  75.         cout << cur->key << " ";
  76.  
  77.         // If this Node is a thread Node, then go to
  78.         // inorder successor
  79.         if (cur->isThreaded)
  80.             cur = cur->right;
  81.  
  82.         else // Else go to the leftmost child in right subtree
  83.             cur = leftMost(cur->right);
  84.     }
  85. }
  86.  
  87. // A utility function to create a new node
  88. Node *newNode(int key)
  89. {
  90.     Node *temp = new Node;
  91.     temp->left = temp->right = NULL;
  92.     temp->key = key;
  93.     return temp;
  94. }
  95.  
  96. // Driver program to test above functions
  97. int main()
  98. {
  99.     /*       1
  100.             / \
  101.            2   3
  102.           / \ / \
  103.          4  5 6  7   */
  104.     Node *root = newNode(1);
  105.     root->left = newNode(2);
  106.     root->right = newNode(3);
  107.     root->left->left = newNode(4);
  108.     root->left->right = newNode(5);
  109.     root->right->left = newNode(6);
  110.     root->right->right = newNode(7);
  111.  
  112.     createThreaded(root);
  113.  
  114.     cout << "Inorder traversal of creeated threaded tree is\n";
  115.     inOrder(root);
  116.     return 0;
  117. }
Success #stdin #stdout 0s 3464KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Inorder traversal of creeated threaded tree is
4 2 5 1 6 3 7
https://ideone.com/1JU0Vp
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!