bstree.cpp

一个关于二叉树的查询 插入 删除 排序的小程序

// BSTree.cpp: implementation of the BSTree class.
//
//////////////////////////////////////////////////////////////////////
#include "stdafx.h"
//#include "WHBtree.h"
#include "BSTree.h"


#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

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

BSTree::BSTree()
{
    Root=NULL;
	
}

BSTree::~BSTree()
{

}

bool BSTree::Tree_Insert(int x)	
{
	if (Root == NULL)
	{
		Root = new Node(x);//为空则新建一个点
		if (Root == NULL)
		{
			::MessageBox(NULL, "不存在", "错误", MB_OK);
	    	return(FALSE);
		}
		Root->HighLight_node = false;
		return(1);
	}
	else
		return Insertnode(x, Root);
			
}

bool BSTree::Insertnode(int x, Node *T)
{
	if (x<T->getkey())               //和左孩子比较
	{
		if (T->getLeft() == NULL)
		{
			Node *Pd = new Node(x);
			if (Pd == NULL)
			{
				::MessageBox(NULL, "不存在", "错误", MB_OK);
				return(FALSE);
			}
			T->setLeft(Pd);
			Pd->setParent(T);
			Pd->HighLight_node =false; 
			return(1);
		}
		else
			return Insertnode(x,T->getLeft());
	}
	else if (x>T->getkey())               //和右孩子比较
	{
		if (T->getRight() == NULL)
		{
			Node *Pd = new Node(x);
			if (Pd == NULL)
			{
				::MessageBox(NULL, "不存在", "错误", MB_OK);
				return(FALSE);
			}
			T->setRight(Pd);
			Pd->setParent(T);
			Pd->HighLight_node = false;
			return(1);
		}
			  
		else
			return Insertnode(x,T->getRight());
	}
	else 
	{ 

	  ::MessageBox(NULL, "该节点已存在", "", MB_OK);
       T->HighLight_node = true;      //插入值已经存在树里并设置为高亮点
	 }
	return 0;
}

Node* BSTree::Tree_delete(int x,Node *root)   //树的删除函数
{
  Node *f,*p,*q,*s,*r;      //指针p 指向 要删除的结点
  p=NULL;
  f=root;
  s=NULL;
  r=NULL;
  q=root; 
  if(this->Root!=NULL)  this->Root->setParent(NULL);
  while(q!=NULL)                         //查找要删除的结点
  {
	  if(x==q->Key) {p=q;q=NULL;}
	  else 
	  { if(x<q->Key) {f=q;q=q->Leftchild;}
		  else {f=q;q=q->Rightchild;}
	  }
  }                                              //查找完毕
 if(p==NULL) 
 {
	 ::MessageBox(NULL, "the number you delete  doesn't  exists", " ", MB_OK);
	 return p;                  //没有找到
	 
 }

 if (p->Rightchild==NULL&&p->Leftchild==NULL)    
 {  
	 if (p==root)  {this->Root=NULL;}    
	 if (p==f->Leftchild)  {f->Leftchild=NULL;free(p);}
	else {f->Rightchild=NULL;free(p);}
 }
 else if(p->Rightchild==NULL&&p->Leftchild!=NULL)
 {    

	  if(p==root)  {this->Root=p->Leftchild;p->Leftchild->setParent(this->Root);}
	  if(p==f->Leftchild){f->Leftchild=p->Leftchild;q=p->Leftchild;q->setParent(f);free(p);}
      else  {f->Rightchild=p->Leftchild;q=p->Leftchild;q->setParent(f);free(p);}
  }
  else if(p->Rightchild!=NULL&&p->Leftchild==NULL)
  {   
	 
       if(p==root)  {this->Root=p->Rightchild;p->Rightchild->setParent(this->Root);}
       if(p==f->Leftchild) {f->Leftchild=p->Rightchild;q=p->Rightchild;q->setParent(f);free(p);}
	   else  {f->Rightchild=p->Rightchild;q=p->Rightchild;q->setParent(f);free(p);}
  }
  else 
  {
	  s=p->Leftchild;
	  if(s->Rightchild==NULL) 
	  {
		  p->Key=s->Key;
	      p->Leftchild=s->Leftchild;
	      q=s->Leftchild;
		  if (q!=NULL)  q->setParent(p);
	      free(s);
	  }
	  else
	  {
		  r=s->Rightchild;
		  while(r->Rightchild!=NULL) {s=r;r=r->Rightchild;}
		  p->Key=r->Key;
		  s->Rightchild=r->Leftchild;
          q=r->Leftchild;
		  if (q!=NULL) q->setParent(s);
		  free(r);
	  }

  }
 return 0;
}


bool BSTree::ResetColor(Node *T)//判断是否为高亮节点
{
	if (T != NULL)
	{
		T->HighLight_node = false;
		ResetColor(T->getLeft());
		ResetColor(T->getRight());
	}
	return TRUE;
}


Node * BSTree::Tree_Search(int x, Node *root)//节点的查找函数
{    Node *T;
     T=root;
	while((T!=NULL)&&(T->Key!=x))//所需节点的遍历
  {
   if(x<T->Key)
	{
     T=T->Leftchild;    
	}
   else
	{
     T=T->Rightchild;
	}
  }

  if(T==NULL)
	 {
	  int status=0;     
      status=AfxMessageBox("can't find the number ,do you want insert the number?",MB_YESNOCANCEL);
      if(status==IDCANCEL) // 在搜索不到时,判断是否插入此数值
		  return 0;
	  else if (status==IDYES)
	  { 
	    Tree_Insert(x);
		//Node *Pd = new Node(x);
       //Pd->HighLight_node=true;     试图将插入的点显示为高亮！！！失败！！！
	  }
      return T;
	 }
	else if(T->Key==x)  
	{ 
	T->HighLight_node=true;
    ::MessageBox(NULL, "find the number", " ", MB_OK);
	return T;
  }
 else return(0);	
}
 

void BSTree::draw_tree(CDC*g,Node *root)//画树（即节点和联线）
{ 
	if (g==NULL)
		return;
	if(Root==NULL)
		return;
    positiontree(20 ,15);
   draw_edge(g,root);
   draw_node(g,root);
}

void BSTree::draw_edge(CDC*g,Node *root)//画节点间的联线
{
	 CPen  pen;
	 pen.CreatePen(PS_SOLID,1,RGB(0,255,0));
	 if(root==NULL)  return; 
	 if (root->getParent()!=NULL)
	 {
		  g->MoveTo(root->x,root->y);
		  g->LineTo((root->getParent())->x,(root->getParent())->y);
	 }
	 	 
     draw_edge(g,root->getLeft());
     draw_edge(g,root->getRight());
     DeleteObject(&pen);
}

void BSTree::draw_node(CDC*g,Node *root)//用ＭＦＣ中函数画节点
{
     CPen  pen;
	 CBrush  brush1,brush2;
	 pen.CreatePen(PS_SOLID,1,RGB(0,255,0));
	 brush1.CreateSolidBrush(RGB(255,255,0));
	 brush2.CreateSolidBrush(RGB(255,0,0));

	 if(root==NULL)  return;	
	 if(root->HighLight_node==false)    
	 {	 
	  g->SelectObject(&brush1);
	  g->Ellipse(root->x-15,root->y-15,root->x+15,root->y+15);
      DeleteObject(&brush1);
	 }
    else 
	 {
	  g->SelectObject(&brush2);
	  g->Ellipse(root->x-15,root->y-15,root->x+15,root->y+15);
      DeleteObject(&brush2);
	 }
	 CPen *pOldPen=g->SelectObject(&pen);
	 CString t;
	 t.Format("%.0lf",root->Key);
	 g->TextOut(root->x-8,root->y-8,t);     
	 g->SelectObject(pOldPen);	 
     draw_node(g,root->getLeft());
     draw_node(g,root->getRight());
     DeleteObject(&pen);	
}

void BSTree::positiontree( int upper, int left )
{
	position_tree( Root, upper, left );
}

int BSTree::position_tree( Node *root, int upper, int left )
{
	int l_width, r_width;
    NODE_HEIGHT=20;
	NODE_WIDTH=30;
	if (root == NULL)
		return 0;
	l_width = position_tree( root->getLeft(), upper + NODE_HEIGHT, left );
	root->x = left  + l_width + NODE_WIDTH/2;
	root->y = upper + NODE_HEIGHT;
	r_width = position_tree( root->getRight(), upper + NODE_HEIGHT,
			 root->x + NODE_WIDTH/2 );
	return l_width + NODE_WIDTH + r_width;
}