用C ++程序搜索二进制搜索树中的元素
在此程序中，我们需要。实现二进制搜索以在二进制搜索树中找到搜索序列的存在。二元搜索的最坏情况时间复杂度为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)?
热门推荐
1 训练狗狗基础
2 怎么训练狗狗笑
3 怎么训练狗狗卧下
4 上海狗狗训练基地
5 训练狗狗排便
6 狗狗基础训练
8 如何训练狗狗装死
9 狗狗站姿训练
10 狗狗训练用品
11 训练狗狗吧
12 狗狗要怎么训练
13 怎么训练狗狗玩球
14 训练狗狗唤回
15 狗狗训练躺下
16 狗狗训练指令
17 狗狗的训练技巧
18 狗狗不好训练