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.