//I need working and clear solution Write a function that inserts the nodes of a
ID: 3917378 • Letter: #
Question
//I need working and clear solution
Write a function that inserts the nodes of a binary tree into an ordered linked list. Also, write a program to test your function.
Do not change anything in the supplied Ch19_Ex9.cpp except to add documentation and your name.
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
Explanation / Answer
/* Program to insert in a sorted list */
#include<stdio.h>
#include<stdlib.h>
/* Link list node */
struct Node
{
int data;
struct Node* next;
};
/* function to insert a new_node in a list. Note that this
function expects a pointer to head_ref as this can modify the
head of the input linked list (similar to push())*/
void sortedInsert(struct Node** head_ref, struct Node* new_node)
{
struct Node* current;
/* Special case for the head end */
if (*head_ref == NULL || (*head_ref)->data >= new_node->data)
{
new_node->next = *head_ref;
*head_ref = new_node;
}
else
{
/* Locate the node before the point of insertion */
current = *head_ref;
while (current->next!=NULL &&
current->next->data < new_node->data)
{
current = current->next;
}
new_node->next = current->next;
current->next = new_node;
}
}
/* BELOW FUNCTIONS ARE JUST UTILITY TO TEST sortedInsert */
/* A utility function to create a new node */
struct Node *newNode(int new_data)
{
/* allocate node */
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));
/* put in the data */
new_node->data = new_data;
new_node->next = NULL;
return new_node;
}
/* Function to print linked list */
void printList(struct Node *head)
{
struct Node *temp = head;
while(temp != NULL)
{
printf("%d ", temp->data);
temp = temp->next;
}
}
/* Drier program to test count function*/
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
struct Node *new_node = newNode(5);
sortedInsert(&head, new_node);
new_node = newNode(10);
sortedInsert(&head, new_node);
new_node = newNode(7);
sortedInsert(&head, new_node);
new_node = newNode(3);
sortedInsert(&head, new_node);
new_node = newNode(1);
sortedInsert(&head, new_node);
new_node = newNode(9);
sortedInsert(&head, new_node);
printf(" Created Linked List ");
printList(head);
return 0;
}
---------------------------------------------------------------------------------------------------------------------------------------------
/* Program to insert in a sorted list */
#include<stdio.h>
#include<stdlib.h>
/* Link list node */
struct Node
{
int data;
struct Node* next;
};
/* function to insert a new_node in a list. Note that this
function expects a pointer to head_ref as this can modify the
head of the input linked list (similar to push())*/
void sortedInsert(struct Node** head_ref, struct Node* new_node)
{
struct Node* current;
/* Special case for the head end */
if (*head_ref == NULL || (*head_ref)->data >= new_node->data)
{
new_node->next = *head_ref;
*head_ref = new_node;
}
else
{
/* Locate the node before the point of insertion */
current = *head_ref;
while (current->next!=NULL &&
current->next->data < new_node->data)
{
current = current->next;
}
new_node->next = current->next;
current->next = new_node;
}
}
/* BELOW FUNCTIONS ARE JUST UTILITY TO TEST sortedInsert */
/* A utility function to create a new node */
struct Node *newNode(int new_data)
{
/* allocate node */
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));
/* put in the data */
new_node->data = new_data;
new_node->next = NULL;
return new_node;
}
/* Function to print linked list */
void printList(struct Node *head)
{
struct Node *temp = head;
while(temp != NULL)
{
printf("%d ", temp->data);
temp = temp->next;
}
}
/* Drier program to test count function*/
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
struct Node *new_node = newNode(5);
sortedInsert(&head, new_node);
new_node = newNode(10);
sortedInsert(&head, new_node);
new_node = newNode(7);
sortedInsert(&head, new_node);
new_node = newNode(3);
sortedInsert(&head, new_node);
new_node = newNode(1);
sortedInsert(&head, new_node);
new_node = newNode(9);
sortedInsert(&head, new_node);
printf(" Created Linked List ");
printList(head);
return 0;
}
---------------------------------------------------------------------------------------------------------------------------------------------
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.