Power Dictionary

B.Second Edition

This is the second edition of my dictionary and it is very powerful now!

1。 Basic idea: I want to add two features to my original dictionary(in fact they seem to be same, yet...). One

is the "frequency" which means how many times the word actually is encountered. It is a very important statistic

data to be stored in file. So, I have to change the "saveToFile" method to add this data.(Actually I add this 

to their ancester---Tree class). Second data is "Rank" which means which position of this word is in total words

in view of "frequency". So, it is a data connected with "frequency" and is not necessary to be save to file. However,

it need to be updated frequently which is not so easy after the total quantity of words increasing. So, I still 

use the basic "binary search tree" to solve the rank problem with changing the "compare method" of RankTree to be

with the "frequency" characteristic instead of "key". In other word, key is "frequency" instead of "name".( but not

exactly, as frequency is often same, and in this case, I compare "key" or "name", otherwise, there will be too 

many same rank word.) 

2。 Program design: The biggest problem is how to walk round the "key" problem and still use the original "insert"

method. It is only way to setup a new class--RankTree which overload the operator "<" and ">" so that the "insert"

method will correctly use "frequency" to compare first during "inserting" procedure. The other big problem is that

I realized how necessary to make a "real call back" function for "traverse" the whole tree along with a user defined

data pointer inside the user defined "visit" method when visiting each node of tree. So, I overload the "traverse"

method of Tree class to allow user sending his own data by parameter "userPtr". Then I easily rank each word by 

this callback function.

3。 Major function：

     A. void Tree::traverse(void (*visit)(Tree* node, void* userPtr), void* userPtr, 
		TraverseOrder defaultOrder)

	This is the callback function with one more user defined data pointer "userPtr", and I actually use it to 

	transfer the rank data to let it increment one by one.

	B. void RankTree::setRankTree(WordTree* wordRoot)

	This is the heart function of using new class RankTree to set up a new "forest" of RankTrees with "frequency"

	as first primary "key" which means "compare" with "freq" first, "key" second if "freq" are same. It is quite

	important that you must setup a root for this "RankTree forest", as "insert" method....Oh my god! It is

	not necessary to differenciate the root with all other nodes, right? I will try later.

	C. bool RankTree::operator <(Tree& node);  bool RankTree::operator >(Tree& node);

	I overload these two function instead of so-called "compare" method, as when I designed I didn't realize

 	the need to put both "rank"&"frequency" into ancester class---Tree. Now, it is better to override "compare"

	method.

4。 Further improvement：

	A. I have to go soon, so, no more time.

	B. Override "compare" method instead of "<,>". try to make simple way of "setRankTree" method, as my "insert"

	method is so perfect, no need to do some extra judgement for root.

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <ctime>

using namespace std;

const MaxWordLength = 255;

enum TraverseOrder
{
	PREORDER, MIDORDER, POSTORDER
};

class Tree
{
private:	
	Tree* pLeft;
	Tree* pRight;
	Tree* pParent;
	char* pName;
	int index;
	static int treeCounter;
	static Tree* pRoot;
	int freq;
	int rank;
	void preWalk(Tree* node, void (*visit)(Tree* node));
	void midWalk(Tree* node, void (*visit)(Tree* node));
	void postWalk(Tree* node, void (*visit)(Tree* node));
	void preWalk(Tree* node, void (*visit)(Tree* node, void* userPtr), void* userPtr);
	void midWalk(Tree* node, void (*visit)(Tree* node, void* userPtr), void* userPtr);
	void postWalk(Tree* node, void (*visit)(Tree* node, void* userPtr), void* userPtr);
protected:
	void* pKey;
public:
	const int getRank() { return rank;}
	void setRank(const int newRank) { rank = newRank;}
	const int getFreq() {return freq;}
	void setFreq(const int newFreq) { freq = newFreq;}
	void setFreq() {freq++;}
	Tree* left();
	Tree* right();
	Tree* parent();
	virtual void* key();
	virtual void setKey(void* newKey);
	void setRoot(Tree* node);
	const char* name();
	const int getIndex();
	void setLeft(Tree* leftSon);
	void setRight(Tree* rightSon);
	void setParent(Tree* father);
	void setIndex(const int number);
	virtual	int compare(const void* otherKey); 
	void setName(const char *str);
	void giveBirth();
	virtual bool operator>(Tree&);
	virtual bool operator==(Tree&);
	virtual bool operator<(Tree&);	
	Tree();
	virtual ~Tree();
	static Tree* root() {return pRoot;}
	const int count();
	void traverse(void ( *visit)(Tree* node), TraverseOrder defaultOrder= MIDORDER);
	void traverse(void (*visit)(Tree* node, void* userPtr), void* userPtr, 
		TraverseOrder defaultOrder = MIDORDER);
};

void visitRank(Tree* node, void* userPtr);

void defaultVisit(Tree* node);

class BinaryTree: public Tree
{
private:
	

public:
	virtual void remove(BinaryTree* node);
	virtual BinaryTree* next();
	virtual BinaryTree* prev();
	virtual bool insert(BinaryTree* node);
	virtual ~BinaryTree();

};

class WordTree: public BinaryTree
{
private:
	static int wordLength;
	static int wordCounter;
	WordTree* addNode(WordTree* node, FILE** stream);
	

protected:
	void setWordCounter();
	void readWord(FILE** file);
	void addWord(char* buffer);
public:

	WordTree* readNode(WordTree* node, FILE** stream);
	WordTree* readFromFile(const char* fileName);
	void saveNode(WordTree* node, FILE** stream);
	virtual int compare(const void *otherKey);
	void setWordLength(const int newLength);
	static const int getWordLength();
	virtual void setKey(void* newKey);
	virtual bool operator>(Tree&);
	virtual bool operator==(Tree&);
	virtual bool operator<(Tree&);
	void openFile(const char* fileName);
	WordTree(const char * fileName);
	WordTree();
	int wordCount();
	virtual void setName(const char *str);
	void saveToFile(const char* fileName);
	~WordTree();
	WordTree* findWord(const char* buffer);
};

class RankTree: public WordTree
{
private:
	static RankTree* rankRoot;
public:	
	virtual bool operator>(Tree& node);
	virtual bool operator<(Tree& node);
	void setRankTree(WordTree* wordRoot);
	

	RankTree();
	

};

int count=0;

int main()
{
	WordTree *ptr = new WordTree;
	char choice[6], fileName[30];

	ptr = ptr->readFromFile("c:\\nickback.txt");
	cout<<"quit? or input?\nEnter your choice: \n";
	cin>>choice;
	while (strcmp(choice, "quit")!=0&&strcmp(choice, "input")!=0)
	{
		cout<<"quit? or input?\n Enter your choic: \n";
		cin>>choice;
	}
	if (strcmp(choice, "quit")==0)
	{
		cout<<"The total number of words in dictionary is "<<ptr->wordCount()<<endl;
		return 0;
	}
	else
	{
		if (strcmp(choice, "input")==0)
		{
			cout<<"\nnow input file name here(input 'quit' to exit):\n";
			cin>>fileName;
			while (strcmp(fileName, "quit")!=0)
			{
				ptr->openFile(fileName);
				cout<<"\nnow input file name here(input quit to exit):\n";
				

				cin>>fileName;
			}
			cout<<"\nDo you want to see contents?(yes or no)\n";
			

			
			cin>>choice;
			if (strcmp(choice, "yes")==0)
			{
				ptr->traverse(defaultVisit, PREORDER);
			}

			cout<<"\nDo you want to rank the tree?(yes or no)\n";
			cin>>choice;
			if (strcmp(choice, "yes")==0)
			{
				int rankCount =0;
				RankTree *rankPtr = new RankTree;
				rankPtr->setRankTree(ptr);
				rankPtr->traverse(visitRank, (void*)(&rankCount), MIDORDER);
				rankPtr->traverse(defaultVisit, PREORDER);
			}
			cout<<"The total number of words in dictionary is "<<ptr->wordCount();
			ptr->saveToFile("c:\\nickback.txt");
		}
	}

	return 0;
}

int WordTree::wordCounter = 0;
int WordTree::wordLength = 20;
RankTree* RankTree::rankRoot = NULL;

RankTree::RankTree()
{
	if (rankRoot == NULL)
	{
		rankRoot = this;
	}
}

void visitRank(Tree* node, void* userPtr)
{
	node->setRank(*(int*)(userPtr));
	*(int*)(userPtr) +=1;
	

}

bool RankTree::operator <(Tree& node)
{
	int result;
	result = getFreq() - node.getFreq();
	if (result !=0)
	{
		return (result<0);
	}
	else
	{
		return (strcmp((char*)key(), (char*)node.key())<0);
	}
}

bool RankTree::operator >(Tree& node)
{
	int result;
	result = getFreq() - node.getFreq();
	if (result !=0)
	{
		return (result>0);
	}
	else
	{
		return (strcmp((char*)key(), (char*)node.key())>0);
	}
}

void RankTree::setRankTree(WordTree* wordRoot)
{
	RankTree* ptr;

	if (wordRoot!=NULL)
	{
		if (this->root()!=NULL)
		{
			ptr = new RankTree;
			ptr->setFreq(wordRoot->getFreq());
			ptr->setKey((void*)wordRoot->key());
			ptr->insert(ptr);
		}
		else
		{
			this->setRoot(this);
			this->setFreq(wordRoot->getFreq());
			this->setKey((void*)wordRoot->key());
		}

		setRankTree((WordTree*)wordRoot->left());
		setRankTree((WordTree*)wordRoot->right());
	}

}

BinaryTree::~BinaryTree()
{

}

WordTree::~WordTree()
{
	

}

void WordTree::setWordCounter()
{
	wordCounter ++;
}

const int WordTree::getWordLength()
{
	return wordLength;
}

WordTree* WordTree::addNode(WordTree* node, FILE** stream)
{
	char buffer[MaxWordLength];
	int index, pIndex, number;
	WordTree *domino;
	char *ptr=buffer, ch;
	

	fread((void*)(&index), sizeof(int), 1, *stream);
	fread((void*)(&pIndex), sizeof(int), 1, *stream);

	if (index==-1&&pIndex==-1)
	{
		return NULL;
	}

	do
	{
		ch = fgetc(*stream);
		*ptr = ch;
		ptr++;
	}
	while(ch!='\0');
	fread((void*)(&number), sizeof(int), 1, *stream);
	setWordCounter();  //add a word

	if (pIndex== -1)  //this is root
	{			
		node->setIndex(index);
		node->setFreq(number);
		node->setName(buffer);
		node->setRoot(node);
		return node;
	}

	while (pIndex!=node->getIndex())
	{	
		if (node->parent()==NULL)
		{
			return NULL;
		}
		node= (WordTree*)node->parent(); 
	}

	if (node!=NULL&&pIndex==node->getIndex())
	{
		domino = new WordTree;
		domino->setIndex(index);
		domino->setName(buffer);
		domino->setFreq(number);
		domino->setParent(node);
		if (*domino<*node)
		{
			node->setLeft(domino);
		}
		else
		{
			node->setRight(domino);
		}
		

		return domino;
	}
	else
	{
		return NULL;
	}
}

WordTree* WordTree::readNode(WordTree* node, FILE** stream)
{	
	WordTree* domino = node;

	while (domino!=NULL)
	{
		domino = addNode(domino, stream);
	}
	return (WordTree*)node->root();  //this is ugly as I have to remove those sentinal 
}

WordTree* WordTree::readFromFile(const char* fileName)
{
	FILE* stream;

	if ((stream=fopen(fileName, "r+b"))==NULL)
	{
		cout<<"unable to open file "<<fileName<<endl;
		return NULL;
	}
	else
	{
		WordTree* ptr= new WordTree;
		return readNode(ptr, &stream);	
	}
	fclose(stream);
}

void WordTree::saveNode(WordTree* node, FILE** stream)
{
	int first, second, number;

	first = node->getIndex();
	number = getFreq();

	fwrite((void*)(&first), sizeof(int), 1, *stream);
	if (node->parent()==NULL)
	{
		second = -1;		
	}
	else
	{
		second = node->parent()->getIndex();		
	}
	fwrite((void*)(&second), sizeof(int), 1, *stream);
	fwrite((void*)(node->name()),sizeof(char), strlen(node->name()), *stream);
	fputc('\0', *stream);//I have to put this '/n' otherwise there is always problem!
	fwrite((void*)(&number), sizeof(int), 1, *stream);
}

	
void traverseTree(WordTree* node, FILE** stream)
{
	if (node!=NULL)
	{
		node->saveNode(node, stream);
		traverseTree((WordTree*)node->left(), stream);
		traverseTree((WordTree*)node->right(), stream);
	}
}

void writeEnd(FILE** stream)
{
	int temp1=-1, temp2=-1;
	fwrite((void*)(&temp1), sizeof(int), 1, *stream);
	fwrite((void*)(&temp2), sizeof(int), 1, *stream);
}

void WordTree::saveToFile(const char* fileName)
{
	void traverseTree(WordTree* node, FILE ** stream);
	void writeEnd(FILE** stream);

	WordTree *domino;
	

	FILE * stream;
	

	if ((stream=fopen("c:\\nickback.txt", "w+b"))==NULL)
	{
		cout<<"unable to save to file "<<fileName<<endl;
	}
	else
	{
		domino = (WordTree*)root();
		traverseTree((WordTree*)domino, &stream);
	}
	writeEnd(&stream);
	fclose(stream);
}

	
const int Tree::count()
{
	return treeCounter;
}

void WordTree::setWordLength(const int newLength)
{
	if (newLength>MaxWordLength)
	{
		cout<<"exceed max word length."<<endl;
	}
	else
	{
		wordLength = newLength;
	}
}

int WordTree::compare(const void*otherKey)
{
	return strcmp((char*)key(), (char*)otherKey);
}

int WordTree::wordCount()
{
	return wordCounter;
}

WordTree::WordTree()
{
	

}

void WordTree::openFile(const char* fileName)
{
	FILE * stream;	
	if ((stream=fopen(fileName, "r+b"))==NULL)
	{
		cout<<"unable open file!"<<endl;
	}
	else
	{
		readWord(&stream);
	}
	fclose(stream);
}

void WordTree::readWord(FILE **stream)
{
	char buffer[MaxWordLength];
	char *ptr = buffer;
	char ch;
	int counter =0;

	
	while (!feof(*stream))
	{
		ptr = buffer;
		counter =  0;
		ch = toupper(fgetc(*stream));
		while (isalnum(ch)&&!feof(*stream)&&counter<wordLength)
		{
			*ptr = ch;
			ch = toupper(fgetc(*stream));
			ptr++;
			counter++;
		}

		if (ptr!=buffer)
		{
			*ptr='\0';
			addWord(buffer);
		}	
	}
}

WordTree* searchWord(WordTree* node, const char* buffer)
{
	int result;
	if (node!=NULL)
	{		
		result = strcmp((char*)(node->key()), buffer);
		if (result ==0)
		{
			return node;
		}
		else
		{
			if (result < 0)
			{
				return searchWord((WordTree*)node->right(), buffer);
			}
			else
			{
				return searchWord((WordTree*)node->left(), buffer);
			}
		}
	}
	else
	{
		return NULL;
	}
}

WordTree* WordTree::findWord(const char *buffer)
{
	WordTree* searchWord(WordTree* node, const char* buffer);
	return searchWord((WordTree*)root(), buffer);
}

void WordTree::addWord(char * buffer)
{
	//need add a findword method and find first and then new
	WordTree *ptr;
	ptr = findWord(buffer);
	if (ptr==NULL)
	{
		ptr = new WordTree;
	

		ptr->setName(buffer);    
		if (ptr->insert(ptr))
		{
			setWordCounter();
		}	
	}
	else
	{
		ptr->setFreq();
	}
}

void WordTree::setName(const char *str)
{
	Tree::setName(str);
	setKey((void*)name());
}

int Tree::treeCounter= 0;

WordTree::WordTree(const char* fileName)
{
	WordTree::WordTree();
	openFile(fileName);
}

void WordTree::setKey(void * newKey)
{
	pKey = newKey;
}

bool WordTree::operator <(Tree& second)
{
	if (strcmp((char*)key(), (char*)second.key())<0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

bool WordTree::operator ==(Tree& second)
{
	if (strcmp((char*)key(), (char*)second.key())==0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

bool WordTree::operator >(Tree& second)
{
	if (strcmp((char*)key(), (char*)second.key())>0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

void defaultVisit(Tree* node)
{
	cout<<"\n\n";
	cout<<"default visiting tree index:"<<node->getIndex()<<endl;
	cout<<"and tree name is:"<<node->name()<<endl;
	cout<<"and its frequency is: "<<(node)->getFreq()<<endl;
	cout<<"and its rank is:"<<node->getRank()<<endl;
	if (node->parent()!=NULL)
	{
		cout<<"its parent is:"<<node->parent()->name()<<endl;
		if (node==node->parent()->left())
		{
			cout<<"and it is left son."<<endl;
		}
		else
		{
			cout<<"and it is right son"<<endl;
		}
	}
	else
	{
		cout<<"it has no parent"<<endl;
	}
	cout<<"\n\n";
}

void Tree::preWalk(Tree* node, void (*visit)(Tree* node))
{
	if (node!=NULL)
	{	
		visit(node);
		preWalk(node->left(), visit);		
		preWalk(node->right(), visit);
	}
}

void Tree::postWalk(Tree* node, void (*visit)(Tree* node))
{
	if (node!=NULL)
	{
		postWalk(node->left(), visit);
		postWalk(node->right(), visit);
		visit(node);
	}
}

void Tree::midWalk(Tree* node, void (*visit)(Tree* node))
{
	if (node!=NULL)
	{
		midWalk(node->left(), visit);
		visit(node);
		midWalk(node->right(), visit);
	}
}

void Tree::preWalk(Tree* node, void (*visit)(Tree* node, void* userPtr), void* userPtr)
{
	if (node!=NULL)
	{	
		visit(node, userPtr);
		preWalk(node->left(), visit, userPtr);		
		preWalk(node->right(), visit, userPtr);
	}
}

void Tree::midWalk(Tree* node, void (*visit)(Tree* node, void* userPtr), void* userPtr)
{
	if (node!=NULL)
	{
		midWalk(node->left(), visit, userPtr);
		visit(node, userPtr);
		midWalk(node->right(), visit, userPtr);
	}
}

void Tree::postWalk(Tree* node, void (*visit)(Tree* node, void* userPtr), void* userPtr)
{
	if (node!=NULL)
	{
		postWalk(node->left(), visit, userPtr);
		postWalk(node->right(), visit, userPtr);
		visit(node, userPtr);
	}
}

void Tree::traverse(void (*visit)(Tree* node, void* userPtr), void* userPtr, 
		TraverseOrder defaultOrder)
{
	Tree *domino;
	domino = root();

	switch(defaultOrder)
	{
	case PREORDER:
		preWalk(domino, visit, userPtr);
		break;
	case MIDORDER:
		midWalk(domino, visit, userPtr);
		break;
	case POSTORDER:
		postWalk(domino, visit, userPtr);
		break;
	}
}

void Tree::traverse(void (*visit)(Tree* node), TraverseOrder defaultOrder)
{
	Tree *domino;
	domino = root();

	switch(defaultOrder)
	{
	case PREORDER:
		preWalk(domino, visit);
		break;
	case MIDORDER:
		midWalk(domino, visit);
		break;
	case POSTORDER:
		postWalk(domino, visit);
		break;
	}
}

Tree* Tree::pRoot = NULL;

void BinaryTree::remove(BinaryTree* node)
{
	BinaryTree* ptr=NULL;

	if (node->left()==NULL || node->right()==NULL)
	{
		if (node->left()!=NULL)
		{
			node->parent()->setLeft(node->left());
			node->left()->setParent(node->parent());
		}
		if (node->right()!=NULL)
		{
			node->parent()->setRight(node->right());
			node->right()->setParent(node->parent());
		}
	}
	else
	{
		ptr = node->next();
		remove(ptr);
		ptr->setParent(node->parent());
		if (node->parent()==NULL)
		{
			node->setRoot(ptr);			
		}
		else
		{
			if (node==node->parent()->left())
			{
				node->parent()->setLeft(ptr);
			}
			else
			{
				node->parent()->setRight(ptr);
			}
			ptr->setLeft(node->left());
			ptr->setRight(node->right());
		}
	}
}

bool Tree::operator==(Tree& second)
{
	if (this->compare(second.key())==0)
	{
		return true;
	}
	else
	{
		return false;
	}	
}

bool Tree::operator <(Tree& second)
{
	if (this->compare(second.key())<0)
	{
		return true;
	}
	else
	{
		return false;
	}	
}

bool Tree::operator >(Tree& second)
{
	if (this->compare(second.key())>0)
	{
		return true;
	}
	else
	{
		return false;
	}	
}

int Tree::compare(const void * otherKey)
{
	return *((int*)(key()))- *((int*)(otherKey));
}

void* Tree::key()
{
	return pKey;
}

void Tree::setKey(void *newKey)
{
	pKey = malloc(sizeof(int));
	*(int*)(pKey) = *(int*)(newKey);
}

void Tree::setRoot(Tree *node)
{
	pRoot = node;
}

bool BinaryTree::insert(BinaryTree* node)
{
	Tree* ptr, *dummy;

	ptr = root();
	dummy = ptr;
	while (ptr!=NULL)
	{
		dummy = ptr;
		if (*ptr>*node)
		{				
			ptr = ptr->left();
		}
		else
		{
			if (*ptr<*node)
			{
				ptr=ptr->right();
			}
			else
			{
				if (*ptr==*node)
				{					
					return false;				
				}
			}
		}
	}

	node->setParent(dummy);

	if (dummy==NULL)
	{
		setRoot(node);		
	}
	else
	{
	//	node->setRoot(dummy->root());
		if (*dummy>*node)
		{
			dummy->setLeft(node);
		}
		else
		{
			if (*dummy<*node)
			{
				dummy->setRight(node);
			}
		}  //if "== ", donot insert;
	}
	return true;
}
				

void Tree::setLeft(Tree* leftSon)
{
	pLeft = leftSon;
}

void Tree::setRight(Tree* rightSon)
{
	pRight = rightSon;
}

void Tree::setParent(Tree* father)
{
	pParent = father;
}

void Tree::giveBirth()
{
	Tree* leftTree = new Tree;
	Tree* rightTree = new Tree;
	char str[128];

	leftTree->setIndex(this->getIndex() *2 );
	rightTree->setIndex(this->getIndex() * 2 + 1);

	this->setLeft(leftTree);
	this->setRight(rightTree);

	leftTree->setParent(this);
	rightTree->setParent(this);

	strcpy(str, "left son of ");
	strcat(str, this->name());

	leftTree->setName(str);

	strcpy(str, "right son of ");
	strcat(str, this->name());

	rightTree->setName(str);

	leftTree->setParent(this);
	rightTree->setParent(this);

	if (root()==NULL)
	{
		setRoot(this);
		setParent(NULL);
	}
	/*
	else
	{
		leftTree->setRoot(root());
		rightTree->setRoot(root());
	}
	*/
}

void Tree::setIndex(const int number)
{
	index = number;
}

const int Tree::getIndex()
{
	return index;
}

const char* Tree::name()
{
	return pName;
}

void Tree::setName(const char *str)
{
	if (str!=NULL)
	{
		pName = (char *)malloc(strlen(str)+1);
		strcpy(pName, str);
	}
}

Tree::Tree()
{
	setIndex(treeCounter);
	treeCounter++;
	pLeft = NULL;
	pRight = NULL;
	pParent = NULL;
	pName = NULL;
	pKey = NULL;
	freq = 0;
	rank =0;
}

Tree::~Tree()
{
	if (pName!=NULL)
	{
		free(pName);
	}
	if (pKey!=NULL)
	{
		free(pKey);
	}
}

Tree* Tree::left()
{
	return pLeft;
}

Tree* Tree::right()
{
	return pRight;
}

Tree* Tree::parent()
{
	return pParent;
}

BinaryTree* BinaryTree::next()
{
	Tree* result = NULL;

	if (right()!=NULL)
	{
		result = right();
		while (result->left!=NULL)
		{
			result = result->left();
		}
	}
	else
	{
		if (parent()!= NULL)
		{
			result = this;
			while(result->parent()!=NULL&&result==result->parent()->right())
			{
				result = result->parent();
			}
		}
		//result = null
	}
	return (BinaryTree*)result;
}

BinaryTree* BinaryTree::prev()
{
	Tree* result = NULL;
	if (left()!=NULL)
	{
		result = left();
		while (result->right()!=NULL)
		{
			result = result->right();
		}
	}
	else
	{
		if (parent()!=NULL)
		{
			result = this;
			while (result->parent()!=NULL&&result==result->parent()->left())
			{
				result = result->parent();
			}
		}
	}
	return (BinaryTree*)result;
}