Intro the computer science

read the slide and do the assignment lab

CSE 112 Intro to Computer Science II
CSE 112 – Lab #12 – Templates, Binary Search Trees and Operations
Using the BinaryTree.h file (shown below and posted as a text file on BB), write a program that inserts
the following numbers 12, 9, 10, 15, 18, 17 and 20 into the tree in that order.







Announce the numbers being inserted
Output the number of nodes, and then display them in order
Announce the deletion of the numbers 9 and 15 from the tree
Output the number of nodes, and then display them in order
Display the tree in postorder, and then “Binary Tree – your name”
Modify the header as needed to output the values horizontally
Extra Credit (10) – Display the tree as it exists at the end replacing the “X”s shown below with
the correct node values. Use “cout” statements and only display branches and numbers that
exist, then “Binary Tree – first initial last name” as shown below.
Submit the main program as a text file.
NOTE: Older compilers do not accept nullptr, use NULL to initialize pointers. Ref: Page 500
Binary Tree – C Simber
Grading will include meeting all of the lab requirements, adherence to programming standards,
operation and accurate output, and programming style including white space and indentation.
1
Assignments submitted after the due date will incur a grade penalty of three (3) points per day
after the first day, and will not be accepted more than one (1) week late.
CSE 112 Intro to Computer Science II
// Binary Tree Template
#ifndef BINARYTREE_H
#define BINARYTREE_H
#include
using namespace std;
template
class BinaryTree
{
public:
struct TreeNode
{
T value;
TreeNode *left;
TreeNode *right;
};
TreeNode *root;
void insert(TreeNode *&, TreeNode *&);
void destroySubTree(TreeNode *);
void deleteNode(T, TreeNode *&);
void makeDeletion(TreeNode *&);
void displayInOrder(TreeNode *);
void displayPreOrder(TreeNode *);
void displayPostOrder(TreeNode *);
int countNodes(TreeNode *&);
public:
BinaryTree() // Constructor
{ root = nullptr; }
~BinaryTree() // Destructor
{ destroySubTree(root); }
void insertNode(T);
bool searchNode(T);
void remove(T);
void displayInOrder()
{ displayInOrder(root); }
void displayPreOrder()
{ displayPreOrder(root); }
void displayPostOrder()
{ displayPostOrder(root); }
int numNodes();
};
2
Assignments submitted after the due date will incur a grade penalty of three (3) points per day
after the first day, and will not be accepted more than one (1) week late.
CSE 112 Intro to Computer Science II
//*************************************************************
// insert accepts a TreeNode pointer and a pointer to a node. The function inserts the *
// node into the tree pointed to by the TreeNode pointer. This function is called recursively. *
//*************************************************************
template
void BinaryTree::insert(TreeNode *&nodePtr, TreeNode *&newNode)
{
if (nodePtr == nullptr)
{
// Insert the node.
nodePtr = newNode;
}
else if (newNode->value < nodePtr->value)
{
// Search the left branch
insert(nodePtr->left, newNode);
}
else
{
// Search the right branch
insert(nodePtr->right, newNode);
}
}
//**********************************************************
// insertNode creates a new node to hold num as its value, *
// and passes it to the insert function.
*
//**********************************************************
template
void BinaryTree::insertNode(T num)
{
TreeNode *newNode = nullptr; // Pointer to a new node.
// Create a new node and store num in it.
newNode = new TreeNode;
newNode->value = num;
newNode->left = newNode->right = nullptr;
// Insert the node.
insert(root, newNode);
}
//***************************************************
3
Assignments submitted after the due date will incur a grade penalty of three (3) points per day
after the first day, and will not be accepted more than one (1) week late.
CSE 112 Intro to Computer Science II
// destroySubTree is called by the destructor. It *
// deletes all nodes in the tree.
*
//***************************************************
template
void BinaryTree::destroySubTree(TreeNode *nodePtr)
{
if (nodePtr->left)
{
destroySubTree(nodePtr->left);
}
if (nodePtr->right)
{
destroySubTree(nodePtr->right);
}
delete nodePtr;
}
//***************************************************
// searchNode determines if a value is present in the tree. If so, *
// the function returns true. Otherwise, it returns false. *
//***************************************************
template
bool BinaryTree::searchNode(T num)
{
bool status = false;
TreeNode *nodePtr = root;
while (nodePtr)
{
if (nodePtr->value == num)
{
status = true;
}
else if (num < nodePtr->value)
{
nodePtr = nodePtr->left;
}
else
{
nodePtr = nodePtr->right;
4
Assignments submitted after the due date will incur a grade penalty of three (3) points per day
after the first day, and will not be accepted more than one (1) week late.
CSE 112 Intro to Computer Science II
}
}
return status;
}
//**********************************************
// remove calls deleteNode to delete the
*
// node whose value member is the same as num. *
//**********************************************
template
void BinaryTree::remove(T num)
{
deleteNode(num, root);
}
//********************************************
// deleteNode deletes the node whose value *
// member is the same as num.
*
//********************************************
template
void BinaryTree::deleteNode(T num, TreeNode *&nodePtr)
{
if (num < nodePtr->value)
{
deleteNode(num, nodePtr->left);
}
else if (num > nodePtr->value)
{
deleteNode(num, nodePtr->right);
}
else
{
makeDeletion(nodePtr);
}
}
//***********************************************************
// makeDeletion takes a reference to a pointer to the node that is to be deleted. *
// The node is removed and the branches of the tree below the node are reattached.
//***********************************************************
*
template
5
Assignments submitted after the due date will incur a grade penalty of three (3) points per day
after the first day, and will not be accepted more than one (1) week late.
CSE 112 Intro to Computer Science II
void BinaryTree::makeDeletion(TreeNode *&nodePtr)
{
// Temporary pointer, used in reattaching the left subtree.
TreeNode *tempNodePtr = nullptr;
if (nodePtr == nullptr)
{
cout right == nullptr)
{
tempNodePtr = nodePtr;
nodePtr = nodePtr->left; // Reattach the left child
delete tempNodePtr;
}
else if (nodePtr->left == nullptr)
{
tempNodePtr = nodePtr;
nodePtr = nodePtr->right; // Reattach the right child
delete tempNodePtr;
}
// If the node has two children.
else
{
// Move one node the right.
tempNodePtr = nodePtr->right;
// Go to the end left node.
while (tempNodePtr->left)
{
tempNodePtr = tempNodePtr->left;
}
// Reattach the left subtree.
tempNodePtr->left = nodePtr->left;
tempNodePtr = nodePtr;
// Reattach the right subtree.
nodePtr = nodePtr->right;
delete tempNodePtr;
}
}
//****************************************************************
6
Assignments submitted after the due date will incur a grade penalty of three (3) points per day
after the first day, and will not be accepted more than one (1) week late.
CSE 112 Intro to Computer Science II
// The displayInOrder member function displays the values
*
// in the subtree pointed to by nodePtr, via inorder traversal. *
//****************************************************************
template
void BinaryTree::displayInOrder(TreeNode *nodePtr)
{
if (nodePtr)
{
displayInOrder(nodePtr->left);
cout value right);
}
}
//****************************************************************
// The displayPreOrder member function displays the values
*
// in the subtree pointed to by nodePtr, via preorder traversal. *
//****************************************************************
template
void BinaryTree::displayPreOrder(TreeNode *nodePtr)
{
if (nodePtr)
{
cout value left);
displayPreOrder(nodePtr->right);
}
}
//****************************************************************
// The displayPostOrder member function displays the values *
// in the subtree pointed to by nodePtr, via postorder traversal.*
//****************************************************************
template
void BinaryTree::displayPostOrder(TreeNode *nodePtr)
{
if (nodePtr)
{
displayPostOrder(nodePtr->left);
displayPostOrder(nodePtr->right);
cout value left) + countNodes(nodePtr->right);
}
return count;
}
#endif
8
Assignments submitted after the due date will incur a grade penalty of three (3) points per day
after the first day, and will not be accepted more than one (1) week late.
// Binary Tree Template
#ifndef BINARYTREE_H
#define BINARYTREE_H
#include
using namespace std;
template
class BinaryTree
{
public:
struct TreeNode
{
T value;
TreeNode *left;
TreeNode *right;
};
TreeNode *root;
void insert(TreeNode *&, TreeNode *&);
void destroySubTree(TreeNode *);
void deleteNode(T, TreeNode *&);
void makeDeletion(TreeNode *&);
void displayInOrder(TreeNode *);
void displayPreOrder(TreeNode *);
void displayPostOrder(TreeNode *);
int countNodes(TreeNode *&);
public:
BinaryTree() // Constructor
{ root = NULL; }
~BinaryTree() // Destructor
{ destroySubTree(root); }
void insertNode(T);
bool searchNode(T);
void remove(T);
void displayInOrder()
{ displayInOrder(root); }
void displayPreOrder()
{ displayPreOrder(root); }
void displayPostOrder()
{ displayPostOrder(root); }
int numNodes();
};
//*************************************************************
// insert accepts a TreeNode pointer and a pointer to a node. The function inserts the *
// node into the tree pointed to by the TreeNode pointer. This function is called recursively. *
//*************************************************************
template
void BinaryTree::insert(TreeNode *&nodePtr, TreeNode *&newNode)
{
if (nodePtr == NULL)
{
// Insert the node.
nodePtr = newNode;
}
else if (newNode->value < nodePtr->value)
{
// Search the left branch
insert(nodePtr->left, newNode);
}
else
{
// Search the right branch
insert(nodePtr->right, newNode);
}
}
//**********************************************************
// insertNode creates a new node to hold num as its value, *
// and passes it to the insert function. *
//**********************************************************
template
void BinaryTree::insertNode(T num)
{
TreeNode *newNode = NULL; // Pointer to a new node.
// Create a new node and store num in it.
newNode = new TreeNode;
newNode->value = num;
newNode->left = newNode->right = NULL;
// Insert the node.
insert(root, newNode);
}
//***************************************************
// destroySubTree is called by the destructor. It *
// deletes all nodes in the tree. *
//***************************************************
template
void BinaryTree::destroySubTree(TreeNode *nodePtr)
{
if (nodePtr->left)
{
destroySubTree(nodePtr->left);
}
if (nodePtr->right)
{
destroySubTree(nodePtr->right);
}
delete nodePtr;
}
//***************************************************
// searchNode determines if a value is present in the tree. If so, *
// the function returns true. Otherwise, it returns false. *
//***************************************************
template
bool BinaryTree::searchNode(T num)
{
bool status = false;
TreeNode *nodePtr = root;
while (nodePtr)
{
if (nodePtr->value == num)
{
status = true;
}
else if (num < nodePtr->value)
{
nodePtr = nodePtr->left;
}
else
{
nodePtr = nodePtr->right;
}
}
return status;
}
//**********************************************
// remove calls deleteNode to delete the *
// node whose value member is the same as num. *
//**********************************************
template
void BinaryTree::remove(T num)
{
deleteNode(num, root);
}
//********************************************
// deleteNode deletes the node whose value *
// member is the same as num. *
//********************************************
template
void BinaryTree::deleteNode(T num, TreeNode *&nodePtr)
{
if (num < nodePtr->value)
{
deleteNode(num, nodePtr->left);
}
else if (num > nodePtr->value)
{
deleteNode(num, nodePtr->right);
}
else
{
makeDeletion(nodePtr);
}
}
//***********************************************************
// makeDeletion takes a reference to a pointer to the node that is to be deleted. *
// The node is removed and the branches of the tree below the node are reattached. *
//***********************************************************
template
void BinaryTree::makeDeletion(TreeNode *&nodePtr)
{
// Temporary pointer, used in reattaching the left subtree.
TreeNode *tempNodePtr = NULL;
if (nodePtr == NULL)
{
cout right == NULL)
{
tempNodePtr = nodePtr;
nodePtr = nodePtr->left; // Reattach the left child
delete tempNodePtr;
}
else if (nodePtr->left == NULL)
{
tempNodePtr = nodePtr;
nodePtr = nodePtr->right; // Reattach the right child
delete tempNodePtr;
}
// If the node has two children.
else
{
// Move one node the right.
tempNodePtr = nodePtr->right;
// Go to the end left node.
while (tempNodePtr->left)
{
tempNodePtr = tempNodePtr->left;
}
// Reattach the left subtree.
tempNodePtr->left = nodePtr->left;
tempNodePtr = nodePtr;
// Reattach the right subtree.
nodePtr = nodePtr->right;
delete tempNodePtr;
}
}
//****************************************************************
// The displayInOrder member function displays the values *
// in the subtree pointed to by nodePtr, via inorder traversal. *
//****************************************************************
template
void BinaryTree::displayInOrder(TreeNode *nodePtr)
{
if (nodePtr)
{
displayInOrder(nodePtr->left);
cout value right);
}
}
//****************************************************************
// The displayPreOrder member function displays the values *
// in the subtree pointed to by nodePtr, via preorder traversal. *
//****************************************************************
template
void BinaryTree::displayPreOrder(TreeNode *nodePtr)
{
if (nodePtr)
{
cout value left);
displayPreOrder(nodePtr->right);
}
}
//****************************************************************
// The displayPostOrder member function displays the values *
// in the subtree pointed to by nodePtr, via postorder traversal.*
//****************************************************************
template
void BinaryTree::displayPostOrder(TreeNode *nodePtr)
{
if (nodePtr)
{
displayPostOrder(nodePtr->left);
displayPostOrder(nodePtr->right);
cout value left) + countNodes(nodePtr->right);
}
return count;
}
#endif
Chapter 21:
Binary Trees
Copyright © 2018, 2015, 2012, 2009 Pearson Education, Inc. All rights reserved.
21.1
Definition and Application of
Binary Trees
Copyright © 2018, 2015, 2012, 2009 Pearson Education, Inc. All rights reserved.
Definition and Application of
Binary Trees
Binary tree: a nonlinear linked list in which each node may
point to 0, 1, or two other nodes
Each node contains
one or more
data fields and
two pointers
null
null
null
null
null
Copyright © 2018, 2015, 2012, 2009 Pearson Education, Inc. All rights reserved.
null
Binary Tree Terminology
Tree pointer: like a head
pointer for a linked list, it
points to the first node in
the binary tree
Root node: the node at the
top of the tree
null
null
null
null
Copyright © 2018, 2015, 2012, 2009 Pearson Education, Inc. All rights reserved.
null
null
Binary Tree Terminology
Leaf nodes: nodes that
have no children
The nodes containing
7 and 43 are leaf
nodes
7
null
31
19
59
null
null
Copyright © 2018, 2015, 2012, 2009 Pearson Education, Inc. All rights reserved.
43
null
null
null
Binary Tree Terminology
Child nodes,
children: nodes
below a given node
The children of the
node containing 31
are the nodes
containing 19 and
59
31
19
7
null
59
null
null
Copyright © 2018, 2015, 2012, 2009 Pearson Education, Inc. All rights reserved.
43
null
null
null
Binary Tree Terminology
Parent node: node
above a given node
The parent of the node
containing 43 is the
node containing 59
7
null
31
19
59
null
null
Copyright © 2018, 2015, 2012, 2009 Pearson Education, Inc. All rights reserved.
43
null
null
null
Binary Tree Terminology
Subtree: the portion of
a tree from a node
down to the leaves
The nodes containing
19 and 7 are the left
subtree of the node
7
containing 31
null
31
19
59
null
null
Copyright © 2018, 2015, 2012, 2009 Pearson Education, Inc. All rights reserved.
43
null
null
null
Uses of Binary Trees
Binary search tree: data organized in a binary tree to
simplify searches
Left subtree of a node
contains data values < the data in the node 31 Right subtree of a node contains values > the data
in the node
7
null
19
59
null
null
Copyright © 2018, 2015, 2012, 2009 Pearson Education, Inc. All rights reserved.
43
null
null
null
Searching in a Binary Tree
1)
2)
Start at root node
Examine node data:
a)
b)
c)
3)
Is it desired value? Done
Else, is desired data < node data? Repeat step 2 with left subtree Else, is desired data > node
data? Repeat step 2 with
right subtree
Continue until desired
value found or a null
pointer reached
31
19
7
null
59
null
Copyright © 2018, 2015, 2012, 2009 Pearson Education, Inc. All rights reserved.
null
43
null
null
null
Searching in a Binary Tree
To locate the node containing 43,
Examine the root node (31) first
Since 43 > 31, examine the
right child of the node containing
31, (59)
Since 43 < 59, examine the left child of the node containing 59, (43) The node containing 43 has been found 7 null 31 19 59 null Copyright © 2018, 2015, 2012, 2009 Pearson Education, Inc. All rights reserved. null 43 null null null 21.2 Binary Search Tree Operations Copyright © 2018, 2015, 2012, 2009 Pearson Education, Inc. All rights reserved. Binary Search Tree Operations Create a binary search tree organize data into a binary search tree Insert a node into a binary tree put node into tree in its correct position to maintain order Find a node in a binary tree locate a node with particular data value Delete a node from a binary tree remove a node and adjust links to maintain binary tree Copyright © 2018, 2015, 2012, 2009 Pearson Education, Inc. All rights reserved. Binary Search Tree Node A node in a binary tree is like a node in a linked list, with two node pointer fields: struct TreeNode { int value; TreeNode *left; TreeNode *right; } Node structure definition Copyright © 2018, 2015, 2012, 2009 Pearson Education, Inc. All rights reserved. Creating a New Node Allocate memory for new node: newNode newNode = new TreeNode; Initialize the contents of the node: newNode->value = num;
newNode
Set the pointers to nullptr:
newNode->Left
= newNode->Right
= nullptr;
23
newNode
23
null
Copyright © 2018, 2015, 2012, 2009 Pearson Education, Inc. All rights reserved.
null
Inserting a Node in a
Binary Search Tree
1)
2)
3)
4)
If tree is empty, insert the new node as the root node
Else, compare new node against left or right child,
depending on whether data value of new node is < or >
root node
Continue comparing and choosing left or right subtree
unitl null pointer found
Set this null pointer to point to new node
Copyright © 2018, 2015, 2012, 2009 Pearson Education, Inc. All rights reserved.
Inserting a Node in a Binary Search Tree
newNode
Examine this node first –
value is < node, so go to left subtree Examine this node second – value is > node,
so go to right
subtree
7
null
23
root
null
31
19
59
null
null
43
null
null
null
Since the right subtree
is null, insert here
Copyright © 2018, 2015, 2012, 2009 Pearson Education, Inc. All rights reserved.
null
Traversing a Binary Tree
Three traversal methods:
1) Inorder:
a) Traverse left subtree of node
b) Process data in node
c) Traverse right subtree of node
2) Preorder:
a) Process data in node
b) Traverse left subtree of node
c) Traverse right subtree of node
3) Postorder:
a) Traverse left subtree of node
b) Traverse right subtree of node
c) Process data in node
Copyright © 2018, 2015, 2012, 2009 Pearson Education, Inc. All rights reserved.
Traversing a Binary Tree
TRAVERSAL NODES
METHOD
VISITED IN
ORDER
31
19
7
null
Inorder
7, 19, 31,
43, 59
Preorder
31, 19, 7,
59, 43
Postorder
7, 19, 43,
59, 31
59
null
null
43
null
null
null
Copyright © 2018, 2015, 2012, 2009 Pearson Education, Inc. All rights reserved.
Traversing a Binary Tree (after adding 23)
TRAVERSAL NODES
METHOD
VISITED IN
ORDER
Inorder
7, 19, 23,
31, 43, 59
Preorder
31, 19, 7,
23, 59, 43
Postorder
7, 23, 19,
43, 59, 31
Copyright © 2018, 2015, 2012, 2009 Pearson Education, Inc. All rights reserved.
Searching in a Binary Tree
Start at root node,
traverse the tree
looking for value
Stop when value
found or null pointer
detected
Can be implemented
as a bool function
31
19
7
null
59
null
null
43
null
null
null
Search for 43? return true
Search for 17? return false
Copyright © 2018, 2015, 2012, 2009 Pearson Education, Inc. All rights reserved.
Deleting a Node from a
Binary Tree – Leaf Node
If node to be deleted is a leaf node, replace
parent node’s pointer to it with the null pointer,
then delete the node
19
19
7
null
null
null
null
null
Deleting node with 7
– before deletion
Deleting node with 7
– after deletion
Copyright © 2018, 2015, 2012, 2009 Pearson Education, Inc. All rights reserved.
Deleting a Node from a
Binary Tree – One Child
If node to be deleted has one child node,
adjust pointers so that parent of node to be
deleted points to child of node to be deleted,
then delete the node
Copyright © 2018, 2015, 2012, 2009 Pearson Education, Inc. All rights reserved.
Deleting a Node from a
Binary Tree – One Child
31
31
19
7
null
59
null
null
43
null
Deleting node with 19
– before deletion
7
null
null
59
null
null
null
43
null
null
Deleting node with 19
– after deletion
Copyright © 2018, 2015, 2012, 2009 Pearson Education, Inc. All rights reserved.
Deleting a Node from a
Binary Tree – Two Children
If node to be deleted has left and right children,
‘Promote’ one child to take the place of the deleted
node
Locate correct position for other child in subtree of
promoted child
Convention in text: promote the right child, position left
subtree underneath
Copyright © 2018, 2015, 2012, 2009 Pearson Education, Inc. All rights reserved.
Deleting a Node from a
Binary Tree – Two Children
31
59
19
7
59
null
null
null
43
null
Deleting node with 31
– before deletion
null
43
null
null
null
19
7
null
null
null
Deleting node with 31
– after deletion
Copyright © 2018, 2015, 2012, 2009 Pearson Education, Inc. All rights reserved.