二元樹

遞迴 非遞迴 搜尋 新增 大量新增

遞迴 輸出

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

#include <vcl.h>
#pragma hdrstop

#include "Unit1.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
        : TForm(Owner)
{
        srand(time(NULL));
}
//---------------------------------------------------------------------------

String out;//final output with recursive

struct BTreeNode{
        struct BTreeNode *leftchild;
        int data;
        struct BTreeNode *rightchild;
};//define tree node

struct BTreeNode *root;//tree root with recursive
struct BTreeNode *rootNR;//tree root with non-recursive

struct BTreeNode* insert(int x){
        struct BTreeNode *node=new struct BTreeNode;
        node->data=x;
        node->leftchild=NULL;
        node->rightchild=NULL;
        return node;
}//build new child and place number;

struct BTreeNode* placeNode(struct BTreeNode *node,int x){
        if(node==NULL){
                return insert(x);
        }
        if(x<node->data){
                node->leftchild=placeNode(node->leftchild,x);
        }else{
                node->rightchild=placeNode(node->rightchild,x);
        }
        return node;
}//find the place where new child should be;
//recursive

void placeNodeNR(int x){
        struct BTreeNode *u, *r;
        u=rootNR;
        r=NULL;
        while(u!=NULL){
                r=u;
                if(x<u->data){
                        u=u->leftchild;
                }else{
                        u=u->rightchild;
                }
        }
        u=insert(x);
        if(rootNR==NULL){
                rootNR=u;
        }else if(x<r->data){
                        r->leftchild=u;
                }else{
                        r->rightchild=u;
                }
}//find the place where new child should be;
//non-recursive

void showTree(struct BTreeNode *node){
        if(node!=NULL){
                showTree(node->leftchild);
                out+=IntToStr(node->data)+"_";
                showTree(node->rightchild);
        }
}//LVR print the child from left to right(small to large number)
//recursive

int searchTree(struct BTreeNode *node,int x){
        if(node==NULL){
                return 0;
        }
        if(x==node->data){
                return 1;
        }
        if(x<node->data){
                return searchTree(node->leftchild,x);
        }else{
                return searchTree(node->rightchild,x);
        }
}//searching data in tree with recursive

int searchTreeNR(struct BTreeNode *node,int x){
        while(node!=NULL){
                if(x==node->data){
                       return 1;
                }
                if(x<node->data){
                        node=node->leftchild;
                }else{
                        node=node->rightchild;
                }
        }
        return 0;
}//searching data in tree with non-recursive
//---------------------------------------------------------------------------

void __fastcall TForm1::Button1Click(TObject *Sender)
{
        Memo1->Clear();
        out="";
        root=placeNode(root,StrToInt(Edit1->Text));
        showTree(root);
        Memo1->Lines->Add(out);
}//join a new child into tree
//recursive
//---------------------------------------------------------------------------

void __fastcall TForm1::Button2Click(TObject *Sender)
{
        Memo1->Clear();
        out="";
        for(int i=0; i<StrToInt(Edit2->Text); i++){
                root=placeNode(root,rand()%StrToInt(Edit3->Text)+1);
        }
        showTree(root);
        Memo1->Lines->Add(out);
}//join random child into two trees several times
//recursive
//---------------------------------------------------------------------------

void __fastcall TForm1::Button3Click(TObject *Sender)
{
        Memo2->Clear();
        out="";
        placeNodeNR(StrToInt(Edit1->Text));
        showTree(rootNR);
        Memo2->Lines->Add(out);
}//join a new child into tree
//non-recursive
//---------------------------------------------------------------------------

void __fastcall TForm1::Button4Click(TObject *Sender)
{
        Memo2->Clear();
        out="";
        for(int i=0; i<StrToInt(Edit2->Text); i++){
                placeNodeNR(rand()%StrToInt(Edit3->Text)+1);
        }
        showTree(rootNR);
        Memo2->Lines->Add(out);
}//join random child into two trees several times
//non-recursive
//---------------------------------------------------------------------------

void __fastcall TForm1::Button6Click(TObject *Sender)
{
        String ans;
        int target=StrToInt(Edit4->Text);
        if(searchTree(root,target)){
                ans="got "+IntToStr(target)+" in tree of recursive";
        }else{
                ans="can't find "+IntToStr(target)+" in tree of recursive";
        }
        Memo1->Lines->Add(ans);
        if(searchTree(rootNR,target)){
                ans="got "+IntToStr(target)+" in tree of non-recursive";
        }else{
                ans="can't find "+IntToStr(target)+" in tree of non-recursive";
        }
        Memo2->Lines->Add(ans);
}//search data in both tree with calling recursive function
//---------------------------------------------------------------------------

void __fastcall TForm1::Button5Click(TObject *Sender)
{
        String ans;
        int target=StrToInt(Edit4->Text);
        if(searchTreeNR(root,target)){
                ans="got "+IntToStr(target)+" in tree of recursive";
        }else{
                ans="can't find "+IntToStr(target)+" in tree of recursive";
        }
        Memo1->Lines->Add(ans);
        if(searchTreeNR(rootNR,target)){
                ans="got "+IntToStr(target)+" in tree of non-recursive";
        }else{
                ans="can't find "+IntToStr(target)+" in tree of non-recursive";
        }
        Memo2->Lines->Add(ans);
}//search data in both tree with calling non-recursive function
//---------------------------------------------------------------------------