C++  Add a new leaf node called nodeM which will possess the data value of M. Make this node the child of nodeB. Perform the findData function you created in #3, what can you observe about the output?  /#3 #include #include using namespace std; struct treeNode{     char dataItem;     struct treeNode *firstChild;     struct treeNode *nextSibling; }; /* Preorder Traversal preorder (v) visit(v) for each child w of v preorder(w)*/ void preorder(treeNode *currNode, char KEY) {     if(currNode != NULL)     {         if(currNode->dataItem == KEY)         {             cout<<"KEY: "<firstChild, KEY);         preorder(currNode->nextSibling, KEY);     }     return; } /*Inorder Traversal if(v==NULL) return inOrder(v.left) visit(v) inOrder(v.right)*/ void inorder(treeNode *currNode, char KEY) {     if(currNode != NULL)     {         if(currNode->dataItem == KEY)         {             cout<<"KEY: "<firstChild, KEY);         inorder(currNode->nextSibling, KEY);     }     return; } /* Postorder Traversal postorder (v) for each child w of v postOrder(w) visit(v)*/ void postorder(treeNode *currNode, char KEY) {     if(currNode != NULL)     {         if(currNode->dataItem == KEY)         {             cout<<"KEY: "<firstChild, KEY);         preorder(currNode->nextSibling, KEY);     }     return; }          void findData(int choice, char KEY, treeNode *root) {     switch (choice)      {         case 1:             preorder(root, KEY);             break;         case 2:             inorder(root, KEY);             break;         case 3:             postorder(root, KEY);             break;         default: cout<<"Invalid Input, Please try again.\n";     } } /*Print the tree*/ int main() {     treeNode *root, *nodeB, *nodeC, *nodeD, *nodeE, *nodeF, *nodeG, *nodeH, *nodeI, *nodeJ, *nodeK, *nodeL, *nodeM, *nodeN, *nodeP, *nodeQ;     root = new treeNode; nodeB = new treeNode; nodeC = new treeNode; nodeD = new treeNode; nodeE = new treeNode; nodeF = new treeNode;     nodeG = new treeNode; nodeH = new treeNode; nodeI = new treeNode; nodeJ = new treeNode; nodeK = new treeNode; nodeL = new treeNode;     nodeM = new treeNode; nodeN = new treeNode; nodeP = new treeNode; nodeQ = new treeNode;     root->dataItem = 'A';     root->firstChild = nodeB;     root->nextSibling = NULL;     nodeB->dataItem = 'B';     nodeB->firstChild = NULL;     nodeB->nextSibling = nodeC;     nodeC->dataItem = 'C';     nodeC->firstChild = NULL;     nodeC->nextSibling = nodeD;     nodeD->dataItem = 'D';     nodeD->firstChild = nodeH;     nodeD->nextSibling = nodeE;     nodeE->dataItem = 'E';     nodeE->firstChild = nodeI;     nodeE->nextSibling = nodeF;     nodeF->dataItem = 'F';     nodeF->firstChild = nodeK;     nodeF->nextSibling = nodeG;     nodeG->dataItem = 'G';     nodeG->firstChild = nodeN;     nodeG->nextSibling = NULL;     nodeH->dataItem = 'H';     nodeH->firstChild = NULL;     nodeH->nextSibling = NULL;     nodeI->dataItem = 'I';     nodeI->firstChild = NULL;     nodeI->nextSibling = nodeJ;     nodeJ->dataItem = 'J';     nodeJ->firstChild = nodeP;     nodeJ->nextSibling = NULL;     nodeK->dataItem = 'K';     nodeK->firstChild = NULL;     nodeK->nextSibling = nodeL;     nodeL->dataItem = 'L';     nodeL->firstChild = NULL;     nodeL->nextSibling = nodeM;     nodeM->dataItem = 'M';     nodeM->firstChild = NULL;     nodeM->nextSibling = NULL;     nodeN->dataItem = 'N';     nodeN->firstChild = NULL;     nodeN->nextSibling = NULL;     nodeP->dataItem = 'P';     nodeP->firstChild = NULL;     nodeP->nextSibling = nodeQ;     nodeQ->dataItem = 'Q';     nodeQ->firstChild = NULL;     nodeQ->nextSibling = NULL;          int CHOICE;     char KEY;          cout<<"PRESS 1 for Pre-Order Traversal\n";     cout<<"PRESS 2 for In-Order Traversal\n";     cout<<"PRESS 3 for Post-Order Traversal\n";          cout<<"\n";          cout<<"Enter your CHOICE and KEY: (Example Format: 1 A, 2 B, 3 C) \n";          cout<<"\n";          cout<<"INPUT: ";          cin>>CHOICE>>KEY;          findData(CHOICE, KEY, root);          /*      FOR CHECKING:      Pre-order: A B C D H E I J P Q F K L M G N       Post-order: B C D H E I J P Q F K L M G N A       In-order: B C H D I P Q J E K L M F N G A     */     return 0; }

C++

 Add a new leaf node called nodeM which will possess the data value of M. Make this node the child of nodeB. Perform the findData function you created in #3, what can you observe about the output? 

/#3

#include<iostream>
#include<queue>
using namespace std;

struct treeNode{
    char dataItem;
    struct treeNode *firstChild;
    struct treeNode *nextSibling;
};

/* Preorder Traversal
preorder (v)
visit(v)
for each child w of v
preorder(w)*/
void preorder(treeNode *currNode, char KEY)
{

    if(currNode != NULL)
    {
        if(currNode->dataItem == KEY)
        {
            cout<<"KEY: "<<KEY<< " was found!\n";
        }
        preorder(currNode->firstChild, KEY);
        preorder(currNode->nextSibling, KEY);
    }
    return;
}

/*Inorder Traversal
if(v==NULL) return
inOrder(v.left)
visit(v)
inOrder(v.right)*/
void inorder(treeNode *currNode, char KEY)
{
    if(currNode != NULL)
    {
        if(currNode->dataItem == KEY)
        {
            cout<<"KEY: "<<KEY<< " was found!\n";
        }
        
        inorder(currNode->firstChild, KEY);
        inorder(currNode->nextSibling, KEY);
    }
    return;
}

/* Postorder Traversal
postorder (v)
for each child w of v
postOrder(w)
visit(v)*/
void postorder(treeNode *currNode, char KEY)
{
    if(currNode != NULL)
    {
        if(currNode->dataItem == KEY)
        {
            cout<<"KEY: "<<KEY<< " was found!\n";
        }
        preorder(currNode->firstChild, KEY);
        preorder(currNode->nextSibling, KEY);
    }
    return;
}
        
void findData(int choice, char KEY, treeNode *root)
{
    switch (choice) 
    {
        case 1:
            preorder(root, KEY);
            break;
        case 2:
            inorder(root, KEY);
            break;
        case 3:
            postorder(root, KEY);
            break;
        default: cout<<"Invalid Input, Please try again.\n";
    }
}

/*Print the tree*/

int main()
{
    treeNode *root, *nodeB, *nodeC, *nodeD, *nodeE, *nodeF, *nodeG, *nodeH, *nodeI, *nodeJ, *nodeK, *nodeL, *nodeM, *nodeN, *nodeP, *nodeQ;
    root = new treeNode; nodeB = new treeNode; nodeC = new treeNode; nodeD = new treeNode; nodeE = new treeNode; nodeF = new treeNode;
    nodeG = new treeNode; nodeH = new treeNode; nodeI = new treeNode; nodeJ = new treeNode; nodeK = new treeNode; nodeL = new treeNode;
    nodeM = new treeNode; nodeN = new treeNode; nodeP = new treeNode; nodeQ = new treeNode;

    root->dataItem = 'A';
    root->firstChild = nodeB;
    root->nextSibling = NULL;

    nodeB->dataItem = 'B';
    nodeB->firstChild = NULL;
    nodeB->nextSibling = nodeC;

    nodeC->dataItem = 'C';
    nodeC->firstChild = NULL;
    nodeC->nextSibling = nodeD;

    nodeD->dataItem = 'D';
    nodeD->firstChild = nodeH;
    nodeD->nextSibling = nodeE;

    nodeE->dataItem = 'E';
    nodeE->firstChild = nodeI;
    nodeE->nextSibling = nodeF;

    nodeF->dataItem = 'F';
    nodeF->firstChild = nodeK;
    nodeF->nextSibling = nodeG;

    nodeG->dataItem = 'G';
    nodeG->firstChild = nodeN;
    nodeG->nextSibling = NULL;

    nodeH->dataItem = 'H';
    nodeH->firstChild = NULL;
    nodeH->nextSibling = NULL;

    nodeI->dataItem = 'I';
    nodeI->firstChild = NULL;
    nodeI->nextSibling = nodeJ;

    nodeJ->dataItem = 'J';
    nodeJ->firstChild = nodeP;
    nodeJ->nextSibling = NULL;

    nodeK->dataItem = 'K';
    nodeK->firstChild = NULL;
    nodeK->nextSibling = nodeL;

    nodeL->dataItem = 'L';
    nodeL->firstChild = NULL;
    nodeL->nextSibling = nodeM;

    nodeM->dataItem = 'M';
    nodeM->firstChild = NULL;
    nodeM->nextSibling = NULL;

    nodeN->dataItem = 'N';
    nodeN->firstChild = NULL;
    nodeN->nextSibling = NULL;

    nodeP->dataItem = 'P';
    nodeP->firstChild = NULL;
    nodeP->nextSibling = nodeQ;

    nodeQ->dataItem = 'Q';
    nodeQ->firstChild = NULL;
    nodeQ->nextSibling = NULL;
    
    int CHOICE;
    char KEY;
    
    cout<<"PRESS 1 for Pre-Order Traversal\n";
    cout<<"PRESS 2 for In-Order Traversal\n";
    cout<<"PRESS 3 for Post-Order Traversal\n";
    
    cout<<"\n";
    
    cout<<"Enter your CHOICE and KEY: (Example Format: 1 A, 2 B, 3 C) \n";
    
    cout<<"\n";
    
    cout<<"INPUT: ";
    
    cin>>CHOICE>>KEY;
    
    findData(CHOICE, KEY, root);
    
    /*
     FOR CHECKING:
     Pre-order: A B C D H E I J P Q F K L M G N 
     Post-order: B C D H E I J P Q F K L M G N A 
     In-order: B C H D I P Q J E K L M F N G A
    */

    return 0;

}