treenode.cpp

二叉树的生成、查询、删除、插入等基本操作

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

#include "stdafx.h"
#include "Tree.h"
#include "TreeNode.h"

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

extern CRect rect;
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
TreeNode::~TreeNode()
{
}

TreeNode * TreeNode::getLeft()
{
	return left;
}
TreeNode * TreeNode::getRight()
{
	return right;
}

 BSTree::BSTree(TreeNode*&root)
 {
	 root=NULL;

 }

 BSTree::~BSTree()
 {
	 
 }


 void BSTree::DeleteBSTree(TreeNode*&root)
 {
	 if (root==NULL) return;
	 if (root->left!=NULL)
		 DeleteBSTree(root->left);
	 if  (root->right!=NULL)
		 DeleteBSTree(root->right);
	 free(root);
 }

void BSTree::BSTreeDelete(TreeNode*&root,int item)
 {
	TreeNode *t,*p,*r,*pr;
	t=root;
	p=NULL;
	while(t!=NULL)
	{
		if(item==t->data)
			break;
		else
		{
			p=t;
			if(item<t->data)
				t=t->left;
			else
				t=t->right;
		}
	}
	if(t==NULL)	return;
	if(t->left==NULL)
	{
		if(p==NULL)
			root=t->right;
		else if(p->left==t)
			p->left=t->right;
		else
			p->right=t->right;
		free(t);
	}
	else
	{
		pr=t;
		r=t->left;
		while(r->right!=NULL)
		{
			pr=r;
			r=r->right;
		}
		t->data=r->data;
		if(pr==t)
			pr->left=r->left;
		else
			pr->right=r->left;
		free(r);
	}
 
 }

bool BSTree::BSTreeEmpty(TreeNode *&root)
{
	if (root==NULL) return true;
	else
		return false;
}

TreeNode *BSTree::BSTreeLocate(TreeNode*&root,int item)
{
	TreeNode * t;
	t=root;
	while (t!=NULL)
	{
		if (t->data==item) 
		{
			break;
		}
		else if (item<t->data)
		{
			t=t->left;
		}
		else
		{
			t=t->right;
		 }
	}
	return t;
} 



bool BSTree::SetColor(TreeNode *T)
{
	if (T!=NULL)
	{
		T->hightlight=false;
		SetColor(T->left);
		SetColor(T->right);
	}
	return true;

}

void BSTree::Inorder(TreeNode*&root,int x0,int y0,int & value)
{
	TreeNode * t;
	t=root;
	if (t!=NULL)
	{
		
		if (abs(t->x-x0)<=15&&abs(t->y-y0)<=15)
		{
			t->hightlight=true;
			value=t->data;
			
		}
		Inorder(t->left,x0,y0, value);
		if ((t->left!=NULL)&&abs(t->left->x-x0)<=15&&abs(t->left->y-y0)<=15)
		{
			t->left->hightlight=true;
			value=t->left->data;
		}
		
		Inorder(t->right,x0,y0,value);
		if ((t->right!=NULL)&&abs(t->right->x-x0)<=15 && abs(t->right->y-y0)<=15)
		{
			t->right->hightlight=true;
			value=t->right->data;
		}
	}
}

void BSTree::BSTreeInsert(TreeNode*&root,int item)
{   
	TreeNode*t,*p,*newN;
	newN=new TreeNode;
	newN->data=item;
	if(root==NULL)
	{
		root=newN;
		
		return;
	}
	t=root;
	p=NULL;
	while(t!=NULL)
	{
		p=t;
		if(item<t->data)
			t=t->left;
		else
			t=t->right;
	}
	if(item<p->data)
	{
		p->left=newN;
		p->hightlight=false;
	}
	else
	{
		p->right=newN;
		p->hightlight=false;
	}

	
}

void BSTree::TreeNodePosition(TreeNode * &root)
{
	TreeNode_Position(rect.Height()/10, rect.Width()/5,root);

}

void BSTree::DrawBSTree(CDC *pDC,TreeNode * &root)
{
	Draw_BSTree(pDC,root);
}


int TreeNode_Position(int upperwidth,int  leftwidth, TreeNode *T)
{
	int rWidth,lWidth;
	if (T==NULL) return 0;
	lWidth=TreeNode_Position(upperwidth+TreeNodeheight,leftwidth,T->getLeft());
	T->x = leftwidth + lWidth + TreeNodewidth/2;
	T->y = upperwidth+TreeNodeheight;
	rWidth=TreeNode_Position(upperwidth+TreeNodeheight,T->x+TreeNodewidth/2,T->getRight());
	return rWidth+lWidth+TreeNodewidth;
}

void Draw_BSTree(CDC *pDC,TreeNode *T)
{
	if (T==NULL) return ;
	CString str;
	str.Format("%d", T->data);
	COLORREF TreeNodeColor;
	COLORREF TreeLineColor;
	COLORREF HightColor;
	COLORREF ChangColor;

	TEXTMETRIC tm;
	
	TreeNodeColor=RGB(0,255,0);
	TreeLineColor=RGB(255,0,0);
	HightColor=RGB(0,0,255);
	ChangColor=RGB(255,255,0);

	pDC->GetTextMetrics(&tm);
	CSize sz=pDC->GetTextExtent(str);

	CPen  PenNew,*pPenOld;
	PenNew.CreatePen(PS_SOLID,1,TreeLineColor);
	pPenOld = pDC->SelectObject(&PenNew);
	
	CBrush  pBrush,HightBrush,*pOldBrush;
	pBrush.CreateSolidBrush(TreeNodeColor);
	HightBrush.CreateSolidBrush(HightColor);
	
	if (T->hightlight)
	{
		pOldBrush = pDC->SelectObject(&HightBrush);
	}
	else
	{
		pOldBrush = pDC->SelectObject(&pBrush);
	}
	
	
	pDC->MoveTo(T->x,T->y);
	if (T->getLeft()!=NULL)
		pDC->LineTo(T->getLeft()->x,T->getLeft()->y);
	
	
	pDC->MoveTo(T->x,T->y);
	if (T->getRight()!=NULL)
		pDC->LineTo(T->getRight()->x,T->getRight()->y);

	
    CRect rect(T->x-TreeNodewidth/2,T->y-TreeNodeheight/2,T->x+TreeNodewidth/2, T->y+TreeNodeheight/2);
	
    pDC->Ellipse(rect);
	pDC->SetBkMode(TRANSPARENT);
	
	
	pDC->TextOut(T->x-sz.cx/2,T->y-tm.tmHeight/2,str);
	
	Draw_BSTree(pDC,T->getLeft());
	Draw_BSTree(pDC,T->getRight());
	
	pDC->SelectObject(pPenOld);
	pDC->SelectObject(pOldBrush);
	PenNew.DeleteObject();
	pBrush.DeleteObject();
}