code. compile. run. debug. share.
#include <limits>
#include <iostream>
#include "Btree.h"
#include "Llist.h"
#include "Stack.h"
using namespace std;
int main() {
//input numbers into linked list
cout << "How many items in list? ";
int lsize;
cin >> lsize;
Llist mylist;
int inpt;
for (int i = 1; i < (lsize + 1); i++) {
cout << "Please input item #" << i << ": ";
cin >> inpt;
mylist.push_back(inpt);
}
cout << "List created!" << endl;
mylist.output(cout);
Btree mytree = Btree(mylist); //convert to tree
cout << "Tree created!\n";
cout << "In-order traversal: \n\n";
mytree.in_order_traverse(cout, ' '); //in-order traverse
return 0;
}
#pragma once
#include <limits>
class BTNode {
public:
int val;
BTNode* right;
BTNode* left;
BTNode() {
val = INT_MIN;
right = nullptr;
left = nullptr;
}
BTNode(int inpt) {
val = inpt;
right = nullptr;
left = nullptr;
}
};
#pragma once
#include <limits>
#include <iostream>
using namespace std;
class Llist {
public:
Llist() {
head.next = nullptr;
head.val = INT_MIN;
iterator = &head;
last = &head;
mysize = 0;
}
~Llist() {
node* ptr = head.next;
node* ptr2;
while (ptr != nullptr) {
ptr2 = ptr->next;
delete ptr;
ptr = ptr2;
}
}
void push_back(int newval) {
last->next = new node;
last = last->next;
last->val = newval;
mysize++;
}
int pop_front() {
if ((mysize == 0) || (head.next == nullptr)) { return INT_MAX; };
node* tmp = head.next;
head.next = head.next->next;
int tmpval = tmp->val;
delete tmp;
mysize--;
return tmpval;
}
int lsize() {
return mysize;
}
void output(ostream& out = cout) {
node* tmp = head.next;
out << "Current Linked List: [ ";
while (tmp != nullptr) {
out << tmp->val << " ";
tmp = tmp->next;
}
out << "]\n" << endl;
}
int iterate() {// advances iterator and returns next value in list
//returns INT_MAX if no more values
if (iterator->next == nullptr) {
return INT_MAX;
}
else {
iterator = iterator->next;
return iterator->val;
}
}
void set_it() { //resets iterator to start of list
iterator = &head;
return;
}
private:
class node {
public:
int val;
node* next;
node() {
val = INT_MIN;
next = nullptr;
}
node(int inpt) {
val = inpt;
next = nullptr;
}
};
node head; //dummy node pointing to first node (or null)
node* last; //points to last node, head if list is empty
node* iterator;
int mysize;
};
#pragma once
using namespace std;
#include <iostream>
#include <limits>
#include "BTNode.h"
const int DefaultSize = 100;
const int NullData = 0;
typedef BTNode* datatype;
class Queue {
/*array-based queue; Insert inserts at end, delete deletes front, and display displays front*/
public:
Queue(): front(0), end(0), allocated(DefaultSize) {
myarray = (datatype*)malloc(DefaultSize * sizeof(datatype));
if (myarray == nullptr)
{
cout << "space not available for operation\n"; allocated = 0; return;
};
}
Queue(int requested): front(0), end(0), allocated(requested) {
myarray = (datatype*)malloc(requested * sizeof(datatype));
if (myarray == nullptr)
{
cout << "space not available for operation\n"; allocated = 0; return;
};
front = 0;
end = 0;
allocated = requested;
}
~Queue() {
if (myarray != nullptr) free(myarray);
};
/*dataype peek() {
if (front != end) { return myarray[front]; }
else return NullData;
}*/
void displayall(ostream& out, char separator) {
if (front == end) { cout << "Queue empty.\n"; return; };
int tmp = front;
while (tmp != end) {
out << (myarray[tmp]->val) << separator; //should add end of list marker
tmp = (tmp + 1) % allocated;
}
}
datatype dequeue() {
if (front == end) { cout << "Queue empty!\n\n"; return (BTNode*)nullptr; };
int tmp = front;
front = (front + 1) % allocated;
return myarray[tmp];
};
int enqueue(datatype newdata) {
//adds newdata to back of queue. If successful returns 1, otherwise 0
if (((end + 1) % allocated) == front)//queue full-resize???
{
resize(allocated * 2);
};
myarray[end] = newdata;
end = (end + 1) % allocated;
return 1;
}
int currsize() {
//returns number of slots allocated for queue
return allocated;
};
int elements() {
//returns number of elements currently in queue
return (end + allocated - front) % allocated; //allows for wraparound
}
bool full() {
//indicates if queue is full
return ((end + 1) % allocated) == front;
}
bool empty() {
//indicates if queue is empty
return (front == end);
}
private:
int front; // points to first valid element in queue. If queue empty, points to same element as end
int end; //end of queue (insertion point)--first empty element
int allocated; //elements in array, not just elements used
datatype* myarray;
void resize(int newsize) {
datatype *newarray = new datatype[newsize];
if (newarray == nullptr) { return; };
if (front == end) { delete myarray; myarray = newarray; front = 0; end = 0; return; };
//copy queue
int tmp = 0;
while (((front + tmp) % allocated != end) && (tmp < newsize)) {
newarray[tmp] = myarray[(front + tmp) % allocated];
tmp++;
}
front = 0;
end = tmp;
allocated = newsize;
delete myarray;
myarray = newarray;
}
};
#pragma once
#pragma once
#include <limits>
#include "BTNode.h"
typedef BTNode* T;
extern const T BAD_DATA= (T)nullptr;
class Stack
//stack of integers of given size
//convert to template!!!
{
public:
Stack(int requested) {
ssize = requested;
stored = 0;
bottom = new T[requested];
top = bottom; //top points to empty slot
}
~Stack() {
delete[ssize] bottom;
}
void push(T val) {
(*top) = val;
top++;
stored++;
}
T pop() {
if (top == bottom) { return BAD_DATA; };
top--;
T tmp = (*top);
stored--;
return tmp;
}
bool is_empty() {
return { stored == 0 };
}
private:
int ssize, stored;
T* bottom;
T* top;
void resize() {
//create new array, twice size
Stack* newarr = new Stack(ssize * 2);
T* tmp = this->bottom;
for (int i = 0; i < ssize; i++) {
newarr->push(*tmp);
tmp++;
}
delete this->bottom;
this->bottom = newarr->bottom;
this->top = tmp;
ssize = ssize * 2;
}
};
#pragma once
#include "Llist.h"
#include "Stack.h"
#include "Queue.h"
#include <iostream>
#include "BTNode.h"
using namespace std;
class Btree
{
public:
Btree() : root(nullptr), btsize(0) { //create empty binary tree
;
}
Btree(Llist& mylist) : root(nullptr), btsize(0)
{
//construct from list assuming mylist represents pre-fix ordered binary tree
root = new BTNode();
btsize = 1;
root->val = mylist.pop_front();
//traverse list to put in bst
Queue tmpqueue; //contains queue of all parent BTNodes without children, in topographical (l->r) order
int pulled_val=root->val; //prime queue with parent
BTNode* bst_ptr{root};
tmpqueue.enqueue(bst_ptr);
while (pulled_val < INT_MAX) {
//pull parent pointer off list
bst_ptr = tmpqueue.dequeue();
//pull 2 values off list--
pulled_val = mylist.pop_front();
if (pulled_val < INT_MAX) {
bst_ptr->left = new BTNode(pulled_val);
tmpqueue.enqueue(bst_ptr->left);
btsize++;
}
pulled_val = mylist.pop_front();
if (pulled_val < INT_MAX) {
bst_ptr->right = new BTNode(pulled_val);
tmpqueue.enqueue(bst_ptr->right);
btsize++;
}
}
}
void in_order_traverse(ostream& out, char spacer)
{
Stack mystack(100);
BTNode* ptr = root;
while (!mystack.is_empty() || ptr != nullptr) {
while (ptr != nullptr) {
mystack.push(ptr);
ptr = ptr->left;
}
if (!mystack.is_empty()) {
ptr = mystack.pop(); //get stuck here popping 4
out << ptr->val << spacer ;
ptr = ptr->right;
}
out << endl;
//if () break;
//if (!(mystack.is_empty())) { ptr = mystack.pop(); };
}
}
private:
int btsize;
BTNode* root;
};
Compiling Program...
Standard Input:
Interactive Console
Text
Program is not being debugged. Click "Debug" button to start program in debug mode.
| # | Function | File:Line |
|---|
| Variable | Value |
|---|
| Register | Value |
|---|
| Expression | Value |
|---|
| # | Description |
|---|