Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- using namespace std;
- class Node {
- public:
- int data;
- Node *next;
- };
- class TNode{
- public:
- int data;
- TNode *left,*right;
- TNode(int key){
- data=key;
- left=NULL;
- right=NULL;
- }
- };
- void Inorder(TNode* root){
- if(root==NULL)
- return;
- Inorder(root->left);
- cout<<" "<<root->data;
- Inorder(root->right);
- }
- Node* MiddleNode(Node *head,Node* last){
- Node* slow=head,*fast=head;
- while(fast!=last && (fast->next)!=last){
- fast=(fast->next)->next;
- slow=slow->next;
- }
- return slow;
- }
- TNode* MakeBBST(Node* head,Node *last){
- if(head==last)
- return NULL;
- Node* mid=MiddleNode(head,last);
- TNode *root=new TNode(mid->data);
- if(head==mid)
- mid->next=last;
- root->left=MakeBBST(head,mid);
- root->right=MakeBBST(mid->next,last);
- return root;
- }
- TNode* ConvertIntoBBST(Node* head){
- if(head==NULL)
- return NULL;
- return MakeBBST(head,NULL);
- }
- void InsertAfterNode(Node *previous_node_ptr,int key) {
- if(previous_node_ptr==NULL)
- cout<<"previous node is absent";
- else{
- Node *new_node_ptr=new Node;
- new_node_ptr->data=key;
- new_node_ptr->next=previous_node_ptr->next;
- previous_node_ptr->next=new_node_ptr;
- }
- }
- void InsertFrontNode(Node **head_ref,int key) {
- Node *new_node_ptr=new Node;
- new_node_ptr->data=key;
- new_node_ptr->next=*head_ref;
- *head_ref=new_node_ptr;
- }
- void Append(Node **head_ref,int key) {
- if(*head_ref==NULL)
- InsertFrontNode(head_ref,key);
- else {
- Node *ptr=*head_ref;
- while(ptr->next!=NULL)
- ptr=ptr->next;
- InsertAfterNode(ptr,key);
- }
- }
- int main() {
- Node *head;
- head=NULL;
- Append(&head,2);
- Append(&head,3);
- Append(&head,4);
- Append(&head,5);
- TNode *root=ConvertIntoBBST(head);
- Inorder(root);
- return 0;
- }
Add Comment
Please, Sign In to add comment