Homework SourseWrite a function that inserts the nodes of a binary tree int
Write a function that inserts the nodes of a binary tree into an ordered linked list. Also write a program to test your function. C++
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
Solution
/* 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; } |
