LeftistNode.h

#pragma once

template <class T>
class LeftistNode
{
private:
	T data;
	int shortest;
	LeftistNode<T> *pLeft;
	LeftistNode<T> *pRight;

public:
	LeftistNode()
	{
		this->shortest = 0;
		this->pLeft = 0;
		this->pRight = 0;
	}
	~LeftistNode()
	{}

	T GetData(void)
	{
		return this->data;
	}
	int GetShortest(void)
	{
		return this->shortest;
	}
	
	LeftistNode<T> *GetLeft(void)
	{
		return this->pLeft;
	}
	LeftistNode<T> *GetRight(void)
	{
		return this->pRight;
	}

	void SetData(T data)
	{
		this->data = data;
	}
	void SetShortest(int shortest)
	{
		this->shortest = shortest;
	}
	
	void SetLeft(LeftistNode<T> *pLeft)
	{
		this->pLeft = pLeft;
	}
	void SetRight(LeftistNode<T> *pRight)
	{
		this->pRight = pRight;
	}
	
};

LeftistTree.h

#pragma once

#include "LeftistNode.h"

template <class T>
class LeftistTree
{
private:
	LeftistNode<T>* pRoot;

public:
	LeftistTree()
	{
		this->pRoot = 0;
	}
	~LeftistTree()
	{
		while (this->pRoot)
		{
			this->Delete();
		}
			
	}

	T GetMin(void)
	{
		return this->pRoot->GetData();
	}

	bool isEmpty(void)
	{
		if (this->pRoot)
			return false;
		else
			return true;
	}
	bool isOnlyRoot(void)
	{
		if (this->pRoot)
		{
			if (this->pRoot->GetLeft() == 0x00
				&& this->pRoot->GetRight() == 0x00)
			{
				return true;
			}
			else
			{
				return false;
			}
		}
		else
			return false;
	}

	LeftistNode<T> *MinUnion(LeftistNode<T> *operand);
	LeftistNode<T> *MinUnion(LeftistNode<T> *operand1, LeftistNode<T> *operand2);
	LeftistNode<T> * MinCombine(LeftistNode<T> *operand);
	LeftistNode<T> * MinCombine(LeftistNode<T> *operand1, LeftistNode<T> *operand2);
	void Insert(T data);
	T Delete(void);
};

template <class T>
LeftistNode<T> * LeftistTree<T>::MinUnion(LeftistNode<T> *operand)
{
	if (this->pRoot->GetData() > operand->GetData())
	{
		LeftistNode<T> *temp = this->pRoot;
		this->pRoot = operand;
		operand = temp;
	}

	if (this->pRoot->GetRight() == 0x00)
	{
		this->pRoot->SetRight(operand);
	}
	else
	{
		this->pRoot->SetRight(MinUnion(this->pRoot->GetRight(), operand));
	}
	
	if (this->pRoot->GetLeft() == 0x00)
	{
		this->pRoot->SetLeft(this->pRoot->GetRight());
		this->pRoot->SetRight(0x00);
	}
	else if (this->pRoot->GetLeft()->GetShortest() < this->pRoot->GetRight()->GetShortest())
	{
		LeftistNode<T> *temp = this->pRoot->GetLeft();
		this->pRoot->SetLeft(this->pRoot->GetRight());
		this->pRoot->SetRight(temp);
	}

	if (this->pRoot->GetRight() == 0x00)
	{
		this->pRoot->SetShortest(1);
	}
	else
	{
		this->pRoot->SetShortest(this->pRoot->GetRight()->GetShortest() + 1);
	}

	return this->pRoot;
}

template <class T>
LeftistNode<T> * LeftistTree<T>::MinUnion(LeftistNode<T> *operand1, LeftistNode<T> *operand2)
{
	if (operand1->GetData() > operand2->GetData())
	{
		LeftistNode<T> *temp = operand1;
		operand1 = operand2;
		operand2 = temp;
	}

	if (operand1->GetRight() == 0x00)
	{
		operand1->SetRight(operand2);
	}
	else
	{
		operand1->SetRight(	MinUnion(operand1->GetRight(),operand2));
	}

	if (operand1->GetLeft() == 0x00)
	{
		operand1->SetLeft(operand1->GetRight());
		operand1->SetRight(0x00);
	}
	else if (operand1->GetLeft()->GetShortest() < operand1->GetRight()->GetShortest())
	{
		LeftistNode<T> *temp = operand1->GetLeft();
		operand1->SetLeft(operand1->GetRight());
		operand1->SetRight(temp);
	}

	if (operand1->GetRight() == 0x00)
	{
		operand1->SetShortest(1);
	}
	else
	{
		operand1->SetShortest(operand1->GetRight()->GetShortest() + 1);
	}

	return operand1;
}
template <class T>
LeftistNode<T> * LeftistTree<T>::MinCombine(LeftistNode<T> *operand)
{
	if (this->pRoot == 0x00)
		this->pRoot = operand;

	else if (operand)
		this->pRoot = this->MinUnion(this->pRoot, operand);
	operand = 0;

	return this->Root;
}

template <class T>
LeftistNode<T> *LeftistTree<T>::MinCombine(LeftistNode<T> *operand1, LeftistNode<T> *operand2)
{
	if (operand1 == 0x00)
		operand1 = operand2;

	else if (operand2)
		operand1 = this->MinUnion(operand1, operand2);
	operand2 = 0;
	return operand1;
}
template <class T>
void LeftistTree<T>::Insert(T data)
{
	LeftistNode<T> *pNew = new LeftistNode<T>;
	pNew->SetData(data);
	
	if (this->pRoot == 0x00)
	{
		this->pRoot = pNew;
	}
	else
	{
		if (this->pRoot->GetData() > data)
		{
			//swap operation
			LeftistNode<T> *temp = this->pRoot;
			this->pRoot = pNew;
			pNew = temp;
		}

		if (this->pRoot->GetRight() == 0x00)
		{
			this->pRoot->SetRight(pNew);
		}
		else//min union a->right, b
		{
			this->pRoot->SetRight(this->MinUnion(this->pRoot->GetRight(), pNew));
		}

		if (this->pRoot->GetLeft() == 0x00)
		{
			this->pRoot->SetLeft(this->pRoot->GetRight());
			this->pRoot->SetRight(0x00);
		}
		else if (this->pRoot->GetLeft()->GetShortest() < this->pRoot->GetRight()->GetShortest())
		{
			LeftistNode<T> *temp = this->pRoot->GetLeft();
			this->pRoot->SetLeft(this->pRoot->GetRight());
			this->pRoot->SetRight(temp);
		}

		if (this->pRoot->GetRight() == 0x00)
			this->pRoot->SetShortest(1);
		else
			this->pRoot->SetShortest(this->pRoot->GetRight()->GetShortest() + 1);
	}
}

template <class T>
T LeftistTree<T>::Delete(void)
{
	LeftistNode<T> *left = 0x00;
	LeftistNode<T> *right = 0x00;
	LeftistNode<T> *pDel = 0x00;

	T pop;
	
	if (this->pRoot)
	{
		left = this->pRoot->GetLeft();
		right = this->pRoot->GetRight();

		left = this->MinCombine(left, right);

		pDel = this->pRoot;

		pop = pDel->GetData();

		this->pRoot = left;

		delete pDel;
	}
	return pop;
}