C++ code

code from assignment 7

-----------------------Code--------------------------

#include

using namespace std;

struct item{

int id;

int value;

string name;

static int currId;

item(){

}

item(int value){

this->value = value;

this->id = ++currId;

}

};

int item::currId = -1;

struct Node{

Node* parent;

Node* leftchild;

Node* rightchild;

item* it;

Node(int value){

it = new item(value);

}

};

struct arrayBinaryTree{

item** A; //pointer to array starting index

int size = 3;

int currInd = 0;

arrayBinaryTree(){

A = (item**)malloc(sizeof(item*)*size);

for(int i=0;i

A[i] = new item();

A[i]->id = -1;

}

}

// doubles the size of array

void increaseSize(){

int i = size;

size += size+1;

A = (item**)realloc(A,sizeof(item*)*size);

for(;i

A[i] = new item();

A[i]->id = -1;

}

}

void insertNode(int value){

// check if array is already full

if(currInd==size) increaseSize();

A[currInd++] = new item(value);

}

// Inorder(0) will start in order traversal

// from head which is at index 0

void Inorder(int i){

// Check if i is valid index and is not empty

if(i>=size || A[i]->id==-1) return;

int left = 2*i+1;

int right = left+1;

Inorder(left);

cout value

Inorder(right);

}

// Preorder(0) will start pre order traversal

// from head which is at index 0

void Preorder(int i){

// Check if i is valid index and is not empty

if(i>=size || A[i]->id==-1) return;

int left = 2*i+1;

int right = left+1;

cout value

Preorder(left);

Preorder(right);

}

// Postorder(0) will start post order traversal

// from head which is at index 0

void Postorder(int i){

// Check if i is valid index and is not empty

if(i>=size || A[i]->id==-1) return;

int left = 2*i+1;

int right = left+1;

Postorder(left);

Postorder(right);

cout value

}

// recursive implementation of bfs which takes in

// leftmost and rightmost index as parameter

// called as bfs(0,0)

void bfs(int l, int r){

// print out all the valid values in current level

for(int i=l;i

if(A[i]->id!=-1)

cout value

}

// get indices of leftmost and rightmost elements

// in the next level

int left = 2*l+1;

int right = 2*r+2;

if(left>=size) return;

// recursively call bfs on new left and right indexes

bfs(left,right);

}

// print out all traversals of binary tree

void traversals(){

cout

Inorder(0);

cout

cout

Preorder(0);

cout

cout

Postorder(0);

cout

cout

bfs(0,0);

cout

}

};

int main(){

// initialize new binary tree

arrayBinaryTree arrB;

int in;

// read data till it is available

// Ctrl+D to mark end of input data

while(cin >> in)

arrB.insertNode(in);

// print out all traversals of binary tree

arrB.traversals();

}

In this assignment you will use the Binary Tree Data structures you created in Assignment 7 in order to construct a binary tree when you are given the Inorder and Postorder traversals for the tree. In comparison, in assignment 7 you used the level order traversal to build the tree. Here you must only use the inorder and postorder traversals. As you know, you need both of them as only the inorder traversal is not enough. Input will be given in the form of two lines, the first representing inorder, and the second representing the post order. Again size is not given so figure out a way to read it in properly Once you have completed your tree generation. Then do inorder(Left, Root, Right), preorder(Root, Left, Right), postorder(Left, Right, Root), and Breadth First/ Level Order Traversals for each of the 2 data structures. Obviously the inorder and postorder should match the input but the way we'll truly know if it worked is when you print the level order. So by printing these out as you did in assignment 4 we can easily check if our algorithm works Notes Comment your source code appropriately Make sure you name your program file in accordance with the syllabus stipulations Test your program by running with different input to make sure the output is correct. Test and execute your program by using data-in by Linux input redirection. If your executable code is Ast# and your data file is named data# execute as: Ast# data# Your input should consist of items to insert into the binary tree data structures. Put those integers into an integer field and insert (don't try to sort them). Don't count the number of items when inserting. Just insert and have your array grow as needed (and start it small with maybe size 3) this will help you see time complexity differences. Your output should be the three traversals separating each number by a space Sample Input: 28 2 4 5 1 80 10 21 11 0 28 4 2 1 80 5 21 0 11 10 Visual Aid Sample output: Inorder: 28 2 4 5180 10 21 11 0 Preorder: 10 5 2 28 4 80 1 11 21 0 Postorder: 28 4 2 1 80 5 21 0 11 10 Breadth First/Level Order: 10 5 11 2 80 21 0 28 4 1 2 80 21 0 28 4 1