c++treeinsertion

Insertion of new nodes in a Tree


I want to code a class named tree for creating the Data Type Tree . I want a function inside class tree which will automatically create nodes and insert values in nodes level-wise( row-wise ). For this I have also created Queue Data Type to store addresses of the left and right of a node which is being filled . But when I traverse the tree using preOrder Traversal I just found 1 printed on my screen. ❤️ Help me in this context.

#include<iostream>
using namespace std;

struct treeNode;

struct node{
    treeNode * address;
    node * next;
};

class queue{
    node *front, *rear;
    public:
    queue(){
        front=NULL;
        rear=NULL;
    }
    void enQueue(treeNode *& item){
        node *temp=new node;
        temp->address=item;
        temp->next=NULL;
        if(front==NULL){
            front=temp;
            rear=temp;
        }
        else{
            rear->next=temp;
            rear=temp;
        }
    }
    treeNode *& deQueue(){
        treeNode *& temp=front->address;
        front=front->next;
        return(temp);
    }
} Q;

struct treeNode{
    int data;
    treeNode * left;
    treeNode * right;
};

class tree{
  public:
    treeNode * root;
    tree(){
        root=NULL;
    }
    void iTree(int item){
        treeNode *temp=new treeNode;
        temp->data=item;
        temp->left=NULL;
        temp->right=NULL;
        if(root==NULL){
            root=temp;
            Q.enQueue((root->left));
            Q.enQueue((root->right));
        }
        else{
            treeNode *& Temp=Q.deQueue();
            Temp=temp;
            Q.enQueue(Temp->left);
            Q.enQueue(Temp->right);
        }
    }
};

void preOrder(treeNode *root){
    if(root!=NULL){
        cout<<root->data<<" ";
        preOrder(root->left);
        preOrder(root->right);
    }
}

void main(){
    tree T;
    T.iTree(1);
    T.iTree(2);
    T.iTree(3);
    T.iTree(4);
    
    preOrder(T.root);
    
}

Solution

  • #include<iostream>
    using namespace std;
    
    // Prortotypes
    struct treeNode;
    
    // Queue required for Tree
    struct node{
        treeNode *address;
        node *next;
    };
    
    class queue{
        node *front, *rear;
      public:
        queue(){
            front=NULL;
            rear=NULL;
        }
        void enQueue(treeNode *);
        treeNode * deQueue();
    } Q;
    void queue::enQueue(treeNode *item){
        node *temp=new node;
        temp->address=item;
        temp->next=NULL;
        if(front==NULL){
            front=temp;
            rear=temp;
        }
        else{
            rear->next=temp;
            rear=temp;
        }
    }
    treeNode * queue::deQueue(){
        treeNode *temp=front->address;
        front=front->next;
        return(temp);
    }
    
    // Node of Tree
    struct treeNode{
        int data;
        treeNode *left;
        treeNode *right;
    };
    
    // Implementating TREE Data Structure
    class tree{
        treeNode *root;
      public:
        tree(){
            root=NULL;
        }
        void insertTree(int);
        treeNode * rtnRoot();
        
    };
    
    // Insert function 
    // (To insert new nodes in Tree)
    void tree::insertTree(int item){
        treeNode *temp=new treeNode;
        temp->data=item;
        temp->left=NULL;
        temp->right=NULL;
        if(root==NULL){
            root=temp;
            Q.enQueue(root);
            Q.enQueue(root);
        }
        else{
            treeNode *TEMP=Q.deQueue();
            if(TEMP->left==NULL){
                TEMP->left=temp;
                Q.enQueue(TEMP->left);
                Q.enQueue(TEMP->left);
            }
            else{
                TEMP->right=temp;
                Q.enQueue(TEMP->right);
                Q.enQueue(TEMP->right);
            }
        }
    }
    // root return function
    treeNode * tree::rtnRoot(){
        return(root);
    }
    
    // preOrder Traversal
    void preOrder(treeNode *root){
        if(root!=NULL){
            cout<<root->data<<" ";
            preOrder(root->left);
            preOrder(root->right);
        }
    }
    
    // Main function
    void main(){
        tree T;
        for(int i=1;i<=10;i++){
            T.insertTree(i);
        }
        
        preOrder(T.rtnRoot());
    }         
    

    I was doing a mistake earlier. I was storing left and right of a node and they are always initialized to NULL pointer . This time I'm storing the address of the node twice in the queue so that I may store values in the left and right of that node. See code for more clarity. Sorry for ridiculous explanation but I figured it out . Thanks to the community for support.