이진 검색을 사용하여 배열에서 최대 요소를 찾는 C++ 프로그램

이진 탐색 트리를 사용하여 배열의 최대 요소를 찾는 C++ 프로그램입니다. 이 프로그램의 시간 복잡도는 O(log(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

예시 코드

#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;
}

출력

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.