Threaded Binary Tree

Threaded-Binary-Tree.cpp

  struct dnode
  {
  	dnode*left;
  	dnode *right;
  	int data;
  	bool right_theard;
  	bool left_theard;
  
  };
  class tbst {
  private: 
  	dnode*droot; 	
  public: 
  	tbst(){
  								      /* Constructor to create  */
  		droot = new dnode; 				      /* dummy node. 		*/
  		droot -> left = droot;
  	       	droot -> right =  droot;
  		droot->left_theard=true;
  		droot -> data = INT_MAX; 			     
  	}
  	void insert(int value) {
  		dnode*check_key = droot;
  		while(1) {
  			if (check_key->data < value) {
  				if(check_key->right_theard) break;    /* Trying to find the best */
  				check_key = check_key-> right;	      /* place to insert the new */
  			}					      /* node, like a regular	 */
  			else if (check_key->data > value) {           /* binary tree, but as you */
  				if(check_key->left_theard) break;     /* can notice, I check for */  
  				check_key = check_key -> left;	      /* free node place with    */
  								      /* its threaded rather	 */
  								      /* nullptr 		 */
  			} else return;				      /* invaild input to inser  */
  		}
  		dnode* new_node = new dnode;
  		new_node->data = value;
  		new_node->right_theard = true;
  		new_node->left_theard = true;
  		if (check_key->data < value) {			      /* insertion in the right. */
  			new_node->right = check_key->right; 
  			new_node->left = check_key; 
  			check_key->right = new_node;
  			check_key->right_theard = false;
  		}
  		else  { 					      /* insertion in the left.  */
  			new_node->right = check_key; 
  			new_node->left = check_key->left; 
  			check_key->left = new_node;
  			check_key->left_theard = false;
  		}
  			
  	}
  	dnode* leftmost(dnode*droot)                                  /* function to get the     */
  								      /* leftmost node, you can  */
  								      /* also include this in    */
  	{							      /* next function without   */
  	while(!droot->left_theard) droot = droot->left;               /* recursion, if you don't */
  	return droot; 						      /* want to use any stack,  */
  	} 							      /* but I prefer to   	 */
  	void inorder(){						      /* implement it like this  */
  		dnode *it = leftmost(droot);
  		while(1)
  		{
		std::cout << it->data;				      /* print it! we are in the */
  		if ( it->right_theard)				      /* leftmose, then go to    */
  		it = it->right; 				      /* right_theard which will */
  		 else it = leftmost(it->right);			      /* be its root, then go    */
  		if (it ==droot) break; 				      /* right to get the right  */
  		}						      /* node. If we rached the  */	
  	}							      /* root again, then we're  */
  								      /* done. 			 */
  };