Scribd
Upload
6 views

271.TreeClassUsingArrayQueueC++ (1)

Uploaded by

pmallik1977
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
6 views

271.TreeClassUsingArrayQueueC++ (1)

Uploaded by

pmallik1977
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
You are on page 1/ 5

#include <iostream>

using namespace std;

class Node{
public:
Node* lchild;
int data;
Node* rchild;
};

class Queue{
private:
int size;
int front;
int rear;
Node** Q; // [Node*]*: Pointer to [Pointer to Node]
public:
Queue(int size);
~Queue();
bool isFull();
bool isEmpty();
void enqueue(Node* x);
Node* dequeue();
};

Queue::Queue(int size) {
this->size = size;
front = -1;
rear = -1;
Q = new Node* [size];
}

Queue::~Queue() {
delete [] Q;
}

bool Queue::isEmpty() {
if (front == rear){
return true;
}
return false;
}

bool Queue::isFull() {
if (rear == size-1){
return true;
}
return false;
}

void Queue::enqueue(Node* x) {
if (isFull()){
cout << "Queue Overflow" << endl;
} else {
rear++;
Q[rear] = x;
}
}
Node* Queue::dequeue() {
Node* x = nullptr;
if (isEmpty()){
cout << "Queue Underflow" << endl;
} else {
front++;
x = Q[front];
}
return x;
}

class Tree{
private:
Node* root;
public:
Tree() { root = nullptr; }
~Tree();
void CreateTree();
void Preorder(){ Preorder(root); } // Passing Private Parameter in Constructor
void Preorder(Node* p);
void Postorder(){ Postorder(root); } // Passing Private Parameter in
Constructor
void Postorder(Node* p);
void Inorder(){ Inorder(root); }
void Inorder(Node* p);
void Levelorder(){ Levelorder(root); } // Passing Private Parameter in
Constructor
void Levelorder(Node* p);
int Height(){ return Height(root); } // Passing Private Parameter in
Constructor
int Height(Node* p);
Node* getRoot(){ return root; }
};

void Tree::CreateTree() {
Node* p;
Node* t;
int x;

Queue q(25);
root = new Node;
cout << "Enter root value: " << flush;
cin >> x;
root->data = x;
root->lchild = nullptr;
root->rchild = nullptr;
q.enqueue(root);

while (! q.isEmpty()){
p = q.dequeue();

cout << "Enter left child value of " << p->data << ": " << flush;
cin >> x;
if (x != -1){
t = new Node;
t->data = x;
t->lchild = nullptr;
t->rchild = nullptr;
p->lchild = t;
q.enqueue(t);
}

cout << "Enter left child value of " << p->data << ": " << flush;
cin >> x;
if (x != -1){
t = new Node;
t->data = x;
t->lchild = nullptr;
t->rchild = nullptr;
p->rchild = t;
q.enqueue(t);
}
}
}

void Tree::Preorder(Node *p) {


if (p){
cout << p->data << ", " << flush;
Preorder(p->lchild);
Preorder(p->rchild);
}
}

void Tree::Inorder(Node *p) {


if (p){
Inorder(p->lchild);
cout << p->data << ", " << flush;
Inorder(p->rchild);
}
}

void Tree::Postorder(Node *p) {


if (p){
Postorder(p->lchild);
Postorder(p->rchild);
cout << p->data << ", " << flush;
}
}

void Tree::Levelorder(Node *p) {


Queue q(100);
cout << root->data << ", " << flush;
q.enqueue(root);

while (! q.isEmpty()){
p = q.dequeue();
if (p->lchild){
cout << p->lchild->data << ", " << flush;
q.enqueue(p->lchild);
}
if (p->rchild){
cout << p->rchild->data << ", " << flush;
q.enqueue(p->rchild);
}
}
}
int Tree::Height(Node *p) {
int l = 0;
int r = 0;
if (p == nullptr){
return 0;
}

l = Height(p->lchild);
r = Height(p->rchild);
if (l > r){
return l + 1;
} else {
return r + 1;
}
}

Tree::~Tree() {
// TODO
}

int main(){

Tree t;

t.CreateTree();

cout << "Preorder: " << flush;


t.Preorder(t.getRoot());
cout << endl;

cout << "Inorder: " << flush;


t.Inorder(t.getRoot());
cout << endl;

cout << "Postorder: " << flush;


t.Postorder(t.getRoot());
cout << endl;

cout << "Levelorder: " << flush;


t.Levelorder(t.getRoot());
cout << endl;

cout << "Height: " << t.Height(t.getRoot()) << endl;

cout << "Recursive Passing Private Parameter in Constructor" << endl;

cout << "Preorder: " << flush;


t.Preorder();
cout << endl;

cout << "Inorder: " << flush;


t.Inorder();
cout << endl;

cout << "Postorder: " << flush;


t.Postorder();
cout << endl;
cout << "Levelorder: " << flush;
t.Levelorder();
cout << endl;

cout << "Height: " << t.Height() << endl;

You might also like