#include“BinTree.h“
void?BinTree::Insert（BinTreeNode?*?rootint?val）
	{
		BinTreeNode?*p=root*q=p;
		BinTreeNode?*node=new?BinTreeNode（valNULLNULL）;
		while（p!=NULL）
		{
			q=p;
			if（p->key				p=p->right;
			else
				p=p->left;
		}
		if（q->key<=val）
			{
				q->right=node;
			}	
		else?
			{
				q->left=node;
			}
	}
	
BinTreeNode?*?BinTree::CreateBinTree?（int?*aint?len）
{

	cout<<“CreateBinTree?start!“<	BinTreeNode?*root;//*p*q;
	root=new?BinTreeNode;
	//p=root;q=root;
	if（root->key==-1）
	{
		BinTreeNode?*node=new?BinTreeNode（a[0]NULLNULL）;
		root=node;
	}
	else
		Insert（roota[0]）;
	for（int?i=1;i	{
		Insert（roota[i]）;
		
		
	}
	cout<<“Create?over“<	return?root;
}
int?BinTree::GetMiniMum（BinTreeNode?*?root）
{
	BinTreeNode?*p=root;
	while（p->left!=NULL）
	{
		p=p->left;
	}
	return?p->key;
}
BinTreeNode?*?BinTree::GetMiniNode（BinTreeNode?*?root）
{
	BinTreeNode?*p=root;
	while（p->left!=NULL）
	{
		p=p->left;
	}
	return?p;
}

int?BinTree::GetMaxiMum（BinTreeNode?*root）
{
	BinTreeNode?*p=root*q=p;
	while（p!=NULL）
	{
		q=p;
		p=p->right;
	}
	return?q->key;
}
BinTreeNode?*BinTree::GetMaxiNode（BinTreeNode?*root）
{
	BinTreeNode?*p=root*q=p;
	while（p!=NULL）
	{
		q=p;
		p=p->right;
	}
	return?q;
}
int?BinTree::GetHeight（BinTreeNode?*root）
{
	//BinTreeNode?*p=root;
	if（root==NULL）
		return?0;
	else?
	{
		int?lh=GetHeight（root->left?）;
		int?rh=GetHeight（root->right?）;
		return?1+（lh>rh?lh:rh）;
	}
}
void?BinTree::InOrder（BinTreeNode?*root）
{
	if（root!=NULL）
	{
		InOrder（root->left?）;
		cout<key?<<“	“;
		InOrder（root->right）;
	}
}
BinTreeNode?*??BinTree::Search（BinTreeNode?*?rootint?key）
{
	BinTreeNode?*p=root;
	while（p!=NULL&&p->key!=key）
	{
		if（p->key?			p=p->right?;
		else?
			p=p->left?;

	}
	return?p;
	/*if（p==NULL）
		return?0;
	else?
		return?1;*/
}
BinTreeNode?*?BinTree::ParentNode（BinTreeNode?*?rootBinTreeNode?*node）
{
	BinTreeNode?*p=root*q=p;
	if（node->key==root->key）
		{
			q=NULL;	
		}
	else
	{
		while（p!=NULL&&（p->key）!=（node->key））
		{
			q=p;
			if（p->key<=node->key）
				p=p->right;
			else?
				p=p->left?;
		}
		
	}
	//cout<key<	return?q;
}
BinTreeNode?*?BinTree::Sucessor（BinTreeNode?*?rootBinTreeNode?*node）
{
	if（node->right!=NULL）
	{
		return?GetMiniNode（node->right?）;
	}
	else
	{
		//int?num=1;
		BinTreeNode?*p=node*q;
		q=ParentNode（rootp）;
	//	cout<key<		//cout<<“wile?will?be?call“<		while（q!=NULL&&q->left!=p）
			{
				p=q;
				q=ParentNode（rootp）;
				//cout<				//cout<key?<			}
		return?q;
	}
}
BinTreeNode?*?BinTree::Sucessor（BinTreeNode?*?rootint?key）
{
	BinTreeNode?*node=Search（rootkey）;
	if（node->right!=NULL）
	{
		return?GetMiniNode（node->right?）;
	}
	else
	{
		//int?num=1;
		BinTreeNode?*p=node*q;
		q=ParentNode（rootp）;
	//	cout<