Given the code below, add the following to the given code: H. (5 points) Write a
ID: 3586976 • Letter: G
Question
Given the code below, add the following to the given code:
H. (5 points) Write a function to find the children of a specified node.
I. (5 points) Write a function to find the parent of a specified node.
3.6 (3points ea.ch) Rewrite the functions below using a vector from the C++ library.
A. (10 points) Write a program to store a tree as an array. In your test program, be sure to print the array values, and to print the values in tree “format”.
B. (5 points) Write a function to add an element to an existing tree.
C. (5 points) Write a function to delete an element from an existing tree.
D. (5 points) Write a function to perform an “in-order” traversal on an existing tree.
E. (5 points) Write a function to perform an “pre-order” traversal on an existing tree.
F. (5 points) Write a function to perform an “post-order” traversal on an existing tree.
G. (5 points) Write a function to perform an “level-order” traversal on an existing tree.
H. (5 points) Write a function to find the children of a specified node.
I. (5 points) Write a function to find the parent of a specified node.
#include <iostream>
#include <iomanip>
using namespace std;
int leftChild(int nodeIndex)
{
return nodeIndex * 2 + 1;
}
int rightChild(int nodeIndex)
{
return nodeIndex * 2 + 2;
}
int parent(int nodeIndex)
{
return (nodeIndex-1) / 2;
}
//Adds a node
void insert(int tArray[], int &size, int element)
{
int newSize = size + 1;
for (int i= newSize; i > newSize; i--){
tArray[i] = tArray[i -1];
}
tArray[size] = element;
}
//Deletes a node
void erase(int tArray[], int index, int size)
{
for (int i= index - 1; i < size; i++){
tArray[i] = tArray[i + 1];
}
}
//Prints a Inorder Traversal
void InOrderTraverse(const int tArray[], int index, int end)
{
if( index <= end){
InOrderTraverse(tArray, leftChild(index), end);
cout << tArray[index] << ' ';
InOrderTraverse(tArray, rightChild(index), end);
}
}
//Prints a Preorder Traversal
void PreOrderTraverse(const int tArray[], int index, int end)
{
if( index <= end){ //base case: index > end
cout << tArray[index] << ' '; //ROOT
PreOrderTraverse(tArray, leftChild(index), end); //Left Child
PreOrderTraverse(tArray, rightChild(index), end); //Right Child
}
}
//Prints a Postorder Traversal
void PostOrderTraverse(const int tArray[], int index, int end)
{
if( index <= end){
PostOrderTraverse(tArray, leftChild(index), end);
PostOrderTraverse(tArray, rightChild(index), end);
cout << tArray[index] << ' ';
}
}
//Prints a levelorder Traversal
void LevelOrderTraverse(const int tArray[], int index, int end)
{
if( index <= end){
cout << tArray[index] << ' ';
LevelOrderTraverse(tArray, index + 1, end);
}
}
//Search Parent
void searchParent(const int tArray[], int index)
{
int num = index-100;
if( num == 0)
cout <<"No parent, this is the root of the tree" << endl;
else
cout << tArray[parent(num)];
}
//Search Child
void searchChild(const int tArray[], int index)
{
int num = index-100;
cout << tArray[leftChild(num)] << " and " << tArray[rightChild(num)];
}
// Test the function
int main()
{
//define array to hold tree and partially fill it
int treeArray[50]= {100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110};
int treeSize = 11; //keep up with the number of tree nodes
cout <<"InOrder Transverse: ";
InOrderTraverse(treeArray, 0, treeSize - 1);
cout << endl;
cout <<"PreOrder Transverse: ";
//start the traversal at the root node
PreOrderTraverse(treeArray, 0, treeSize - 1);
cout << endl;
cout <<"PostOrder Transverse: ";
PostOrderTraverse(treeArray, 0, treeSize - 1);
cout << endl;
cout <<"LevelOrder Transverse: ";
LevelOrderTraverse(treeArray, 0, treeSize - 1);
cout << endl;
cout <<"Insert a node : ";
LevelOrderTraverse(treeArray, 0, treeSize - 1);
cout <<"Updated Array: ";
cout << endl;
cout <<"Delete a node : ";
LevelOrderTraverse(treeArray, 0, treeSize - 1);
cout <<"Updated Array: ";
cout << endl;
cout <<"Search Parent of : ";
LevelOrderTraverse(treeArray, 0, treeSize - 1);
cout <<"Parent of : ";
cout << endl;
cout <<"Search Child(ren) of : ";
searchParent(treeArray, 0, treeSize - 1);
cout <<"Child(ren) of : ";
cout << endl;
}
Explanation / Answer
B. (5 points) Write a function to add an element to an existing tree.
#include<iostream>
using namespace std;
{
bool Bst::add(int data) {
if (roottree == NULL) {
roottree= new BinarysearchtreeNode(data);
return true;
} else
return roottree->add(data);
}
bool BinarysearchtreeNode::add(int data) {
if (data== this->data)
return false;
else if (data < this->data) {
if (left == NULL) {
left = new binarysearchtreeNode(data);
return true;
} else
return left->add(data);
} else if (data> this->data) {
if (right == NULL) {
right = new BinarysearchtreeNode(data);
return true;
} else
return right->add(data);
}
return false;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.