The goal of this assignment is to reinforce the tree data structure in C++. Spec

ID: 3599435 • Letter: T

Question

The goal of this assignment is to reinforce the tree data structure in C++. Specifically, the assignment is to do the following:

Construct a function that will display a binary tree by levels (each level on a separate line), using the included files (node2.h, node2.template, bintree.h, and bintree.template). If there is no node at a position in a level, then the function should display NULL. Only levels that contain at least 1 datum should be displayed.

---------------------------------------

node2.h

---------------------------------------

// FILE: node2.h (part of the namespace main_savitch_6B)

// PROVIDES: A template class for a node in a linked list, and list manipulation

// functions. The template parameter is the type of the data in each node.

// This file also defines a template class: node_iterator.

// The node_iterator is a forward iterators with two constructors:

// (1) A constructor (with a node* parameter) that attaches the iterator

// to the specified node in a linked list, and (2) a default constructor that

// creates a special iterator that marks the position that is beyond the end of a

// linked list. There is also a const_node_iterator for use with

// const node* .

// TYPEDEF for the node template class:

// Each node of the list contains a piece of data and a pointer to the

// next node. The type of the data (node::value_type) is the Item type

// from the template parameter. The type may be any of the built-in C++ classes

// (int, char, ...) or a class with a default constructor, an assignment

// operator, and a test for equality (x == y).

// NOTE:

// Many compilers require the use of the new keyword typename before using

// the expression node::value_type. Otherwise

// the compiler doesn't have enough information to realize that it is the

// name of a data type.

// CONSTRUCTOR for the node class:

// node(

// const Item& init_data = Item(),

// node* init_link = NULL

// )

// Postcondition: The node contains the specified data and link.

// NOTE: The default value for the init_data is obtained from the default

// constructor of the Item. In the ANSI/ISO standard, this notation

// is also allowed for the built-in types, providing a default value of

// zero. The init_link has a default value of NULL.

// NOTE about two versions of some functions:

// The data function returns a reference to the data field of a node and

// the link function returns a copy of the link field of a node.

// Each of these functions comes in two versions: a const version and a

// non-const version. If the function is activated by a const node, then the

// compiler choses the const version (and the return value is const).

// If the function is activated by a non-const node, then the compiler choses

// the non-const version (and the return value will be non-const).

// EXAMPLES:

// const node *c;

// c->link( ) activates the const version of link returning const node*

// c->data( ) activates the const version of data returning const Item&

// c->data( ) = 42; ... is forbidden

// node *p;

// p->link( ) activates the non-const version of link returning node*

// p->data( ) activates the non-const version of data returning Item&

// p->data( ) = 42; ... actually changes the data in p's node

// MEMBER FUNCTIONS for the node class:

// const Item& data( ) const <----- const version

// and

// Item& data( ) <----------------- non-const version

// See the note (above) about the const version and non-const versions:

// Postcondition: The return value is a reference to the data from this node.

// const node* link( ) const <----- const version

// and

// node* link( ) <----------------- non-const version

// See the note (above) about the const version and non-const versions:

// Postcondition: The return value is the link from this node.

// void set_data(const Item& new_data)

// Postcondition: The node now contains the specified new data.

// void set_link(node* new_link)

// Postcondition: The node now contains the specified new link.

// FUNCTIONS in the linked list toolkit:

// template

// void list_clear(node*& head_ptr)

// Precondition: head_ptr is the head pointer of a linked list.

// Postcondition: All nodes of the list have been returned to the heap,

// and the head_ptr is now NULL.

// template

// void list_copy

// (const node* source_ptr, node*& head_ptr, node*& tail_ptr)

// Precondition: source_ptr is the head pointer of a linked list.

// Postcondition: head_ptr and tail_ptr are the head and tail pointers for

// a new list that contains the same items as the list pointed to by

// source_ptr. The original list is unaltered.

// template

// void list_head_insert(node*& head_ptr, const Item& entry)

// Precondition: head_ptr is the head pointer of a linked list.

// Postcondition: A new node containing the given entry has been added at

// the head of the linked list; head_ptr now points to the head of the new,

// longer linked list.

// template

// void list_head_remove(node*& head_ptr)

// Precondition: head_ptr is the head pointer of a linked list, with at

// least one node.

// Postcondition: The head node has been removed and returned to the heap;

// head_ptr is now the head pointer of the new, shorter linked list.

// template

// void list_insert(node* previous_ptr, const Item& entry)

// Precondition: previous_ptr points to a node in a linked list.

// Postcondition: A new node containing the given entry has been added

// after the node that previous_ptr points to.

// template

// size_t list_length(const node* head_ptr)

// Precondition: head_ptr is the head pointer of a linked list.

// Postcondition: The value returned is the number of nodes in the linked

// list.

// template

// NodePtr list_locate(NodePtr head_ptr, SizeType position)

// The NodePtr may be either node* or const node*

// Precondition: head_ptr is the head pointer of a linked list, and

// position > 0.

// Postcondition: The return value is a pointer that points to the node at

// the specified position in the list. (The head node is position 1, the

// next node is position 2, and so on). If there is no such position, then

// the null pointer is returned.

// template

// void list_remove(node* previous_ptr)

// Precondition: previous_ptr points to a node in a linked list, and this

// is not the tail node of the list.

// Postcondition: The node after previous_ptr has been removed from the

// linked list.

// template

// NodePtr list_search

// (NodePtr head_ptr, const Item& target)

// The NodePtr may be either node* or const node*

// Precondition: head_ptr is the head pointer of a linked list.

// Postcondition: The return value is a pointer that points to the first

// node containing the specified target in its data member. If there is no

// such node, the null pointer is returned.

// DYNAMIC MEMORY usage by the toolkit:

// If there is insufficient dynamic memory, then the following functions throw

// bad_alloc: the constructor, list_head_insert, list_insert, list_copy.

#ifndef MAIN_SAVITCH_NODE2_H

#define MAIN_SAVITCH_NODE2_H

#include // Provides NULL and size_t

#include // Provides iterator and forward_iterator_tag

namespace main_savitch_6B

{

template

class node

{

public:

// TYPEDEF

typedef Item value_type;

// CONSTRUCTOR

node(const Item& init_data=Item( ), node* init_link=NULL)

{ data_field = init_data; link_field = init_link; }

// MODIFICATION MEMBER FUNCTIONS

Item& data( ) { return data_field; }

node* link( ) { return link_field; }

void set_data(const Item& new_data) { data_field = new_data; }

void set_link(node* new_link) { link_field = new_link; }

// CONST MEMBER FUNCTIONS

const Item& data( ) const { return data_field; }

const node* link( ) const { return link_field; }

private:

Item data_field;

node *link_field;

};

// FUNCTIONS to manipulate a linked list:

template

void list_clear(node*& head_ptr);

template

void list_copy

(const node* source_ptr, node*& head_ptr, node*& tail_ptr);

template

void list_head_insert(node*& head_ptr, const Item& entry);

template

void list_head_remove(node*& head_ptr);

template

void list_insert(node* previous_ptr, const Item& entry);

template

std::size_t list_length(const node* head_ptr);

template

NodePtr list_locate(NodePtr head_ptr, SizeType position);

template

void list_remove(node* previous_ptr);

template

NodePtr list_search(NodePtr head_ptr, const Item& target);

// FORWARD ITERATORS to step through the nodes of a linked list

// A node_iterator of can change the underlying linked list through the

// * operator, so it may not be used with a const node. The

// node_const_iterator cannot change the underlying linked list

// through the * operator, so it may be used with a const node.

// WARNING:

// This classes use std::iterator as its base class;

// Older compilers that do not support the std::iterator class can

// delete everything after the word iterator in the second line:

template

class node_iterator

: public std::iterator

{

public:

node_iterator(node* initial = NULL)

{ current = initial; }

Item& operator *( ) const

{ return current->data( ); }

node_iterator& operator ++( ) // Prefix ++

{

current = current->link( );

return *this;

}

node_iterator operator ++(int) // Postfix ++

{

node_iterator original(current);

current = current->link( );

return original;

}

bool operator ==(const node_iterator other) const

{ return current == other.current; }

bool operator !=(const node_iterator other) const

{ return current != other.current; }

private:

node* current;

};

template

class const_node_iterator

: public std::iterator

{

public:

const_node_iterator(const node* initial = NULL)

{ current = initial; }

const Item& operator *( ) const

{ return current->data( ); }

const_node_iterator& operator ++( ) // Prefix ++

{

current = current->link( );

return *this;

}

const_node_iterator operator ++(int) // Postfix ++

{

const_node_iterator original(current);

current = current->link( );

return original;

}

bool operator ==(const const_node_iterator other) const

{ return current == other.current; }

bool operator !=(const const_node_iterator other) const

{ return current != other.current; }

private:

const node* current;

};

}

#include "node2.template"

#endif

---------------------------------------

node2.template

---------------------------------------

bintree.h

---------------------------------------

// FILE: bintree.h (part of the namespace main_savitch_10)

// PROVIDES: A template class for a node in a binary tree and functions for

// manipulating binary trees. The template parameter is the type of data in

// each node.

// TYPEDEF for the binary_tree_node template class:

// Each node of the tree contains a piece of data and pointers to its

// children. The type of the data (binary_tree_node::value_type) is

// the Item type from the template parameter. The type may be any of the C++

// built-in types (int, char, etc.), or a class with a default constructor,

// and an assignment operator.

// CONSTRUCTOR for the binary_tree_node class:

// binary_tree_node(

// const item& init_data = Item( ),

// binary_tree_node* init_left = NULL,

// binary_tree_node* init_right = NULL

// )

// Postcondition: The new node has its data equal to init_data,

// and it's child pointers equal to init_left and init_right.

// MEMBER FUNCTIONS for the binary_tree_node class:

// const item& data( ) const <----- const version

// and

// Item& data( ) <----- non-const version

// Postcondition: The return value is a reference to the data from

// this binary_tree_node.

// const binary_tree_node* left( ) const <----- const version

// and

// binary_tree_node* left( ) <----- non-const version

// and

// const binary_tree_node* right( ) const <----- const version

// and

// binary_tree_node* right( ) <----- non-const version

// Postcondition: The return value is a pointer to the left or right child

// (which will be NULL if there is no child).

// void set_data(const Item& new_data)

// Postcondition: The binary_tree_node now contains the specified new data.

// void set_left(binary_tree_node* new_link)

// and

// void set_right(binary_tree_node* new_link)

// Postcondition: The binary_tree_node now contains the specified new link

// to a child.

// bool is_leaf( )

// Postcondition: The return value is true if the node is a leaf;

// otherwise the return value is false.

// NON-MEMBER FUNCTIONS to maniplulate binary tree nodes:

// tempate

// void inorder(Process f, BTNode* node_ptr)

// Precondition: node_ptr is a pointer to a node in a binary tree (or

// node_ptr may be NULL to indicate the empty tree).

// Postcondition: If node_ptr is non-NULL, then the function f has been

// applied to the contents of *node_ptr and all of its descendants, using

// an in-order traversal.

// Note: BTNode may be a binary_tree_node or a const binary tree node.

// Process is the type of a function f that may be called with a single

// Item argument (using the Item type from the node).

// tempate

// void postorder(Process f, BTNode* node_ptr)

// Same as the in-order function, except with a post-order traversal.

// tempate

// void preorder(Process f, BTNode* node_ptr)

// Same as the in-order function, except with a pre-order traversal.

// template

// void print(const binary_tree_node* node_ptr, SizeType depth)

// Precondition: node_ptr is a pointer to a node in a binary tree (or

// node_ptr may be NULL to indicate the empty tree). If the pointer is

// not NULL, then depth is the depth of the node pointed to by node_ptr.

// Postcondition: If node_ptr is non-NULL, then the contents of *node_ptr

// and all its descendants have been written to cout with the << operator,

// using a backward in-order traversal. Each node is indented four times

// its depth.

// template

// void tree_clear(binary_tree_node*& root_ptr)

// Precondition: root_ptr is the root pointer of a binary tree (which may

// be NULL for the empty tree).

// Postcondition: All nodes at the root or below have been returned to the

// heap, and root_ptr has been set to NULL.

// template

// binary_tree_node* tree_copy(const binary_tree_node* root_ptr)

// Precondition: root_ptr is the root pointer of a binary tree (which may

// be NULL for the empty tree).

// Postcondition: A copy of the binary tree has been made, and the return

// value is a pointer to the root of this copy.

// template

// size_t tree_size(const binary_tree_node* node_ptr)

// Precondition: node_ptr is a pointer to a node in a binary tree (or

// node_ptr may be NULL to indicate the empty tree).

// Postcondition: The return value is the number of nodes in the tree.

#ifndef BINTREE_H

#define BINTREE_H

#include // Provides NULL and size_t

namespace main_savitch_10

{

template

class binary_tree_node

{

public:

// TYPEDEF

typedef Item value_type;

// CONSTRUCTOR

binary_tree_node(

const Item& init_data = Item( ),

binary_tree_node* init_left = NULL,

binary_tree_node* init_right = NULL

)

{

data_field = init_data;

left_field = init_left;

right_field = init_right;

}

// MODIFICATION MEMBER FUNCTIONS

Item& data( ) { return data_field; }

binary_tree_node* left( ) { return left_field; }

binary_tree_node* right( ) { return right_field; }

void set_data(const Item& new_data) { data_field = new_data; }

void set_left(binary_tree_node* new_left) { left_field = new_left; }

void set_right(binary_tree_node* new_right) { right_field = new_right; }

// CONST MEMBER FUNCTIONS

const Item& data( ) const { return data_field; }

const binary_tree_node* left( ) const { return left_field; }

const binary_tree_node* right( ) const { return right_field; }

bool is_leaf( ) const

{ return (left_field == NULL) && (right_field == NULL); }

private:

Item data_field;

binary_tree_node *left_field;

binary_tree_node *right_field;

};

// NON-MEMBER FUNCTIONS for the binary_tree_node:

template

void inorder(Process f, BTNode* node_ptr);

template

void preorder(Process f, BTNode* node_ptr);

template

void postorder(Process f, BTNode* node_ptr);

template

void print(binary_tree_node* node_ptr, SizeType depth);

template

void tree_clear(binary_tree_node*& root_ptr);

template

binary_tree_node* tree_copy(const binary_tree_node* root_ptr);

template

std::size_t tree_size(const binary_tree_node* node_ptr);

}

#include "bintree.template"

#endif

---------------------------------------

bintree.template

---------------------------------------

Explanation / Answer

Algorithm to print the binary tree level by level is geven below:

For each node, first the node is visited and then it’s child nodes are put in a FIFO queue.

printLevelorder(tree)

1) Create an empty queue q

2) temp_node = root /*start from root*/

3) Loop while temp_node is not NULL

a) print temp_node->data.

b) Enqueue temp_node’s children (first left then right children) to q

c) Dequeue a node from q and assign it’s value to temp_node

Following is the C++ code as required:

template <class Item>

void print_LevelOrder(binary_tree_node* root)

{

// Base Case

if (root == NULL) return;

// Create an empty queue for level order tarversal

queue<Node *> q;

// Enqueue Root and initialize height

q.push(root);

q.push(NULL); //For end of level

while (q.empty() == false)

{

// Print front of queue and remove it from queue

Node *node = q.front();

if (node == NULL)

{ cout<<endl;

q.push(NULL);

}

else

{

cout << node->data() << " ";

}

q.pop();

/* Enqueue left child */

if (node->left() != NULL)

q.push(node->left();

/*Enqueue right child */

if (node->right() != NULL)

q.push(node->right();

}

Navigate

The goal of this assignment is to reinforce the contain class concepts in C++. S

The goal of this assignment is to reinforce the tree data structure in C++. Spec

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

The goal of this assignment is to reinforce the tree data structure in C++. Spec

Question

Explanation / Answer

Related Questions

Navigate