C++ Programming: Program Design Including Data Structures 7th Edition Ch19 Ex9 C
ID: 3868431 • Letter: C
Question
C++ Programming: Program Design Including Data Structures 7th Edition Ch19 Ex9
Ch 16 orderedLinkedList.h: https://pastebin.com/Atavitrx
Ch 16 linkedList.h: https://pastebin.com/UBEnUj4i
Ch 19 binarySearchTree.h: https://pastebin.com/R0x8xN8n
Ch 19 binaryTree.h: https://pastebin.com/BYSQRp2V
I need the createList member for bSearchTreeType<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 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 "orderedinkedList.h" using namespace std; int mainO bSearchTreeTypecint> treeRoot; orderedLinkedListcint 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) coutendl; coutExplanation / Answer
1).
template <class Type>
bool orderedLinkedList<Type>::search(const Type& searchItem) const
{
bool found = false;
nodeType<Type> *current;
current = first;
while (current != nullptr && !found)
if (current->info >= searchItem)
found = true;
else
current = current->link;
if (found)
found = (current->info == searchItem);
return found;
}
template <class Type>
void orderedLinkedList<Type>::insert(const Type& newItem)
{
nodeType<Type> *current;
nodeType<Type> *trailCurrent;
nodeType<Type> *newNode;
bool found;
newNode = new nodeType<Type>;
newNode->info = newItem;
newNode->link = nullptr;
if (first == nullptr)
{
first = newNode;
last = newNode;
count++;
}
else
{
current = first;
found = false;
while (current != nullptr && !found)
if (current->info >= newItem)
found = true;
else
{
trailCurrent = current;
current = current->link;
}
if (current == first)
{
newNode->link = first;
first = newNode;
count++;
}
else
{
trailCurrent->link = newNode;
newNode->link = current;
if (current == nullptr)
last = newNode;
count++;
}
}
}
template<class Type>
void orderedLinkedList<Type>::insertFirst(const Type& newItem)
{
insert(newItem);
}
template<class Type>
void orderedLinkedList<Type>::insertLast(const Type& newItem)
{
insert(newItem);
}
template<class Type>
void orderedLinkedList<Type>::deleteNode(const Type& deleteItem)
{
nodeType<Type> *current;
nodeType<Type> *trailCurrent;
bool found;
if (first == nullptr)
cout << "Cannot delete from an empty list." << endl;
else
{
current = first;
found = false;
while (current != nullptr && !found)
if (current->info >= deleteItem)
found = true;
else
{
trailCurrent = current;
current = current->link;
}
if (current == nullptr)
cout << "The item to be deleted is not in the "
<< "list." << endl;
else
if (current->info == deleteItem)
//deleted is in the list
{
if (first == current)
{
first = first->link;
if (first == nullptr)
last = nullptr;
delete current;
}
else
{
trailCurrent->link = current->link;
if (current == last)
last = trailCurrent;
delete current;
}
count--;
}
else
cout << "The item to be deleted is not in the "
<< "list." << endl;
}
}
2).
#include <stdlib.h>
#include <memory>
#pragma once
template <typename T>
class LinkedList;
template <typename TNode>
class LinkedListIterator
{
friend class LinkedList<typename TNode::value_type>;
TNode* p;
public:
LinkedListIterator(TNode* p) : p(p) {}
LinkedListIterator(const LinkedListIterator& other) : p(other.p) {}
LinkedListIterator& operator=(LinkedListIterator other) { std::swap(p, other.p); return *this; }
void operator++() { p = p->next; }
void operator++(int) { p = p->next; }
bool operator==(const LinkedListIterator& other) { return p == other.p; }
bool operator!=(const LinkedListIterator& other) { return p != other.p; }
const int& operator*() const { return p->data; }
LinkedListIterator<TNode> operator+(int i)
{
LinkedListIterator<TNode> iter = *this;
while (i-- > 0 && iter.p)
{
++iter;
}
return iter;
}
};
template <typename T>
class Node
{
friend class LinkedList<T>;
friend class LinkedListIterator<Node<T>>;
friend class LinkedListIterator<const Node<T>>;
Node() : next(nullptr) {}
Node(const T &data) : data(data), next(nullptr) {}
Node<T> *next;
T data;
public:
typedef T value_type;
};
template <typename T>
class LinkedList
{
typedef Node<T> node;
std::size_t size;
std::unique_ptr<node> head;
std::unique_ptr<node> tail;
void init()
{
size = 0;
head.reset(new node);
tail.reset(new node);
head->next = tail.get();
}
public:
typedef LinkedListIterator<node> iterator;
typedef LinkedListIterator<const node> const_iterator;
LinkedList() { init(); }
LinkedList(const LinkedList& other)
{
init();
const_iterator i = other.begin();
while (i != other.end())
{
add(*i);
i++;
}
head.reset(other.head.get());
tail.reset(other.tail.get());
}
LinkedList(LinkedList&& other)
{
init();
size = other.size;
head = other.head;
tail = other.tail;
other.first = nullptr;
other.size = 0;
}
LinkedList& operator=(LinkedList other)
{
swap(*this, other);
return *this;
}
LinkedList& operator=(LinkedList&& other)
{
assert(this != &other);
while (head->next != tail)
remove(begin());
head = other.head;
tail = other.tail;
size = other.size;
first = other.first;
other.size = 0;
other.first = nullptr;
return *this;
}
virtual ~LinkedList()
{
while (head->next != tail.get())
remove(begin());
}
friend void swap(LinkedList& first, LinkedList& second)
{
std::swap(first.size, second.size);
std::swap(first.head, second.head);
std::swap(first.tail, second.tail);
}
void add(const T &value)
{
node *first = new node(value);
first->next = head->next;
head->next = first;
size++;
}
void remove(iterator& removeIter)
{
node *last = head.get();
iterator i = begin();
while (i != removeIter)
{
last = i.p;
++i;
}
if (i != end())
{
last->next = i.p->next;
size--;
delete i.p;
}
}
const int getSize()
{
return size;
}
iterator begin()
{
return iterator(head->next);
}
const_iterator begin() const
{
return const_iterator(head->next);
}
iterator end()
{
return iterator(tail.get());
}
const_iterator end() const
{
return const_iterator(tail.get());
}
};
3).
#include <iostream>
using namespace std;
#include <conio.h>
struct tree
{
tree *l, *r;
int data;
}*root = NULL, *p = NULL, *np = NULL, *q;
void create()
{
int value,c = 0;
while (c < 7)
{
if (root == NULL)
{
root = new tree;
cout<<"enter value of root node ";
cin>>root->data;
root->r=NULL;
root->l=NULL;
}
else
{
p = root;
cout<<"enter value of node ";
cin>>value;
while(true)
{
if (value < p->data)
{
if (p->l == NULL)
{
p->l = new tree;
p = p->l;
p->data = value;
p->l = NULL;
p->r = NULL;
cout<<"value entered in left ";
break;
}
else if (p->l != NULL)
{
p = p->l;
}
}
else if (value > p->data)
{
if (p->r == NULL)
{
p->r = new tree;
p = p->r;
p->data = value;
p->l = NULL;
p->r = NULL;
cout<<"value entered in right ";
break;
}
else if (p->r != NULL)
{
p = p->r;
}
}
}
}
c++;
}
}
void inorder(tree *p)
{
if (p != NULL)
{
inorder(p->l);
cout<<p->data<<endl;
inorder(p->r);
}
}
void preorder(tree *p)
{
if (p != NULL)
{
cout<<p->data<<endl;
preorder(p->l);
preorder(p->r);
}
}
void postorder(tree *p)
{
if (p != NULL)
{
postorder(p->l);
postorder(p->r);
cout<<p->data<<endl;
}
}
int main()
{
create();
cout<<"printing traversal in inorder ";
inorder(root);
cout<<"printing traversal in preorder ";
preorder(root);
cout<<"printing traversal in postorder ";
postorder(root);
getch();
}
4).
#include<stdlib.h>
#include<stdio.h>
struct bin_tree {
int data;
struct bin_tree * right, * left;
};
typedef struct bin_tree node;
void insert(node ** tree, int val)
{
node *temp = NULL;
if(!(*tree))
{
temp = (node *)malloc(sizeof(node));
temp->left = temp->right = NULL;
temp->data = val;
*tree = temp;
return;
}
if(val < (*tree)->data)
{
insert(&(*tree)->left, val);
}
else if(val > (*tree)->data)
{
insert(&(*tree)->right, val);
}
}
void print_preorder(node * tree)
{
if (tree)
{
printf("%d ",tree->data);
print_preorder(tree->left);
print_preorder(tree->right);
}
}
void print_inorder(node * tree)
{
if (tree)
{
print_inorder(tree->left);
printf("%d ",tree->data);
print_inorder(tree->right);
}
}
void print_postorder(node * tree)
{
if (tree)
{
print_postorder(tree->left);
print_postorder(tree->right);
printf("%d ",tree->data);
}
}
void deltree(node * tree)
{
if (tree)
{
deltree(tree->left);
deltree(tree->right);
free(tree);
}
}
node* search(node ** tree, int val)
{
if(!(*tree))
{
return NULL;
}
if(val < (*tree)->data)
{
search(&((*tree)->left), val);
}
else if(val > (*tree)->data)
{
search(&((*tree)->right), val);
}
else if(val == (*tree)->data)
{
return *tree;
}
}
void main()
{
node *root;
node *tmp;
root = NULL;
insert(&root, 9);
insert(&root, 4);
insert(&root, 15);
insert(&root, 6);
insert(&root, 12);
insert(&root, 17);
insert(&root, 2);
printf("Pre Order Display ");
print_preorder(root);
printf("In Order Display ");
print_inorder(root);
printf("Post Order Display ");
print_postorder(root);
tmp = search(&root, 4);
if (tmp)
{
printf("Searched node=%d ", tmp->data);
}
else
{
printf("Data Not found in tree. ");
}
deltree(root);
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.