Chương trình C ++ để tìm kiếm phần tử trong cây tìm kiếm nhị phân

Trong chương trình này, chúng ta cần. Thực hiện tìm kiếm nhị phân để tìm sự tồn tại của một chuỗi tìm kiếm trong cây tìm kiếm nhị phân. Độ phức tạp thời gian trong trường hợp xấu nhất của tìm kiếm nhị phân là O (n) nhưng đối với trường hợp trung bình là O (log (n)).

Thuật toán

Begin
   Construct binary search tree for the given unsorted data array by inserting data into tree one by one.
   Take the input of data to be searched in the BST.
   Now starting from the root node, compare the data with data part of the node.
   if data < temp->d, move the temp pointer to the left child.
   if data > temp->d move the temp pointer to the right child.
   if data = temp->d print the tree depth where it is found and return to main.
   Else print item not found.
End

Mã mẫu

#include<iostream>
using namespace std;
struct node {
   int d;
   node *left;
   node *right;
};
node* CreateNode(int d) {
   node *newnode = new node;
   newnode->d = d;
   newnode->left = NULL;
   newnode->right = NULL;
   return newnode;
}
node* InsertIntoTree(node* root, int d) {
   node *temp = CreateNode(d);
   node *t = new node;
   t = root;
   if(root == NULL)
      root = temp;
   else {
      while(t != NULL) {
         if(t->d < d) {
            if(t->right == NULL) {
               t->right = temp;
               break;
            }
            t = t->right;
         } else if(t->d > d) {
            if(t->left == NULL) {
               t->left = temp;
               break;
            }
            t = t->left;
         }
      }
   }
   return root;
}
void Search(node *root, int d) {
   int depth = 0;
   node *temp = new node;
   temp = root;
   while(temp != NULL) {
      depth++;
      if(temp->d == d) {
         cout<<"\nitem found at depth: "<<depth;
         return;
      } else if(temp->d > d)
         temp = temp->left;
         else
            temp = temp->right;
   }
   cout<<"\n item not found";
   return;
}
int main() {
   char ch;
   int n, i, a[10] = {93, 53, 45, 2, 7, 67, 32, 26, 71, 76};
   node *root = new node;
   root = NULL;
   for (i = 0; i < 10; i++)
      root = InsertIntoTree(root, a[i]);
   up:
   cout<<"\nEnter the Element to be searched: ";
   cin>>n;
   Search(root, n);
   cout<<"\n\n\tDo you want to search more...enter choice(y/n)?";
   cin>>ch;
   if(c == 'y' || c == 'Y')
      goto up;
   return 0;
}

Đầu ra

Enter the Element to be searched: 26
item found at depth: 7
Do you want to search more...enter choice(y/n)?
Enter the Element to be searched: 1
item not found
Do you want to search more...enter choice(y/n)?