minleftlisttree.cpp

插入和删除最小元素操作

// MinLeftistTree.cpp: implementation of the MinLeftistTree class.
//
//////////////////////////////////////////////////////////////////////

#include "MinLeftlistTree.h"

#include <iostream>

using std::cout;
using std::cin;
using std::endl;

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

LeftlistNode* MinLeftlistTree::MinUnion(LeftlistNode *a, LeftlistNode *b )
{
	if( a->data.key > b->data.key )
	{
		LeftlistNode *t = a;
		a = b;
		b = t;
	}
	if( !a->RightChild)
		a->RightChild = b;
	else
		a->RightChild = MinUnion( a->RightChild, b );

	if(!a->LeftChild)
	{
		a->LeftChild = a->RightChild;
		a->RightChild = 0;
	}
	else if( a->LeftChild->shortest < a->RightChild->shortest )
	{
		LeftlistNode *t = a->LeftChild;
		a->LeftChild = a->RightChild;
		a->RightChild = t;
	}

	if( !a->RightChild )
		a->shortest = 1;
	else
		a->shortest = a->RightChild->shortest + 1;
	return a;
}

void MinLeftlistTree::Insert( const element& x  )
{
}

void MinLeftlistTree::MinCombine(MinLeftlistTree* b)
{
	if(!root) 
		root = b->root;
	else if(b->root) 
		root = MinUnion(root,b->root);
	b->root = 0;
}

element* MinLeftlistTree::Delete( element& del )
{
	LeftlistNode* empty = 0;
	if( root == empty )
	{
		return 0;
	}

	return &del;
}