Find the minimum data of binary tree

[ppendless]

I want a recursive function that returns a pointer pointing to the node which has the minimum data in the binary tree.

That's what I wrote:

struct CP {
int data; // data of the node
CP * left; // pointer to the left subtree
CP * right; // pointer to the right subtree
};

typedef CP * CPPtr;

CPPtr MinValue(CPPtr SP){

if(SP->left!=NULL || SP->right!=NULL){
if(SP->data < SP->left->data && SP->data < SP->right->data){
return SP;
}
else if(SP->left->data < SP->data && SP->left->data < SP->right->data){
return SP->left;
}
else if(SP->right->data < SP->left->data && SP->right->data < SP->data){
return SP->right;
}
}
else return SP;
}

It can only find one side of the binary tree. Can someone help me how to do with the code? Thank you very much!

[ppendless]

can someone help me?

[toomanystars]

Have a look at this excellent and easy to understand article by Alex Allain on binary trees. It should anwser your question I think.

http://www.cprogramming.com/tutorial/lesson18.html

Mike

[Michaela Elise]

since you asked, here is the code. It is your homework to find and edit the parts you need.

The function and var names are based on ferngully. Get it, tree, ferngully, ha ha.

//Michaela Ervin - Tree ADT

#ifndef H_TREE
#define H_TREE

#include <iostream>
#include "stack.h"

template <class dType>
struct leaf
{
	dType _id;
	leaf<dType> *_left, *_right;
};

const int MAXSTACK = 15;

template <class dType>
class tree
{
	template <class dType> friend std::ostream& operator<< (std::ostream& outs, const tree<dType>& tree);
protected:
	leaf<dType>* _root;
public:
	tree();
	bool isEmpty() const;
	void grow(dType _water);
	void prune(dType _todel);
	void inordertraversalR(std::ostream& outs) const;
	void preordertraversalR(std::ostream& outs) const;
	void postordertraversalR(std::ostream& outs) const;
	void inordertraversalI(std::ostream& outs) const;
	void preordertraversalI(std::ostream& outs) const;
	int countR(node* _root);
	void killtree();
	~tree();
private:
	void delete_zero(leaf<dType>* _p, leaf<dType>* _l);
	void delete_one(leaf<dType>* _p, leaf<dType>* _l);
	void delete_two(leaf<dType>* _l);
	void inorderR(leaf<dType>* _l, std::ostream& outs) const;
	void preorderR(leaf<dType>* _l, std::ostream& outs) const;
	void postorderR(leaf<dType>* _l, std::ostream& outs) const;
	void hexxus(leaf<dType>*& _l);
};

template <class dType>
tree<dType>::tree():_root(NULL) {}

template <class dType>
std::ostream& operator<< (std::ostream& outs, const tree<dType>& tree)
{
	//Put stuff to do here!
	return outs;
}

template <class dType>
bool tree<dType>::isEmpty() const{return (_root == NULL);}

template <class dType>
void tree<dType>::grow(dType _water)
{
	leaf<dType> *_l, *_t, *_n;
	_n = new leaf<dType>;

	_n->_id = _water;
	_n->_left = NULL;
	_n->_right = NULL;

	if (!isEmpty())
	{
		_l = _root;
		while (_l != NULL)
		{
			_t = _l;
			if (_water < _l->_id)
				_l = _l->_left;
			else if (_water > _l->_id)
				_l = _l->_right;
		}
		if (_t->_id > _water)
			_t->_left = _n;
		else
			_t->_right = _n;
	}
	else
		_root = _n;
}

template <class dType>
void tree<dType>::prune(dType _todel)
{
	leaf<dType> *_l, *_p;
	_p = NULL;
	_l = _root;
	
	while (_l != NULL && _l->_id != _todel)
	{
		_p = _l;
		if (_todel < _l->_id)
			_l = _l->_left;
		else
			_l = _l->_right;
	}
	if (_l != NULL)
	{
		if (_l->_left == NULL && _l->_right == NULL)
			delete_zero(_p, _l);
		else if (_l->_left != NULL && _l->_right != NULL)
			delete_two(_l);
		else
			delete_one(_p, _l);
	}
	else
		std::cout << "Node w/ id: " << _todel << " is not in the tree...";
}

template <class dType>
void tree<dType>::delete_zero(leaf<dType>* _p, leaf<dType>* _l)
{
	if (_p->_left == _l)
		_p->_left = NULL;
	else
		_p->_right = NULL;
	delete _l;
}

template <class dType>
void tree<dType>::delete_one(leaf<dType>* _p, leaf<dType>* _l)
{
	if (_p->_left == _l)
		if (_l->_left != NULL)
			_p->_left = _l->_left;
		else
			_p->_left = _l->_right;
	else if (_p->_right == _l)
		if (_l->_left != NULL)
			_p->_right = _l->_left;
		else
			_p->_right = _l->_right;
}

template <class dType>
void tree<dType>::delete_two(leaf<dType>* _l)
{
	leaf<dType> *_s;
	dType _holder;

	_s = _l->_left;
	while (_s->_right != NULL)
	{
		if (_s->_right != NULL)	
			_s = _s->_right;
		else
			_s = _s->_left;
	}
	_holder = _s->_id;
	prune(_s->_id);
	_l->_id = _holder;
}

template <class dType>
void tree<dType>::inordertraversalR(std::ostream& outs) const{inorderR(_root, outs);}

template <class dType>
void tree<dType>::inorderR(leaf<dType>* _l, std::ostream& outs) const
{
	if (!isEmpty())
	{
		if (_l->_left != NULL) inorderR(_l->_left, outs);
		outs << _l->_id << " ";
		if (_l->_right != NULL) inorderR(_l->_right, outs);
	}
	else
		outs << "The tree has not grown yet...";
}

template <class dType>
void tree<dType>::preordertraversalR(std::ostream& outs) const{preorderR(_root, outs);}

template <class dType>
void tree<dType>::preorderR(leaf<dType>* _l, std::ostream& outs) const
{
	if (!isEmpty())
	{
		outs << _l->_id << " ";
		if (_l->_left != NULL) preorderR(_l->_left, outs);
		if (_l->_right != NULL) preorderR(_l->_right, outs);
	}
	else
		outs << "The tree has not grown yet...";
}

template <class dType>
void tree<dType>::postordertraversalR(std::ostream& outs) const{postorderR(_root, outs);}

template <class dType>
void tree<dType>::postorderR(leaf<dType>* _l, std::ostream& outs) const
{
	if (!isEmpty())
	{
		if (_l->_left != NULL) postorderR(_l->_left, outs);
		if (_l->_right != NULL) postorderR(_l->_right, outs);
		outs << _l->_id << " ";
	}
	else
		outs << "The tree has not grown yet...";
}

template <class dType>
void tree<dType>::inordertraversalI(std::ostream& outs) const
{
	if (!isEmpty())
	{
		stack<leaf<dType>*> _logs(MAXSTACK, NULL);
		leaf<dType> *_l = _root;

		while (!_logs.isEmpty() || _l != NULL)
			if ( _l != NULL)
			{
				_logs.push(_l);
				_l = _l->_left;
			}
			else
			{
				_l = _logs.pop();
				outs << _l->_id << " ";
				_l = _l->_right;
			}
	}
	else
		outs << "The tree has not grown yet...";
}

template <class dType>
void tree<dType>::preordertraversalI(std::ostream& outs) const
{
	if (!isEmpty())
		{
			stack<leaf<dType>*> _logs(MAXSTACK, NULL);
			leaf<dType> *_l = _root;

			while (!_logs.isEmpty() || _l != NULL)
				if ( _l != NULL)
				{
					outs << _l->_id << " ";
					_logs.push(_l);
					_l = _l->_left;
				}
				else
				{
					_l = _logs.pop();
					_l = _l->_right;
				}
		}
		else
			outs << "The tree has not grown yet...";	
}

template <class dType>
int tree<dType>::countR(node* _root)
{
	if (!isEmpty())
	{
		if (_l->_left != NULL) return 1 + countR(_l->_left, outs);
		if (_l->_right != NULL) return 1 + countR(_l->_right, outs);
	}
}

template <class dType>
tree<dType>::~tree(){hexxus(_root);}

template <class dType>
void tree<dType>::killtree(){hexxus(_root);}

template <class dType>
void tree<dType>::hexxus(leaf<dType>*& _l)
{
	if (_l != NULL)
	{
		hexxus(_l->_left);
		hexxus(_l->_right);
		delete _l;
		_l = NULL;
	}
}
#endif 

[toomanystars]

@Michaela Elise (21)



I think you are going to give ppendless (2) a heart attack

[ppendless]

well indeed.....

[Michaela Elise]

lol, well, ppendless, you should be able to find the recursive traversals (Hint they either end with an R or I) bet you can guess which one is recursive. LOL. Just edit one of them to store the min value.

CP* min;
if(CP->value < current->value)
    CP = current;

you will need go initialize min, whatever the first node is, most likely root, is fine.

[Smac89]

comments are for sissies :D

[Michaela Elise]

LOL @ Smac89

It is a basic bstree, other than my 'at-the-time' variable names.