//---------------------------------------------------------------------------

#include <vcl.h>
#pragma hdrstop
#include <math.h>
#include "cd5_3u.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
class bntree;

class node        //結(jié)點類
{
   public:
      int data;
      node* left;                                //左子樹指針
      node* right;                               //右子樹指針
      node():data(0),left(NULL),right(NULL){}    //結(jié)點構(gòu)建時的設(shè)置
      getdata(){return data;}                     //取得結(jié)點內(nèi)容
};

class bntree                           	//二叉樹類
{
   public:
      void insert(int da,int *lv,int *d)           //安插一個新結(jié)點的函數(shù)
      {
         node* newnode=new node;           //產(chǎn)生新結(jié)點
         newnode->data=da;
         if(root==NULL)           //如果二叉樹為空，建立根結(jié)點
            root=newnode;
         else
         {
            node* P=root;
            node* F;
            while(1)                          //自動循環(huán)直到return為止
            {
               *d=(*d)+1;                   //用指針傳遞函數(shù)間的d值
               F=P;
               if(da < (P->data))           //新加入的值小于目前結(jié)點值
               {
                  *lv=(*lv)*2;              //用指針傳遞函數(shù)間的lv值
                  P=P->left;
                  if(P==NULL)         //若此結(jié)點無數(shù)據(jù),新值設(shè)置在此并跳出循環(huán)
                  {
                     F->left=newnode;
                     return ;
                  }
               }
               else                      //新加入的值小于當(dāng)前結(jié)點值
               {
                  *lv=(*lv)*2+1;
                  P=P->right;
                  if(P==NULL)
                  {
                     F->right=newnode;
                     return ;
                  }
               }
            }
         }
      }
      int find(int k,int l)               //搜尋樹中結(jié)點位置的函數(shù)
      {
         node* P=root;
         while(P->getdata()!=k)            //當(dāng)前結(jié)點數(shù)據(jù)不等于搜尋值時運行
         {
            if(k<P->data)                //當(dāng)搜尋值小于當(dāng)前數(shù)據(jù)時往左子結(jié)點移動
            {
               P=P->left;
               l=l*2;
            }
            else
            {
               P=P->right;
               l=l*2+1;
            }
            if(P==NULL)                   //找不到要搜尋的結(jié)點返回0
               return 0;
         }
         return l;                      //返回搜索成功的結(jié)點位置
      }
      void droot(){clear(root);}        //用連續(xù)調(diào)用遞歸的方式清除所有結(jié)點
      void clear(node* T)               //清除二叉樹結(jié)點
      {
         if(T!=NULL)
         {
            clear(T->left);       //不斷調(diào)用清除函數(shù)以尋找端點
            clear(T->right);      //清除該端的葉子結(jié)點
            delete T;
         }
      }
   private:
      node* root;
};
bntree tree;              //新建立一個bntree類別,名稱為tree
int dat,l,timer=0;
int i;
TShape *sp[32];  //為取得運行時所構(gòu)建的對象,所以將其聲明為數(shù)組以便索引
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
        : TForm(Owner)
{
}
//---------------------------------------------------------------------------
void create(int lv,int d,int da)      //構(gòu)建窗體顯示控件的函數(shù)
{
   static int p[16];

   TColor color[5]={clWhite,clYellow,clLime,clBlue,clRed};
   sp[lv]=new TShape(Form1);        //構(gòu)建的結(jié)點控件形體
   sp[lv]->Parent=Form1->pn;
   sp[lv]->Height=20;
   sp[lv]->Width=30;

   TLabel *lb;                  //構(gòu)建結(jié)點控件內(nèi)容表示
   lb=new TLabel(Form1);
   lb->Parent=Form1->pn;
   lb->Height=20;
   lb->Width=30;
   lb->Transparent=true;
   lb->Caption=IntToStr(da);

   sp[lv]->Top=20+d*35;
   lb->Top=24+d*35;

   if(d==0)                   //取得結(jié)點左端座標(biāo)
   {
      sp[lv]->Left=175;
      lb->Left=185;
   }
   else
   {
      sp[lv]->Left=175-d*40+(d*80/(pow(2,d)-1)*(lv-(pow(2,d))));
      lb->Left=185-d*40+(d*80/(pow(2,d)-1)*(lv-(pow(2,d))));

      Form1->img->Canvas->MoveTo(p[lv/2],35+(d-1)*35);      //構(gòu)建結(jié)點連接線段
      Form1->img->Canvas->LineTo((sp[lv]->Left)+15,(sp[lv]->Top)+15);
   }

   sp[lv]->Shape=stEllipse;
   sp[lv]->Brush->Color=color[d];         //結(jié)點顏色根據(jù)所在層而變化

   if(lv<16)
      p[lv]=(sp[lv]->Left)+15;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button3Click(TObject *Sender)   	//增加新結(jié)點
{
   int lv=1,d=0;                          //設(shè)置深度及位置的初始值
   dat=StrToInt(ein->Text);
   tree.insert(dat,&lv,&d);    //調(diào)用安插新結(jié)點的函數(shù)
   ein->Text="";
   if(d<5)
      create(lv,d,dat);        //調(diào)用生成窗體顯示控件的函數(shù)
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button5Click(TObject *Sender)     //關(guān)閉程序并清除結(jié)點
{
   tree.droot();
   Close();
}
//---------------------------------------------------------------------------
void fnode(int l)
{
   sp[l]->Shape=stRoundRect;            //將找到的結(jié)點形狀改為圓角方形
}
//---------------------------------------------------------------------------

void __fastcall TForm1::Button2Click(TObject *Sender)       //搜尋二叉樹結(jié)點
{
   int key;
   l=1;
   key=StrToInt(ein->Text);
   l=tree.find(key,l);                //調(diào)用搜索函數(shù),并將值返回給l
            //函數(shù)返回一個值可直接傳遞,若欲返回兩個以上則可用適當(dāng)?shù)淖兞炕蛑羔?   if(l==0)
      ShowMessage("找不到"+IntToStr(key)+" 這個數(shù)");
   else
   {
      fnode(l);           //將找到的結(jié)點變形
      timer=1;           //使找到的結(jié)點閃爍
   }
   ein->Text="";
}
//---------------------------------------------------------------------------

void __fastcall TForm1::Timer1Timer(TObject *Sender)
{                                       //熟悉計數(shù)器的使用有助于動畫及效果的表現(xiàn)
   static int t=0;
   if(timer==1)
   {
      if(t%2==0)                       //鎖定結(jié)點使其閃爍
         sp[l]->Visible=false;
      else
         sp[l]->Visible=true;
      t++;
      if(t>20)                          //結(jié)束計數(shù)器并將形狀還原
      {
        timer=0;                          //還原搜尋結(jié)果變化
        sp[l]->Shape=stEllipse;
        t=0;
      }
   }
}
//---------------------------------------------------------------------------