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+ 瀏覽
廣告