1. The programming language is C++ 2. Write a function that inserts the nodes of
ID: 3860259 • Letter: 1
Question
1. The programming language is C++
2. Write a function that inserts the nodes of a binary tree into an ordered linked list. Also write a program to test your function.
a. Do not change anything in the supplied Ch19_Ex9.cpp except to add documentation and your name.
b. Please use the file names listed below since your file will have the following components:
Ch19_Ex9.cpp shown below
//Data
//68 43 10 56 77 82 61 82 33 56 72 66 99 88 12 6 7 21 -999
#include <iostream>
#include "binarySearchTree.h"
#include "orderedLinkedList.h"
using namespace std;
int main()
{
bSearchTreeType<int> treeRoot;
orderedLinkedList<int> newList;
int num;
cout << "Enter numbers ending with -999" << endl;
cin >> num;
while (num != -999)
{
treeRoot.insert(num);
cin >> num;
}
cout << endl << "Tree nodes in inorder: ";
treeRoot.inorderTraversal();
cout << endl;
cout << "Tree Height: " << treeRoot.treeHeight()
<< endl;
treeRoot.createList(newList);
cout << "newList: ";
newList.print();
cout << endl;
system("pause");
return 0;
}
binarySearchTree.h
binaryTree.h
linkedList.h
orderedLinkedList.h
Please lable which code goes in which file
Explanation / Answer
//Code in orderedLinkedList.h
#ifndef OrderedLinkedlist
#define OrderedLinkedList
struct Node
{
int data;
struct Node* next;
}
void sorted(struct Node** head , struct Node* new1)
{
struct Node* current;
if(*head==NULL || (*head)->data >=new1->data)
{
new1->next=*head;
*head=new1;
}
else
{
current=*head;
while(current->next != NULL && current->next->data < new1->data)
{
current=current->next;
}
new1->next=current->next;
current->next = new1;
}}
void print(struct Node* head)
{
struct Node* t =head;
while(t!=NULL)
{
printf("%d n",t->data);
t=t->next;
}
//Code in Binary tree.h file
#ifndef BinaryTree
#define BinaryTree
void insert(int n)
{
Node* new_node;
new_node = new Node;
new_node->data=n;
new_node->next=NULL;
return new_node;
}
// Program to test
#include<iostream.h>
#include"BinaryTree.h"
#include"OrderedLinkedList.h"
int main()
{
BinaryTree<int> treeRoot1;
OrderedLinkedList<int> newList1;
int x;
struct Node* head = NULL;
struct Node *new_node;
cout<<"enter numbers ending with -999"<<endl;
cin>>x;
while(x!=-999)
{
new_node=treeRoot1.insert(x);
newList1.sorted(&head, new_node);
cin >> x;
}
cout << endl << "Tree nodes in ordered linked list";
newList1.print(head);
return 0;
}
Explaination:
In the program first code is of OrderedLinkedList.h
In this there are two functions:
1) sorted() : This function takes two arguments head of the linked list and a new node that is to be inserted in ordered linked list. In this first we have checked weather the linked list is empty or has a single node having data greater than the data of new node. If any of the above condition satisfy then we insert the new node as the first node of the linked list.
But if the linked list already has some nodes then we will do the traversing either till the end of the list or till we find any node whose data is greater than data of the new node. When we find the position then we will make it as the current node and insert the new node after the current node.
2) print(): This function takes head of the linked list as an argument and traverse the linked list till the last node and will print the data of each node.
Second code is of BinaryTree.h file
In this there is one function:
1) insert(): This function simply takes an integer number as an argument and add create a node of it.
Third code is used to test the above code
In this program we have included OrderedLinkedList and Binary tree header files. We ask user to input numbers and in last enter -999. We inserted that number in binary tree by calling insert function. Then called sorted function and in last called print function to print the list.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.