2017-07-22 20:35:51
writer:pprp
在创建二叉树的基础上进行查找,由于二叉树的特点最快为O(logn),最慢为O(n)。
代码如下:
#include <iostream>
using namespace std;
struct tree
{
tree*left;
int date;
tree*right;
};
void print(tree * root)
{
if(root!=NULL)
{
print(root->left);
cout << root->date << endl;
print(root->right);
}
}
tree* insert(tree * root,int key);
tree * create(int *node,int len)
{
tree *root = NULL;
for(int i = 0 ; i< len ; i++ )
{
root = insert(root,node[i]);
}
return root;
}
tree* insert(tree * root,int key)
{
tree*current;
tree*parent;
tree*newval=new tree();
newval->left = NULL;
newval->right = NULL;
newval->date = key;
if(root == NULL)
{
root = newval;
}
else
{
current = root;
while(current!=NULL)
{
parent = current;
if(current->date>key)
{
current = current->left;
}
else
{
current = current->right;
}
}
if(parent->date > key)
{
parent->left = newval;
}
else
{
parent->right = newval;
}
}
return root;
}
tree * bisearch(tree* root,int x)
{
// if(root!=NULL)
// {
// if(root->date == x)
// {
// return root;
// }
// else if(root->date > x)
// {
// root = bisearch(root->left,x);
// }
// else
// {
// root = bisearch(root->right,x);
// }
// }
// return NULL;
bool solve = false;
while(root && !solve)
{
if(x == root->date)
solve = true;
else if(x < root->date)
root = root->left;
else
root = root->right;
}
return root;
}
int main()
{
int x;
tree * root = NULL;
tree * point = NULL;
int node[11] = {1,2,3,4,5,6,7,8,9,10,11};
root = create(node,11);
print(root);
cout << "您想查找的节点大小:" << endl;
cin >> x;
point = bisearch(root,x);
if(point == NULL)
cout <<"没有您要的数" << endl;
else
cout <<point->date<< endl;
return 0;
}
代码改变世界