Chương trình C ++ để tìm phần tử tối đa trong một mảng bằng cách sử dụng tìm kiếm nhị phân

Đây là một Chương trình C ++ để tìm phần tử tối đa của một mảng bằng cách sử dụng Cây tìm kiếm nhị phân. Độ phức tạp về thời gian của chương trình này là O (log (n)).

Thuật toán

Begin
   Construct the Binary Search Tree using the given data elements.
   Next traverse the root pointer to the rightmost child node available.
   Print the data part of the node as the maximum data element of the given data set.
   Print the Depth of the maximum data.
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;
}
int main() {
   int n, i, a[10] = {86, 63, 95, 6, 7, 67, 52, 26, 45, 98};
   node *root = new node;
   root = NULL;
   cout<<"\nData set:\n";
   for(i = 0; i < 10; i++) {
      cout<<a[i]<<" ";
      root = InsertIntoTree(root, a[i]);
   }
   cout<<"\n\nThe maximum element of the given data set is\n ";
   i = 0;
   while(root->right != NULL) {
      i++;
      root = root->right;
   }
   cout<<root->d<<"\n"<<"data found at "<<i<<" depth from the root.";
   return 0;
}

Đầu ra

Data set:
86 63 95 6 7 67 52 26 45 98
The maximum element of the given data set is
98
data found at 2 depth from the root.