?? 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;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -