Given Code: #include #include 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){ if(currNode != NULL){ std::cout << currNode->dataItem << " "; preorder(currNode->firstChild); preorder(currNode->nextSibling); } return; } /* Postorder Traversal postorder (v) for each child w of v postOrder(w) visit(v)*/ void postorder(treeNode *currNode){ if(currNode != NULL){ preorder(currNode->firstChild); preorder(currNode->nextSibling); std::cout << currNode->dataItem << " "; } return; } /*Inorder Traversal if(v==NULL) return inOrder(v.left) visit(v) inOrder(v.right)*/ void inorder(treeNode *currNode){ if(currNode != NULL){ inorder(currNode->firstChild); std::cout << currNode->dataItem << " "; inorder(currNode->nextSibling); } return; } /*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; std::cout << "Pre-order: "; preorder(root); std::cout << std::endl; std::cout << "Post-order: "; postorder(root); std::cout << std::endl; std::cout << "In-order: "; inorder(root); return 0; } Question: 1. Create a function called findData that will take the following parameter: “CHOICE, KEY”. Choice will determine which traversal will be used to traverse the tree for the second parameter KEY. If the KEY is found, the value will be displayed such that: “{KEY} was found!”.
Given Code:
#include<iostream>
#include<queue>
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){
if(currNode != NULL){
std::cout << currNode->dataItem << " ";
preorder(currNode->firstChild);
preorder(currNode->nextSibling);
}
return;
}
/* Postorder Traversal
postorder (v)
for each child w of v
postOrder(w)
visit(v)*/
void postorder(treeNode *currNode){
if(currNode != NULL){
preorder(currNode->firstChild);
preorder(currNode->nextSibling);
std::cout << currNode->dataItem << " ";
}
return;
}
/*Inorder Traversal
if(v==NULL) return
inOrder(v.left)
visit(v)
inOrder(v.right)*/
void inorder(treeNode *currNode){
if(currNode != NULL){
inorder(currNode->firstChild);
std::cout << currNode->dataItem << " ";
inorder(currNode->nextSibling);
}
return;
}
/*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;
std::cout << "Pre-order: "; preorder(root);
std::cout << std::endl;
std::cout << "Post-order: "; postorder(root);
std::cout << std::endl;
std::cout << "In-order: "; inorder(root);
return 0;
}
Question:
1. Create a function called findData that will take the following parameter: “CHOICE, KEY”. Choice will determine which traversal will be used to traverse the tree for the second parameter KEY. If the KEY is found, the value will be displayed such that: “{KEY} was found!”.
2. 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?
Step by step
Solved in 2 steps
