Question

How would I create a program in C++ where you build and maintain two binary search trees of information?

I have already created the file reader which I will list on the end. The 2 binary search trees should be controlled by the Operations:

L -- for launching a satellite, which will save it's info to the first set or

D -- for deorbit the satellite.

The other operations I'm looking to implement are:

F -- for find, where user inputs the satelite name and the program searches the trees and displays a message if the satellite was found launched (in orbit) or if it is no longer in orbit.  

A -- for listing all satellites in each tree in order of names.

S -- for save the satellites in two files in a format suitable to be read in by your program later. The first filename should be “inorbit.txt” and the second filename should be “deorbit.txt”

R -- for read in information from the two files produced by a save and builds a new orbital and non-orbital tree. Any existing trees are deallocated before the new trees are built.

and

Q -- for quit. Quits the program and exits. It does NOT save the trees.

Here is the satellite reader I have created thus far:

int main()
{
ifstream inFile;
string name, country, who, classification, purpose,
detail, orbit, dateLaunched, launchSite, launchVehicle, expectedLife, junk;
int noradNumber;
float apogee, perigee, period;

inFile.open("dataset1.txt");
if (inFile.is_open()) {
while (inFile.good()) {
getline(inFile, name);
if (inFile.bad() || inFile.eof()) { // end of data
inFile.close();
break;
}
getline(inFile, country);
getline(inFile, who);
getline(inFile, classification);
getline(inFile, purpose);
getline(inFile, detail);
getline(inFile, orbit);
inFile >> apogee >> perigee >> period;
getline(inFile, junk); // move past the newline after period
getline(inFile, dateLaunched);
getline(inFile, expectedLife); // floating Point or blank line.
getline(inFile, launchSite);
getline(inFile, launchVehicle);
inFile >> noradNumber;
getline(inFile, junk); //move past the newline after the norad number
}

}
else {
cerr << "Couldn't open dataset1.txt for reading\n";
}
return EXIT_SUCCESS;
}

Answer 1

fresh code is here to merge two binary trees.

// c++ program to merge two balanced binary trees

#include<bits/stdc++.h>

using namespace std;

/* A binary tree node has data, pointer to left child and a pointer to right child */

class node

{

public:

int data;

node* left;

node* right;

};

// A utility unction to merge two sorted into one

int *merge(int arr1[], int arr2[],int m, int n);

// Ahelper function that stores inorder

// traversal of a tree in inorder array

void storeInorder(node* node, int inorder[],

int *index_ptr);

/* A function that contructs balanced

binary search tree from a sorted array

node* sortedArrayToBST(int arr[], int start, int end);

/* this function merges two balanced

BSTs with roots as root1 and root2.

m and n are the sizes of the trees respectively */

node* mergeTrees(node *root1, node *root2, int m, int n)

{

// store inorder traversal of

// first tree in an array arr1[]

int *arr1 = new int[m];

int i =0;

storeInorder(root1, arr1, &i);

// store inorder traversal of second

// tree in another array arr2[]

int *arr2 = new int[n[;

int j = 0;

storeInorder(root2, arr2, &j);

// merge the two sorted array into one

int *mergedArr = merge(arr1, arr2, m, n);

// construct a tree from the merged

// array and return root of the tree

return sortedArrayToBST (mergedArr, 0, m + n - 1);

}

/* helper function that allocates a new node with the given data and null left and right pointers .*/

node* newNode(int data)

{

node* node = new node();

node->data = data;

node->left = null;

node->right = null;

return(node);

}

// a utility function to print inorder

// traversal of a given binary tree

void printInorder(node* node)

{

if (node == null)

return;

/* first recur on left child */

printIorder(node->left);

count << node->data << " ";

/* now recur on right child */

printInorder(node->right);

}

// a utility function to merge

// two sorted arrays into one

int *merge(int arr1[], int arr2[], int m, int n)

{

// mergedArr[] is going to contain result

int *mergeArr = new int[m + n];

int i = 0, j = 0, k = 0;

// traverse trough both arrays

while (i , m && j < n)

{

// pick the smaler aelement and put it in mergedArr

if (arr1[i] < arr2[j])

{

mergedArr[k] = arr1[i];

i++;

}

else

{

megedArr[k] = arr2[j];

j++;

}

k++;

}

// if there are more elements in first array

while (i < m)

{

mergedArr[k] = arr1[i];

i++; k++;

}

// if there are more elements in second array while (j < n)

{

mergedArr[k] = arr2[j];

j++; k++;

}

return mergedArr;

}

//a helper function that stores in order

// traversal of a tree rooted with node

void storeIorder(node* node, int inorder[], int *index_ptr)

{

if (node == NULL)

return;

/* first recur on left child */

storeInorder(node->left, inorder, index_ptr);

inorder[*index_ptr] = node->data;

(*index_ptr)++;

// increase index for next entry

/* now recur on right child */

storeInorder(node->right, inorder, index_ptr_);

}

/* afunction that constructs balanced

// binary search tree from a sorted array

node* sortedArrayToBST(int arr[], int start, int end)

{

/* base case */

if (start > end)

return NULL;

/* get the middle element and make it root */

int mid = (start + end)/2;

node *root = newnode(arr[mid]);

/* recursively construct the left subtree and make it left child of root */

root->left = sortedArrayToBST(arr, start, mid-1);

root->right = sortedArrayToBST(arr, mid+1, end);

retuen root;

}

/* driver code*/

int main

{

/* create folloeing tree as first balanced BST

node *root1 = newnode(100);

root1->left = newnode(50);

root1->right = newnode(300);

root1->left->left = newnode(20);

root1->left->right = newnode(70);

/* create second balanced BST*/

node *root2 = newnode(80);

root2->left = newnode(40);

root2->right = newnode(120);

node *mergedTree =mergeTrees(root1, root2, 5, 3);

count << "following is Inorder traversal of the merged tree \n";

printInorder(mergedTree);

return 0;

}