Write a function that inserts the nodes of a binary tree into an ordered linked

Question

Write a function that inserts the nodes of a binary tree into an ordered linked list. Also write a program to test your function.
I need these headers Ch20_Ex9.cpp - given file

binarySearchTree.h

binaryTree.h

linkedList.h

orderedLinkedList.h



Here is the main program
//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;


return 0;
}
Please HELP ME I need it done ASAP. Thank you.

Explanation / Answer

#ifndef LIST_NODE_H #define LIST_NODE_H template class List; template class ListNode //nodes to be contained with a list { friend class List; public: ListNode(T); T getData(); private: T data; //templatized data stored in node ListNode* nextPtr; //pointer to the next node in list }; template ListNode::ListNode(T dataIn) { data = dataIn; //stores data in node nextPtr = 0; //initializes point to next node to null } template T ListNode::getData() //returns data stored in node { return data; } #endif List.h #ifndef LIST_H #define LIST_H #include using namespace std; #include "ListNode.h" template class List //linked list of ListNode objects { public: List(); ~List(); void insertNewNode(T); //fucntion used to insert new node in order in the list void print(); //prints the contents of the linked list ListNode* search(T); //searches for a value in the linked list and returns the point to object that contains that value private: ListNode *startPtr; //stores the pointer of first object in the linked list ListNode *endPtr; //stored the pointer of the last object in the linked list bool isEmpty(); //utility functions used to see if the list contains no elements void insertBegin(T); //inserts new node before the first node in the list void insertEnd(T); //inserts new node after the last node in the list }; template List::List() //creates list with start and end as NULL { startPtr = NULL; endPtr = NULL; } template List::~List() { if ( !isEmpty() ) // List is not empty { ListNode *currentPtr = startPtr; ListNode *tempPtr; while ( currentPtr != 0 ) // delete remaining nodes { tempPtr = currentPtr; currentPtr = currentPtr->nextPtr; delete tempPtr; } } } template bool List::isEmpty() { if(startPtr == NULL && endPtr == NULL) //if the start pointer and end pointer are NULL then the list is empty return 1; else return 0; } template void List::insertBegin(T dataIn) { if(isEmpty()) //if the list is empty create first element of the list { ListNode * newPtr = new ListNode(dataIn); //creates new node startPtr = newPtr; //start and end pointer are same becuase there is only one object in list endPtr = newPtr; }else //if node(s) exist in list insert additional object before the first { ListNode * newPtr = new ListNode(dataIn); newPtr->nextPtr = startPtr; //the next pointer of the new node points to the node that was previously first startPtr = newPtr; //the pointer for the new node is now the starting node } } template void List::insertEnd(T dataIn) { if(isEmpty()) //if the list is empty create first element of the list (same as first case in insert at begin) { ListNode * newPtr = new ListNode(dataIn); startPtr = newPtr; endPtr = newPtr; }else //if node(s) exist in the list then insert new node at the end of the list { ListNode * newPtr = new ListNode(dataIn); endPtr->nextPtr = newPtr; //the current last node's next pointer points to the new node endPtr = newPtr; //the new node is now the last node in the list } } template void List::insertNewNode(T dataIn) //general funtionn to insert new node the proper order in the list { if(isEmpty()) //if there is no nodes in the list simply insert at beginning { insertBegin(dataIn); }else //otherwise { if(dataIn data) //if the data of the new object is less than than the data of first node in list insert at beginning { insertBegin(dataIn); } else if(dataIn >= endPtr->data) //if the data of the new object is greater than than the data of last node in list insert at end { insertEnd(dataIn); } else //the new node is being inserted in order but not at the beginning or end { ListNode * currentPtr = startPtr; ListNode * newPtr = new ListNode(dataIn); //creates new node while(currentPtr != endPtr) //runs until the end of the list is reached { if((newPtr->data nextPtr->data) && (newPtr->data >= currentPtr->data)) //if the data of the new node is less the data in the next node and greater than the data in the current node, insert after current node { ListNode * next = currentPtr->nextPtr; currentPtr->nextPtr = newPtr; //current nodes next pointer now points to the new node newPtr->nextPtr = next; //the new nodes next pointer now points the node previously after the current node break; } currentPtr = currentPtr->nextPtr; //moves to the next node in the list } } } } template void List::print() { if(isEmpty()) { cout (*temp)->data) //if input data is greater than data in current node insertNewNodeUtility(&((*temp)->rightPtr),dataIn); //recursive function call with current node's right child as input leaf else //if input data is equal to data in current node cout

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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