Please show all the steps as detail as possible.... I need help with this.... **

Question

Please show all the steps as detail as possible.... I need help with this....

*****************************************************************

Need Help on C++ Programming, I need to create three different of tree programming. Can you show me and teach me how to make this programming.

*Make sure the programming is working and do not turn in a handwriting.

*Do not separate the file, use main.cpp that make me understand how to do this programming. Use "iostream"

**********************************************************************************************************************************

Program 1 Implement a tree using an array

Program 3 - Convert program 1 to a template

Explanation / Answer

Program 1

#include<iostream>
using namespace std;
public:
int size;
int* array;
void insertElement(int x);
void searchElement(int x);
void inOrder(int currentIndex);
void preOrder(int currentIndex);
void postOrder(int currentIndex);
void parent(int x);
int extendSize(int x);
BinarySearchTree (int size) {
this -> size = extendSize(size);
//cout << this -> size << endl;
this -> array = new int[this -> size];
for(int x = 0; x < this -> size; x++){
array[x] = NULL;
}
}
};
int BinarySearchTree::extendSize(int x) {
int value = 0;
for(int y = 0; y < x + 1; y++) {
value = (2 * value) + 2;
}
return value;
}
void BinarySearchTree::insertElement(int x) {
int currentIndex = 0;
cout << "Adding: " << x;
while(true) {
if(array[currentIndex] == NULL){
array[currentIndex] = x;
cout << " Inserted at index: " << currentIndex << endl;
break;
}else if(array[currentIndex] <= x) {
if(array[currentIndex] == x){
cout << "ERROR!-- Repeating element" << endl;
break;
}else
cout << " Right ";
currentIndex = (2 * currentIndex + 2);
}else if(array[currentIndex] >= x) {
if(array[currentIndex] == x){
cout << "ERROR!-- Repeating element" << endl;
break;
}else
cout << " Left ";
currentIndex = (2 * currentIndex + 1);
}
}
}
void BinarySearchTree::searchElement(int x){
int currentIndex = 0;
while (true) {
if (array[currentIndex] == NULL) {
cout << "Not Found" << endl;
break;
}
if (array[currentIndex] == x) {
cout << "Found at index: " << currentIndex << endl;
break;
}
else if(array[currentIndex] < x) {
currentIndex = (2 * currentIndex + 2);
}
else if(array[currentIndex] > x) {
currentIndex = (2 * currentIndex + 1);
}
}
}
void BinarySearchTree::parent(int x){
while (x != 0) {
x = (x-1) / 2;
cout << "---";
}
}
void BinarySearchTree::inOrder(int currentIndex){
if(array[currentIndex] != NULL) {
inOrder(2 * currentIndex + 1);
parent(currentIndex);
cout << array[currentIndex] << endl;
inOrder(2 * currentIndex + 2);
}
}
void BinarySearchTree::postOrder(int currentIndex) {
if(array[currentIndex] != NULL){
postOrder(2 * currentIndex + 1);
postOrder(2 * currentIndex + 2);
parent(currentIndex);
cout << array[currentIndex] << " " << endl;
}
}
void BinarySearchTree::preOrder(int currentIndex) {
if(array[currentIndex] != NULL) {
preOrder(2 * currentIndex + 1);
parent(currentIndex);
cout << array[currentIndex] << " " << endl;
preOrder(2 * currentIndex + 2);
}
}
int main () {
BinarySearchTree frank(5);
frank.insertElement(4);
frank.insertElement(6);
frank.insertElement(9);
frank.insertElement(3);
frank.insertElement(2);
frank.searchElement(1);
frank.inOrder(0);
};

Program 3:

#include <iostream>
#include <cstdlib>
#include <cstdio>

template<class E>
struct TNode{
E value;
TNode<E>* leftChild;
TNode<E>* rightChild;

TNode<E>(){
this->value = NULL;
this->leftChild = NULL;
this->rightChild = NULL;
}

TNode<E>(E value){
this->value = value;
this->leftChild = NULL;
this->rightChild = NULL;
}
};

template<class E>
class BTree{
private:
TNode<E>* root;

/**
build and return the pointer to a binary tree for given array 'arr' and array size 'len'
*/
TNode<E>* build(E* arr, int len){

TNode<E> *subRoot = new TNode<E>(arr[0]);
if (len == 1){
return subRoot; // terminating function - at the leaf
}
E* elementsToLeft = new E[len]; // array to store the left subtree children
E* elementsToRight = new E[len]; // array to store the right sub tree children

int counterLeft = 0;
int counterRight = 0;

for (int i = 1; i < len; i = (i * 2) + 1){
for (int j = i; j < i + ((i + 1) / 2); j++){
elementsToLeft[counterLeft] = arr[j]; // appending the array which has children of left sub tree
counterLeft++;
if ((j + (i + 1) / 2)<len){ // check whether there are childs to store in the right sub tree....
elementsToRight[counterRight] = arr[j + (i + 1) / 2]; // appending the array which has children of left sub tree
counterRight++;
}

}
}
subRoot->leftChild = build(elementsToLeft, counterLeft); // recursive call> array- left sub tree's children and size
subRoot->rightChild = build(elementsToRight, counterRight); // recursive call> array- right sub tree's children and size
return subRoot;
}

public:

/**
add the value specified by newvalueas the left child of the tree node specified by parent,if the node does not have a left childalready.
returns 1 if addition is successful and returns -1 in failure.
*/
template <class E>
int intaddLeftChild(TNode<E>* parent, E newvalue){
if (parent->leftChild != NULL){ return -1; }
TNode<E> *temp = new TNode<E>(newvalue);
parent->leftChild = temp;
return 1;
}

/**add the value specified by newvalueas the right child of the tree node specified by parent, if the node does not have a right childalready.
returns 1 if addition is successful and returns -1 in failure.
*/
template <class E>
int intaddRightChild(TNode<E>* parent, E newvalue){
if (parent->rightChild != NULL){ return -1; }
TNode<E> *temp = new TNode<E>(newvalue);
parent->rightChild = temp;
return 1;
}

/**
function to create and return the pointer to a Binary tree from an array
input an array. eg:- int i[] = {3,5,7} ; create_tree(i);
*/
template<class E, int N>
TNode<E>* create_tree(E(&elements)[N]){
int length = N;
return build(elements, N);
}
};

int main(){
//to demonstrate
int nums[] = { 7,5,9,1,7,3};
BTree<int> mal;

TNode<int>* BinaryTree = mal.create_tree(nums); // store the made binary tree from nums and point it by the pointer, BinaryTree.

}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.