Notes: Operative Systems – Part 1

(Operative Systems – Part 2) Next >

NOTIFICATION: These notes are published for educational purposes. Using these notes is under your own responsibility and risk. These notes are given ‘as is’. I do not take responsibilities for how you use them.

PDF Content:

  • Software and Hardware structure
  • Application Binary Interface (ABI)
  • Application Programming Interface (API)
  • Memory hierarchy
  • Hard drives
  • Interrupt processing
  • What is an Operating System (OS)
  • CPU privilege levels
  • Process
  • Memory layout of a typical process
  • Multiple processes sharing main memory
  • Process creation
  • Process hierarchy tree
  • Exec(), wait(), fork(), waitpid(), sleep(), and exit() functions
  • Orphan process
  • Zombie process
  • Possible process states
  • Kernel-level data structure
  • Process management
  • Memory management
  • File management
  • System call
  • Inter-process Communication (IPC)
  • Semaphores, signals, shared memory, sockets, pipes
  • Parent-child communication using pipes
  • read() and write() functions
  • Error handling
  • Handling signals
  • SigChild
  • CPU scheduling
  • Process life-cycle
  • CPU-bound process
  • I/O-bound process

Operative_Systems_1

 

(Operative Systems – Part 2) Next >

Share

Example: Binary Search Tree (BST) as Template

Example of Binary Search Tree (BST) as template by using vectors, iterators, and time STL.

NOTIFICATION: These examples are provided for educational purposes. Using this code is under your own responsibility and risk. The code is given ‘as is’. I do not take responsibilities of how they are used.

Please notice that as an example, the first tree will have all the nodes to the left, the the second tree will have all the nodes to the right, and the third tree will be balance.

Since the second tree have to check first to the left and then to the right it will take more time than the first tree. Also since the third tree is balance it will find faster the values than the second tree

BSTree.cc:

#ifndef BST_CC
#define BST_CC

#include <iostream>

using namespace std;

// Forward declaration of class BST
// By fowarding the declaration, the class BST
// can access to the private data members of BSTNode
// helping to maintain the concept of encapsulation
template <typename T> class BST;

/**
 * BSTNode
 * @description:
 */
template <typename T>
class BSTNode {

	// This is needed to grant class BST access
	// to the private members of BSTNode
	// and help to maintaining the concept of encapsulation
	friend class BST<T>;

	private:
		BSTNode<T>* pLeft;
		T data;
		BSTNode<T>* pRight;

	public:

	//Default Constructor
	BSTNode(void);

	//Constructor
	BSTNode(const T& newData);

	// **** Get Methods ****

	T getData() const;

	// **** Set Methods ****

	void setData(const T& newData);

	//Destructor
	~BSTNode(void);

};

//////////////////////////////////////////////////////////////////

/**
 * BST
 * @description:
 */
template <typename T>
class BST {

	private:	

	int numberOfNodes;

	BSTNode<T> *pRoot;

	T insertNode(BSTNode<T> **pBSTNode,
			     const T& newData);

	T findNode(BSTNode<T> **pBSTNode,
		  	   const T& searchData);

	void displayPreOrderTraversal(BSTNode<T> *pBSTNode) const;

	void displayInOrderTraversal(BSTNode<T> *pBSTNode) const;

	void displayPostOrderTraversal(BSTNode<T> *pBSTNode) const;

	void removeAll(BSTNode<T> *pBSTNode) const;

	public:

	//Default Constructor
	BST(void);

	//Constructor
	BST(const T& newData);

	// **** Get Methods ****

	// **** Set Methods ****

	// **** Methods ****
	T insert(const T& newData);

	T find(const T& searchData);

	int size(void);

	void displayPreOrder(void) const;

	void displayInOrder(void) const;

	void displayPostOrder(void) const;

	//Destructor
	~BST(void);

};

//*****************************************************************************
//**** BSTNODE METHODS ****
//*****************************************************************************

///////////////////////////////////////////////////////////////////////////////
//**** BSTNODE PRIVATE METHODS ****
///////////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////////
//**** BSTNODE PUBLIC METHODS ****
///////////////////////////////////////////////////////////////////////////////

template <typename T>
BSTNode<T>::BSTNode(void){
	//cout << endl << '[Default BSTNode]' << endl;
}

template <typename T>
BSTNode<T>::BSTNode(const T& newData):
					  pLeft(NULL),
					  data(newData),
					  pRight(NULL){
//	cout << endl << '[BSTNode]' << endl;
}

// **** Get Methods ****

/**
 *
 */
template <typename T>
T BSTNode<T>::getData() const{
	return data;
}

// **** Set Methods ****

template <typename T>
void BSTNode<T>::setData(const T& newData){
	data = newData;
}

template <typename T>
BSTNode<T>::~BSTNode(void){
//	cout << endl << '[~BSTNode(X)]' << endl;
}

//*****************************************************************************
//**** BST METHODS ****
//*****************************************************************************

///////////////////////////////////////////////////////////////////////////////
//**** BST PRIVATE METHODS ****
///////////////////////////////////////////////////////////////////////////////

/**
 *
 */
template <typename T>
T BST<T>::insertNode(BSTNode<T> **pBSTNode,
			 		 const T& newData){

	// If subBST is empty then
	// create new BSTNode for the value
	if (*pBSTNode == NULL){

		*pBSTNode = new BSTNode<T>(newData);

		numberOfNodes++;

		return newData;

	}else{

		// If the data is not duplicated
		if (newData != (*pBSTNode)->data){

			// if newData is less than the current node's data
			// then insert a left BSTNode with newData
			// else insert a right BSTNode with newData
			if (newData < (*pBSTNode)->data ){

				insertNode( &( ( *pBSTNode) -> pLeft), newData);		

			}else{

				insertNode( &( ( *pBSTNode) -> pRight), newData);		

			}
		}else{

			T rtnT;

			return rtnT;
		}

	}
}

/**
 *
 */
template <typename T>
T BST<T>::findNode(BSTNode<T> **pBSTNode,
	  	   		   const T& searchData){

	T rtnT;

	// If subBST is empty
	if (*pBSTNode == NULL){

		// Object not found 

		return rtnT;

	}else{

		// If the data is not found
		// Keep searching
		if (searchData != (*pBSTNode)->data){

			// if newData is less than the current node's data
			// then insert a left BSTNode with newData
			// else insert a right BSTNode with newData
			if (searchData < (*pBSTNode)->data ){

				rtnT = findNode( &( ( *pBSTNode) -> pLeft), searchData);		

Just to let you know			}else{

				rtnT = findNode( &( ( *pBSTNode) -> pRight), searchData);		

			}

		}else{

			rtnT = (*pBSTNode)->data;
		}

	}	

	return rtnT;
}

/**
 *
 */
template <typename T>
void BST<T>:GrinisplayPreOrderTraversal(BSTNode<T> *pBSTNode) const{

	if (pBSTNode != NULL){

		// Process Node
		cout << pBSTNode->data << ' ';

		// Traverse left subBST
		displayPreOrderTraversal(pBSTNode->pLeft);

		// Traverse right subBST
		displayPreOrderTraversal(pBSTNode->pRight);

	}
}

/**
 *
 */
template <typename T>
void BST<T>:GrinisplayInOrderTraversal(BSTNode<T> *pBSTNode) const{

	if (pBSTNode != NULL){

		// Traverse left subBST
		displayInOrderTraversal( pBSTNode->pLeft);

		// Process Node
		cout << pBSTNode->data << ' ';

		// Traverse right subBST
		displayInOrderTraversal( pBSTNode->pRight);

	}

}

/**
 *
 */
template <typename T>
void BST<T>:GrinisplayPostOrderTraversal(BSTNode<T> *pBSTNode) const{

	if (pBSTNode != NULL){

		// Traverse left subBST
		displayPostOrderTraversal(pBSTNode->pLeft);

		// Traverse right subBST
		displayPostOrderTraversal(pBSTNode->pRight);

		// Process Node
		cout << pBSTNode->data << ' ';

	}

}

/**
 *
 */
template <typename T>
void BST<T>::removeAll(BSTNode<T> *pBSTNode) const{

	if (pBSTNode != NULL){

		// Traverse left subBST
		removeAll(pBSTNode->pLeft);

		// Traverse right subBST
		removeAll(pBSTNode->pRight);

		delete pBSTNode;

	}

}

///////////////////////////////////////////////////////////////////////////////
//**** BST PUBLIC METHODS ****
///////////////////////////////////////////////////////////////////////////////

/**
 *
 */
template <typename T>
BST<T>::BST(void){
	//cout << endl << '[Default BST]' << endl;
	pRoot = NULL;
	numberOfNodes = 0;
}

/**
 *
 */
template <typename T>
BST<T>::BST(const T& newData){
	//cout << endl << '[BST]' << endl;
	numberOfNodes = 0;
}

// **** Get Methods ****

// **** Set Methods ****

// **** Methods ****

/**
 *
 */
template <typename T>
T BST<T>::insert(const T& newData){
	return insertNode( &pRoot, newData);
}

/**
 *
 */
template <typename T>
T BST<T>::find(const T& searchData){

	//cout << endl << '[find : ' << searchData << ']' << endl;

	return findNode( &pRoot, searchData);
}

/**
 *
 */
template <typename T>
int BST<T>::size(void){
	return numberOfNodes;
}

/**
 *
 */
template <typename T>
void BST<T>:GrinisplayPreOrder(void) const{
	displayPreOrderTraversal( pRoot );
}

/**
 *
 */
template <typename T>
void BST<T>:GrinisplayInOrder(void) const{
	displayInOrderTraversal( pRoot );
}

/**
 *
 */
template <typename T>
void BST<T>:GrinisplayPostOrder(void) const{
	displayPostOrderTraversal( pRoot );
}

/**
 *
 */
template <typename T>
BST<T>::~BST(void){

	cout << endl << '[~BST(X)]' << endl;

//	removeAll(pRoot);

}

#endif

main.cpp:

#include <iostream>
#include <cstdlib>
#include <time.h>
#include <sys/time.h>
#include <vector>
#include <algorithm>
#include 'BSTree.cc'

const int MAX_NUMBERS = 10000;

int main(int argc, char *argv[]){

	cout << endl << '{main}' << endl;

	vector<int> numbers;
	vector<int> reverseNumbers;
	vector<int> randomNumbers;

	BST<int> tree;
	BST<int> reverseTree;
	BST<int> randomTree;

	//Declare at top of main...

	struct timeval initialSimTime, postSimTime;

	double totalSimTime;

	int findMod = 10000;
	int NTimes = 5000;

	cout << 'Create Numbers...' << endl;

	// Insert the first 10,000 odd numbers, in order, into it.
	for (int i = 1; i < MAX_NUMBERS; i += 2)
			reverseNumbers.push_back(i);

	numbers = reverseNumbers;

	reverse(numbers.begin(), numbers.end());

	randomNumbers = numbers;

	random_shuffle(randomNumbers.begin(), randomNumbers.end());

	while(!numbers.empty()){
		tree.insert(numbers.back());
		numbers.pop_back();
	}

	while(!reverseNumbers.empty()){
		reverseTree.insert(reverseNumbers.back());
		reverseNumbers.pop_back();
	}

	while(!randomNumbers.empty()){
		randomTree.insert(randomNumbers.back());
		randomNumbers.pop_back();
	}

	cout << 'Search...' << endl;

///////////////////////////////////////////////////////////////////////

	// Place before the thing you want to time

	gettimeofday(&initialSimTime, NULL);

	cout << endl << 'Values found: ';

	for (int i = 1, j = 0; i < MAX_NUMBERS && j < NTimes; i += 2)
		if (i % findMod)
			if (tree.find(i) == i){
				cout << i << ' ';
				j++;
			}

	cout << endl;

	//Place after the thing you want to time

	gettimeofday(&postSimTime, NULL);

	totalSimTime = (double)(
				   (double)(postSimTime.tv_sec - initialSimTime.tv_sec) * 1000000 +
				   (double)(postSimTime.tv_usec - initialSimTime.tv_usec) ) /
				   (double)1000000;

	//Report how long it takes your program to run each call to that function
	//Output the time it took to do the stuff you wanted to time
	cout << 'Simulation took '<< totalSimTime << ' seconds' << endl << endl;

////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////

	// Place before the thing you want to time

	gettimeofday(&initialSimTime, NULL);

	cout << endl << 'Values found: ';

	for (int i = 1, j = 0; i < MAX_NUMBERS && j < NTimes; i += 2)
		if (i % findMod)
			if (reverseTree.find(i) == i){
				cout << i << ' ';
				j++;
			}

	cout << endl;

	//Place after the thing you want to time

	gettimeofday(&postSimTime, NULL);

	totalSimTime = (double)(
				   (double)(postSimTime.tv_sec - initialSimTime.tv_sec) * 1000000 +
				   (double)(postSimTime.tv_usec - initialSimTime.tv_usec) ) /
				   (double)1000000;

	//Report how long it takes your program to run each call to that function
	//Output the time it took to do the stuff you wanted to time
	cout << '(Reverse) Simulation took '
	     << totalSimTime << ' seconds' << endl << endl;

////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////

	// Place before the thing you want to time

	gettimeofday(&initialSimTime, NULL);

	cout << endl << 'Values found: ';

	for (int i = 1, j = 0; i < MAX_NUMBERS && j < NTimes; i += 2)
		if (i % findMod)
			if (tree.find(i) == i){
				cout << i << ' ';
				j++;
			}

	cout << endl;

	//Place after the thing you want to time

	gettimeofday(&postSimTime, NULL);

	totalSimTime = (double)(
				   (double)(postSimTime.tv_sec - initialSimTime.tv_sec) * 1000000 +
				   (double)(postSimTime.tv_usec - initialSimTime.tv_usec) ) /
				   (double)1000000;

	//Report how long it takes your program to run each call to that function
	//Output the time it took to do the stuff you wanted to time
	cout << '(Random) Simulation took '
	 	 << totalSimTime << ' seconds' << endl << endl;

////////////////////////////////////////////////////////////////////////

/*
	// Search for the first 20 multiples of 1,000
	for (int i = 0; i <= NTimes; i++)
		if (i % findMod == 0)
			if (tree.find(i) == i)
				cout << 'Value ' << i << ' Found!' << endl;

	//Report how long it takes your program to run each call to that function
	//Output the time it took to do the stuff you wanted to time
	cout << 'Simulation took '<< totalSimTime << ' seconds' << endl;

	// Start over with a new BST and insert the same odd numbers,
	// but in reverse order.
	// Again, search for the first 20 multiples of 1,000 and
	// report how long each takes	

	// Insert the first 10,000 odd numbers, in order, into it.
	for (int i = MAX_NUMBERS; i >= 0; i--)
		if (i % 2 != 0)
			reverseTree.insert(i);

	findMod = 1000;
	NTimes = 20;

	// Place before the thing you want to time

	gettimeofday(&initialSimTime, NULL);

	// Search for the first 20 multiples of 1,000
	for (int i = 0; i <= NTimes; i++)
		if (i % findMod)
			if (reverseTree.find(i) == i)
				cout << 'Value ' << i << ' Found!' << endl;

	//Place after the thing you want to time

	gettimeofday(&postSimTime, NULL);

	totalSimTime = (double)(
				   (double)(postSimTime.tv_sec - initialSimTime.tv_sec) * 1000000 +
				   (double)(postSimTime.tv_usec - initialSimTime.tv_usec) ) /
				   (double)1000000;

	//Report how long it takes your program to run each call to that function
	//Output the time it took to do the stuff you wanted to time
	cout << 'Simulation (Reverse) took '<< totalSimTime << ' seconds' << endl;

	// Insert the first 10,000 odd integers in random order into,
	// yet another BST, and run the same test.

	// Insert the first 10,000 odd numbers, in order, into it.

	int i;
	srand(time(NULL));

	bool bMatch[MAX_NUMBERS];

	for (int i = 0; i < MAX_NUMBERS; i++)
		bMatch[i] = false;

	int max = MAX_NUMBERS;
	int min = 0;

	int counter = 0;
	while(randomTree.size() < MAX_NUMBERS){

		i = rand() % (max - 1) + min;

		if ((max - 1) == i)
			max--;

		if ((min + 1) == i)
			min++;

		if (i >= max)
			i -= min;	

		for (int j = 0; j < MAX_NUMBERS; j++)
			cout << ((bMatch[i])? 1: 0);

		if ( i % 2 != 0 && !bMatch[i]){
			bMatch[i] = true;
			cout << ' ' << i;
			randomTree.insert(i);
		}
		cout << endl;

	}

	cout << endl << 'SIZE: ' << randomTree.size() << endl;

	findMod = 1000;
	NTimes = 20;

	// Place before the thing you want to time

	gettimeofday(&initialSimTime, NULL);

	// Search for the first 20 multiples of 1,000
	for (int i = 0; i <= NTimes; i++)
		if (i % findMod)
			if (reverseTree.find(i) == i)
				cout << 'Value ' << i << ' Found!' << endl;

	//Place after the thing you want to time

	gettimeofday(&postSimTime, NULL);

	totalSimTime = (double)(
				   (double)(postSimTime.tv_sec - initialSimTime.tv_sec) * 1000000 +
				   (double)(postSimTime.tv_usec - initialSimTime.tv_usec) ) /
				   (double)1000000;

	//Report how long it takes your program to run each call to that function
	//Output the time it took to do the stuff you wanted to time
	cout << 'Simulation (Random) took '<< totalSimTime << ' seconds' << endl;
*/

	return 0;
}

If you encounter any problems or errors, please let me know by providing an example of the code, input, output, and an explanation. Thanks.

Share

Simple Tree in VC++

Simple Tree in Visual C++

This code was compiled and tested on a Windows.

NOTIFICATION: These examples are provided for educational purposes. Using this code is under your own responsibility and risk. The code is given ‘as is’. I do not take responsibilities of how they are used.

mainTree.cpp:

#include 'standard.h'
#include 'tree.h'

using namespace std;

//Print the divider to the specified file
void PrintDivider ( ofstream& fout,
				    char symbol,
					int numOfSymbols,
					int section );

//Print the count to the specified file
void PrintCount ( ofstream& fout,
				  int count );

int main(void)
{
	//declare the files
	ifstream fin;
	ofstream fout;

	//Set the task number to -1
	int section = -1;

	//Open the files
	fin.open('tree.txt');
	fout.open('treeOut.txt');

	//Create an instance of the class
	TreeClass tree;

	//Declare variables
	int numOfNodesInTree;

	//print empty tree message
	tree.PrintTree ( fout );
	PrintDivider ( fout,
		           '*',
				   63,
				   section++);

	//Insert values from the input file
	tree.CreateATree ( fin );

	//Print the tree nodes on one line
	tree.PrintTree ( fout );
	PrintDivider ( fout,
		           '*',
				   63,
				   section++);

	//Calculate the number of nodes in the tree
	numOfNodesInTree = tree.CountNodesInTree();

	//Print the count
	PrintCount ( fout,
		         numOfNodesInTree );
	fout << endl;

	//Close the files
	fin.close();
	fout.close();

	return 0;
}

//Print the divider to the specified file
void PrintDivider ( ofstream& fout,
				    char symbol,
					int numOfSymbols,
					int section )
{
	fout << endl << endl;
	fout << '#' << setw(2)<< section << BLANK;
	fout.fill( symbol );
	fout << setw( numOfSymbols ) << BLANK;
	fout << endl;
	fout.fill( BLANK );
	fout << setw(3)<<BLANK;

}

//Print the count to the specified file
void PrintCount ( ofstream& fout,
				  int count )
{
	fout << ' Number of Nodes currently in the tree are: '
		 << count << endl;

}

standard.h:

#ifndef standard_h

#define standard_h

#include <iostream>

#include <iomanip>

#include <fstream>

using namespace std;

const char BLANK = ' ';

#endif

tree.h:

#ifndef tree_h

#define tree_h

#include 'standard.h'

struct nodeType

{

	int value;

};

struct treeType

{

	nodeType  data;

    treeType* left;

	treeType* right;

};

typedef treeType* treePtr;

class TreeClass

{ 

	private:

		treePtr root;

		//Insert the node in ascending order

		void InsertNode ( treePtr& ptr,

		                  nodeType aNode );

		//Create memory, insert data into a tree node

		treePtr GetANode ( nodeType ANode );

		//Delete a leaf node from a tree, free the memory

		void DeleteLeaf( treePtr location, 

					     treePtr& parent );

		//Delete a node with one left child only

		void DeleteLeft ( treePtr location,

					      treePtr& parent );

		//Delete a node with one right child only

		void DeleteRight ( treePtr location,

						   treePtr& parent );

		//Delete a node that has two children

		void DeleteTwoChildren( treePtr& location );

		//Called recursively to visit each node in the tree InOrder

		void InOrder ( ofstream& fout,

			           treePtr ptr );

		//Called recursively to visit each node in the tree PreOrder

		void PreOrder ( ofstream& fout,

			            treePtr ptr );

		//Called recursively to visit each node in the tree PostOrder

		void PostOrder ( ofstream& fout,

			             treePtr ptr );

		//Count the nodes in the tree

		void CountNodes ( treePtr ptr,

			              int& count );

	public:

		//Constructor

		TreeClass( void );

		//Create a tree from an input file

		void CreateATree ( ifstream& fin );

		//Return a bool based on value of root

		bool EmptyTree() const;

		//Print Tree content to an output file

		void PrintTree ( ofstream& fout );

		//Count the nodes in a tree

		int CountNodesInTree ( void );

		//Delete a node in the tree, return success of delete

		bool Delete ( int num );

		//Insert a node in Order in a tree

		void Insert ( nodeType node );

		//Print tree in PreOrder

		void PrintPreOrder ( ofstream& fout );

		//Print tree in PostOrder

		void PrintPostOrder ( ofstream& fout );

		//Search the tree for a num, return the node, the parent and a flag

		void Search ( treePtr& ptr,

			          treePtr& parent,

					  int num,

					  bool& success );

		//The destructor, free the memory

		~TreeClass ( void );

};

#endif

TreeFunctions.cpp:

#include 'tree.h'
///Add your methods HERE

///Private Methods ------------------------------------------------------------------------///

//Insert the node in ascending order
void TreeClass::InsertNode ( treePtr& ptr,
				             nodeType aNode )
{
	//if this is the first node
	if ( ptr == NULL )
	{

		ptr = GetANode ( aNode );

	}
	//is the value less than current ptr value, insert to the left
	else if ( aNode.value < ptr->data.value )
	{
		InsertNode ( ptr->left, aNode );
	}
	//if the value greater than the current ptr value,insert to the right
	else
	{
		InsertNode ( ptr->right, aNode );
	}
}

//Create memory, insert data into a tree node
treePtr TreeClass::GetANode ( nodeType aNode )
{
	treePtr ptr;

	//Create a new tree node
	ptr = new treeType;

	//Put the data into the tree node
	ptr->data = aNode;

	//Set the pointers of this new leaf node
	ptr->left = NULL;
	ptr->right = NULL;

	return ptr;
}

//Delete a leaf node from a tree, free the memory
void TreeClass:GrineleteLeaf( treePtr location,
						    treePtr& parent )
{
	//Check to see if it is the root
    if ( parent == NULL )
	{
		root = NULL;
	}
	else if (parent->right == location)
	{
		//right child, sever connection
		parent->right = NULL;
	}
    else
	{
		//left child, sever connection
        parent->left = NULL;
	}

	//free the memory
	delete location;
}

//Delete a node with one left child only
void TreeClass:GrineleteLeft ( treePtr location,
						     treePtr& parent )
{
	//Check to see if it is the root
	if ( parent == NULL )
	{
		//Make left child the root
		root = location->left;
	}
	else if ( parent->left == location )
	{
		//left child, re-connect to it's left
		parent->left = location->left;
	}
	else
	{
		//right child, re-connect to it's right
		parent->right = location->left;
	}

	//Set left pointer to NULL
	location->left = NULL;

	//Free the memory
	delete location;
}

//Delete a node with one right child only
void TreeClass:GrineleteRight( treePtr location,
						     treePtr& parent )
{
	//Check to see if it is the root
	if ( parent == NULL )
	{
		//Set root to the right child
		root = location->right;
	}
	else if ( parent->right == location )
	{
		//right child, re-connect right
		parent->right = location->right;
	}
    else
	{
		//left child, re-connect left
		parent->left = location->right;
	}

	//Set right pointer to NULL
	location->right = NULL;

	//Free the memory
	delete location;
}

//Delete a node that has two children
void TreeClass:GrineleteTwoChildren( treePtr& location )
{

	treePtr place;
	treePtr walker;

	//Go left once
	place = location->left;

	//Check right, if NULL stop
	if ( place->right == NULL )
	{// found a place
		//move the data into location
		location->data = place->data;

		//Set the pointer of location left to place's left
		location->left = place->left;

	}// found a place

	else
	{// walk through tree
		do
		{
			// find node without right child
			walker = place;

			//Keep going right
			place = place->right;
		}while ( place->right!=NULL );

		//move the data into location
		location->data = place->data;

		//connect left child of place to right of walker
		walker->right = place->left;

	}// walk through tree

	//set place's pointer to NULL
	place->left = NULL;

	//Free the memory
	delete place;
}

//Called recursively to visit each node in the tree InOrder
void TreeClass::InOrder( ofstream& fout,
					     treePtr ptr )
{
	//There is still a node in the tree
	if ( ptr != NULL )
	{
		//Go left
		InOrder( fout,
		         ptr->left );

		//Print this node
		fout << setw(3) << ptr->data.value;

		//Go right
		InOrder( fout,
		         ptr->right );
   }
}

//Called recursively to visit each node in the tree PreOrder
void TreeClass:RazzreOrder ( ofstream& fout,
						   treePtr ptr )
{
	//There is still a node in the tree
	if ( ptr != NULL )
	{
		//Print this node
		fout << setw(3) << ptr->data.value;

		//Go left
		PreOrder( fout,
		          ptr->left );

		//Go right
		PreOrder( fout,
		          ptr->right );

   }
} 

//Called recursively to visit each node in the tree PostOrder
void TreeClass:RazzostOrder ( ofstream& fout,
						    treePtr ptr )
{
	//There is still a node in the tree
	if ( ptr != NULL )
	{
		//Go left
		PostOrder( fout,
		           ptr->left );

		//Go right
		PostOrder( fout,
		           ptr->right );

		//Print the node
		fout << setw(3) << ptr->data.value;
   }
}

//Count the nodes in the tree
void TreeClass::CountNodes ( treePtr ptr,
						     int& count )
{
	//There is still a node in the tree
	if ( ptr !=NULL )
	{
		//Increment the count
		count++;

		//Go left
		CountNodes ( ptr->left,
			         count );

		//Go right
		CountNodes ( ptr->right,
			         count );
	}
}
///Public Methods ------------------------------------------------------------------------///
//Constructor
TreeClass::TreeClass()
{
	root = NULL;
}

//Create a tree from an input file
void TreeClass::CreateATree ( ifstream& fin )
{
	nodeType node;

	//while there is data in the input file
	while ( !fin.eof() )
	{
		//read a value
		fin >> node.value;

		//Insert the value into the tree
		Insert( node );
	}
}

//Return a bool based on value of root
bool TreeClass::EmptyTree() const
{
	return ( root == NULL );
}

//Print Tree content to an output file
void TreeClass:RazzrintTree ( ofstream& fout)

{
	//Set a node to the root
	treePtr ptr = root;

	//if null, tree is empty
	if (ptr == NULL)
	{
		fout<< 'Tree is empty' << endl;
	}
	else
	{
		//Call Inorder Print of tree
		InOrder ( fout,
	              ptr );
	}	           

}

//Count the nodes in a tree
int TreeClass::CountNodesInTree ( void )
{
	//Set a pointer to the root
	treePtr ptr = root;

	//Initialize the count
	int count = 0;

	//Call the recursive method to count the nodes in the tree
	CountNodes ( ptr,
		         count );

	return count;
}

//Delete a node in the tree, return success of delete
bool TreeClass:Grinelete ( int num )
{
	//Set a pointer to the root
	treePtr ptr = root;

	//Parent of root is null
	treePtr parent = NULL;

	bool success ;

	//Call recursive search method
	Search ( ptr,
		     parent,
			 num,
			 success );

	//If it was successful, node was found
	if ( success )
	{
		//Is it a leaf node?
		if ( ptr->left == NULL && ptr->right == NULL )
		{
			//Delete the leaf
			DeleteLeaf ( ptr,
				         parent );
		}
		//This is a node with only a left child
		else if ( ptr->left !=NULL && ptr->right == NULL )
		{
			//Delete a node with a left child
			DeleteLeft ( ptr,
				         parent );
		}
		//This is a node with a right child
		else if ( ptr->left == NULL && ptr->right != NULL )
		{
			//Delete a node with a right child
			DeleteRight ( ptr,
				          parent );
		}
		//it must be a node with two children
		else
		{
			//Delete a node with two children
			DeleteTwoChildren ( ptr );
		}
	}

	return success;
}

//Insert a node in Order in a tree
void TreeClass::Insert ( nodeType node )
{
	//Set a pointer to the root
	treePtr ptr = root;

	//Call the recursive method to insert a node
	InsertNode ( ptr,
		         node );

	//if this is the first node,set the root to the new node
	if ( EmptyTree())
	{
		root = ptr;
	}
}

//Print tree in PreOrder
void TreeClass:RazzrintPreOrder ( ofstream& fout )
{
	//Call the recursive method for PreOrder
	PreOrder ( fout,
		       root );
}

//Print tree in PostOrder
void TreeClass:RazzrintPostOrder ( ofstream& fout )
{
	//Call the recursive method for PostOrder
	PostOrder ( fout,
		        root );
}

//Search the tree for a num, return the node, the parent and a flag
void TreeClass::Search ( treePtr& ptr,
						 treePtr& parent,
						 int num,
						 bool& success )
{
	//Node was not found yet
	success = false;

	//while there are still nodes to search and node value was not found
	while ( ptr !=NULL && !success )
	{
		//If the node value in the tree is the value you are searching for
		if ( ptr->data.value == num )
		{
			//you found it
			success = true;
		}
		//if the node value in the tree is less than the value you are searching for
		else if ( num < ptr->data.value )
		{
			//Set the parent to the current ptr in the tree
			parent = ptr;

			//Move to the left
			ptr = ptr->left;
		}
		else
		{
			//Set the parent to the current ptr in the tree
			parent = ptr;

			//Move to the right
			ptr = ptr->right;
		}
	}
}

//The destructor, free the memory
TreeClass::~TreeClass ( void )
{
	//while the tree is not empty
	while ( !EmptyTree())
	{
		//Delete the node at the root
		Delete ( root->data.value );
	}
}

tree.txt:

48
12
56
2
9
18
52
49
10
-5
55
5
59
57
58
9
65
41
18
42

If you encounter any problems or errors, please let me know by providing an example of the code, input, output, and an explanation. Thanks.

Share