Data Structure
Networking
RDBMS
Operating System
Java
MS Excel
iOS
HTML
CSS
Android
Python
C Programming
C++
C#
MongoDB
MySQL
Javascript
PHP
Physics
Chemistry
Biology
Mathematics
English
Economics
Psychology
Social Studies
Fashion Studies
Legal StudiesC++ 程序搜索二叉搜索树中的元素
在此程序中，我们需要执行以下操作：实现二分查找，以在二叉搜索树中查找搜索序列是否存在。二分查找的最坏情况时间复杂度为 O(n)，但平均情况为 O(log(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
示例代码
#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;
}输出
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)?
更新于：2019-07-30
2K+ 浏览
广告