سورس درخت جستجوی دودویی (BST) به زبان C++

پنجشنبه ۱ اسفند ۱۳۹۸
بازدید ۲,۶۳۴ نفر
آرتین
(10 امتیاز از 2 رای)
Loading...

تصویر binary-search-tree-in-cpp_8171 سورس درخت جستجوی دودویی (BST) به زبان C++

سورس درخت جستجوی دودویی با زبان C++

در این بخش سورس درخت جستجوی دودویی با زبان C++ را برای شما آماده کرده ایم که در محیط نرم افزار Code::Blocks و زبان برنامه نویسی سی پلاس پلاس نوشته شده است. در ادامه می توانید توضیحات، تصاویر و همچنین فیلمی از نحوه اجرا شدن پروژه را مشاهده کنید.

توضیحات پروژه

BST یا همان Binary Search Tree یک درخت باینری با ترتیب متقارن است. منظور از ترتیب متقارن این است که هر گره شامل یک کلید است. کلید هر گره کوچکتر از کلید گره زیر درخت سمت راست و بزرگتر از کلید گره زیر درخت سمت چپ است. درخت جستجوی باینری با نام Sorted/Ordered Binary Tree نیز شناخته می شود. عملیاتی که می توان بر روی درخت جستجوی باینری انجام داد عبارت اند از:

Insert : افزودن یک گره جدید به درخت
Delete : حذف یک گره موجود از درخت
Search : جستجوی کلید یک گره در درخت
Traverse : به معنای پیماش گره های یک درخت است. یک درخت باینری را می توان در سه حالت per-order، in-order و post-order پیمایش کرد. برای درخت جستجوی باینری از پیمایش in-order استفاده می شود.

در این پروژه بعد از اجرا شدن برنامه یک منوی 9 گزینه ای شامل موارد زیر به کاربر نمایش داده می شود و کاربر با استفاده از آن ها با BST کار کند.

Insert
Delete
Make Empty
Find Minimum
Find Maximum
Search
Print Ascending
Print Descending
Exit

در لیست فوق گزینه اول برای افزودن یک گره به BST، گزینه دوم برای حذف یک گره، گزینه سوم برای خالی کردن BST، گزینه چهارم و پنجم برای پیدا کردن کوچکترین و بزرگترین عنصر، گزینه ششم برای جستجو، گزینه هفتم و هشتم برای نمایش BST با ترتیب صعودی و نزولی و گزینه آخر هم برای خروج از برنامه استفاده می شود.

قسمت های از سورس کد

#include <iostream>
#include <cstdlib>
#include <conio.h>
using namespace std;
struct node {
  int info;
  struct node* right;
  struct node* left;
};
typedef struct node* BST;
typedef struct node node;
main()
{
  BST tree, pos;
  char ans;
  int val;
  tree = NULL;
  while (true) {
    cout << " Binary Search Tree (BST)" << endl << endl;
    cout << "[1].tInsert" << endl;
    cout << "[2].tDelete" << endl;
    cout << "[3].tMake Empty" << endl;
    cout << "[4].tFind Minimum" << endl;
    cout << "[5].tFind Maximum" << endl;
    cout << "[6].tSearch" << endl;
    cout << "[7].tPrint Ascending" << endl;
    cout << "[8].tPrint Descending" << endl;
    cout << "[9].tExit" << endl << endl;
    cout << "Enter Choice:" << endl;
    ans = getche();
    switch (ans)
    {
      case '1':
      {
        cout << endl << "Enter Value: ";
        cin >> val;
        tree = insertnode(tree, val);
      }
      break;
      case '2':
      {
        if (tree != NULL) {
            cout << endl << "Enter Value to be Deleted: ";
            cin >> val;
            tree = deletenode(tree, val);
        }
        else
            cout << endl << "Cannot Delete!! Empty BST!!";
        getch();
      }
      break;
      case '3':
      {
        tree = makeempty(tree);
        cout << endl << "BST is now Empty!!";
        getch();
      }
      break;
      case '4':
      {
        pos = findmin(tree);
        if (pos != NULL)
            cout << endl << "Minimum Value: " << pos->info;
        else
            cout << endl << "Empty BST!! No Minimum Value.";
        getch();
      }
      break;
      case '5':
      {
        pos = findmax(tree);
        if (pos != NULL)
            cout << endl << "Maximum Value: " << pos->info;
        else
            cout << endl << "Empty BST!! No Maximum Value.";
        getch();
      }
      break;
      case '6':
      {
        if (tree != NULL) {
            cout << endl << "Enter Value to be Searched: ";
            cin >> val;
            pos = find(tree, val);
            if (pos != NULL)
                cout << endl << pos->info << " is found in the BST";
            else
                cout << endl << pos->info << " not found in the BST";
        }
        else {
            cout << endl << "The BST is Empty!!";
        }

        getch();
      }
      break;
      case '7':
      {
        if (tree != NULL) {
          system("cls");
          cout << endl << "BST IN ASCENDING ORDER" << endl << endl;
          printtree_asc(tree);
        }

        else
          cout << endl << "The BST is Empty!!";
        getch();
      }
      break;
      case '8':
      {
        if (tree != NULL) {
            system("cls");
            cout << endl << "BST IN DESCENDING ORDER" << endl << endl;
            printtree_desc(tree);
        }

        else
          cout << endl << "The BST is Empty!!";
        getch();
      }
      break;
      case '9':
        exit(0);
      default:
      {
            cout << endl << endl << "Choose from 1 to 9 only!!";
            getch();
      }
      break;
    }

    system("cls");
  }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

#include <iostream>

#include <cstdlib>

#include <conio.h>

using namespace std;

struct node {

int info;

struct node* right;

struct node* left;

};

typedef struct node* BST;

typedef struct node node;

main()

{

BST tree, pos;

char ans;

int val;

tree = NULL;

while (true) {

cout << " Binary Search Tree (BST)" << endl << endl;

cout << "[1].tInsert" << endl;

cout << "[2].tDelete" << endl;

cout << "[3].tMake Empty" << endl;

cout << "[4].tFind Minimum" << endl;

cout << "[5].tFind Maximum" << endl;

cout << "[6].tSearch" << endl;

cout << "[7].tPrint Ascending" << endl;

cout << "[8].tPrint Descending" << endl;

cout << "[9].tExit" << endl << endl;

cout << "Enter Choice:" << endl;

ans = getche();

switch (ans)

{

case '1':

{

cout << endl << "Enter Value: ";

cin >> val;

tree = insertnode(tree, val);

}

break;

case '2':

{

if (tree != NULL) {

cout << endl << "Enter Value to be Deleted: ";

cin >> val;

tree = deletenode(tree, val);

}

else

cout << endl << "Cannot Delete!! Empty BST!!";

getch();

}

break;

case '3':

{

tree = makeempty(tree);

cout << endl << "BST is now Empty!!";

getch();

}

break;

case '4':

{

pos = findmin(tree);

if (pos != NULL)

cout << endl << "Minimum Value: " << pos->info;

else

cout << endl << "Empty BST!! No Minimum Value.";

getch();

}

break;

case '5':

{

pos = findmax(tree);

if (pos != NULL)

cout << endl << "Maximum Value: " << pos->info;

else

cout << endl << "Empty BST!! No Maximum Value.";

getch();

}

break;

case '6':

{

if (tree != NULL) {

cout << endl << "Enter Value to be Searched: ";

cin >> val;

pos = find(tree, val);

if (pos != NULL)

cout << endl << pos->info << " is found in the BST";

else

cout << endl << pos->info << " not found in the BST";

}

else {

cout << endl << "The BST is Empty!!";

}

getch();

}

break;

case '7':

{

if (tree != NULL) {

system("cls");

cout << endl << "BST IN ASCENDING ORDER" << endl << endl;

printtree_asc(tree);

}

else

cout << endl << "The BST is Empty!!";

getch();

}

break;

case '8':

{

if (tree != NULL) {

system("cls");

cout << endl << "BST IN DESCENDING ORDER" << endl << endl;

printtree_desc(tree);

}

else

cout << endl << "The BST is Empty!!";

getch();

}

break;

case '9':

exit(0);

default:

{

cout << endl << endl << "Choose from 1 to 9 only!!";

getch();

}

break;

}

system("cls");

}

تصاویری از خروجی

دسته ها: زبان برنامه نویسی C++ - سورس کدها

آموزش هوش مصنوعی و الگوریتم های فراابتکاری با پایتون

آموزش برنامه نویسی PHP از مقدماتی تا پیشرفته (فیلم آموزشی)

فیلم آموزش PHP به صورت مقدماتی به زبان فارسی

آموزش زبان برنامه نویسی R به صورت فیلم | دوره مقدماتی

آموزش CSS به زبان ساده در قالب فیلم | دوره مقدماتی

آموزش HTML به زبان ساده در قالب فیلم | دوره مقدماتی

فیلم آموزش درس ساختمان داده ها به زبان فارسی

سورس درخت جستجوی دودویی (BST) به زبان C++

سورس درخت جستجوی دودویی با زبان C++

توضیحات پروژه

قسمت های از سورس کد