binary search and search using binary tree

I have to implement binary search and search with binary tree.

Suppose I have an array to be searched for value (for example int numbers to avoid complications).Binary search is not a problem. With binary search array must be first sorted,so for example when I
have an array {2 1 4 8 1 5}, I first call some function for sorting. After that I have
{1 1 2 4 5 8}. Then I call binary search that divides array into halfs until find
specific element (if element exists).
But, what is search with binary tree? I suppose first I have to create binary tree from
array members. For example using some function Insert.

Code:

for(int i=0;i<length_array;i++) Insert(array[i]);

After that I have following structure:

2

1 4
1 8 5
And then I should use some function Find() to find element in the tree.
If this is search with binary tree?
Assumption is that I have to sort unsorted array. This way will work, but I wonder if
this really search with binary tree. Significant amount of time is lost while creating
tree calling Insert(), and after that, calling function Find is necessary.
All advices are welcome
Thanks

I don't know exactly what means searching using binary tree when I have unsorted array,
maybe I have to create binary search tree first and then search for desired element, something like this:

Code:

#include <iostream> using namespace std; typedef struct Node { int data; struct Node* left; struct Node* right; }node; node* create_tree(int[],int); void insert(node**,int); int *binary_tree_search(node*,int); void Show(node*); int main() { int array[]={6,7,3,1,2,5,8,9,4,10}; int *x=binary_tree_search(create_tree(array,10),1); Show(create_tree(array,10)); if(!x) cout<<"Element not found!"; else cout<<"element is "<<*x; } node* create_tree(int arr[],int len) { node* head=new node(); head=0; for(int i=0;i<len;i++) insert(&head,arr[i]); return head; } void insert(node**head,int data) { if(!*head) { *head=new node; (*head)->data=data; (*head)->left=0; (*head)->right=0; return; } if((*head)->data>data) insert(&(*head)->left,data); else insert(&(*head)->right,data); } int *binary_tree_search(node* head,int dat) { if(!head) return 0; if(head->data==dat) return &(head->data); else { if(head->data>dat) return binary_tree_search(head->left,dat); else return binary_tree_search(head->right,dat); } return 0; } void Show(node* root) { if(root) { Show(root->left); printf("%d ",root->data); Show(root->right); } }

This seems to be unefficient because of allocating memory and creating tree.
Maybe search array with binary tree is not about creating tree at all,but
rearanging array to look like binary tree (!?!)
Please help, I don't know what to do else.

>But, what is search with binary tree?
Just what you would think:

Code:

bool bt_search ( bt_node *root, int key ) { if ( root == NULL ) return false; else if ( key < root->data ) return bt_search ( root->left, key ); else if ( key > root->data ) return bt_search ( root->right, key ); else return true; }

>This way will work, but I wonder if this really search with binary tree.
Yes, it will work fine. But be sure not to sort the array before inserting the items into the tree. If you do you'll build a degenerate tree that gives you linear search times.

>Significant amount of time is lost while creating tree calling Insert()
Not as much as you would think. Building a binary search tree from a set of data is a useful technique for sorting and searching.

>This seems to be unefficient because of allocating memory and creating tree.
Don't worry about it until you've profiled it and know that it is inefficient. Programmer's intuition is notoriously bad in matters of performance.

>Maybe search array with binary tree is not about creating tree at all
Yes, in this case it is.

>but rearanging array to look like binary tree (!?!)
What do you think binary search is?

So, when I have array of numbers do I have to build tree and insert elements as nodes?
Is this this code ok?
I'm not sure about creating tree with functions such as Insert and Find?
How would you solve this?
My approach is code you see.
Please if you have time, can you comment my code?
Other technique such binary search (after I sort an array) or simple seqential search work directly with an array, but this technique first build binary tree (left is smaller right is bigger)
and then search through tree.

>So, when I have array of numbers do I have to build tree and insert elements as nodes?

Yes, see pseudo code below which is based on your code, some of which has been corrected, and which I think is a better attempt at a possible solution

Code:

for(int i=0; i<len; i++) insert(head, arr[i]); return head; void insert(node* head, int _data) create new node assign _data to new node data assign NULL to new node pointers declare a pointer to node called currentNode assign head to current node if tree is empty assign new node to current node else findInsertionSpot() void findInsertionSpot(node* , node*) //now compare data in current node to data in new node //and insert new node at the first left or right that is NULL if currentNode data greater than newNode data if currentNode left is NULL assign new node to currentNode left else assign currentNode left to currentNode call findInsertionSpot() again else if currentNode data less than newNode data if currentNOde right is NULL assign new node to currentNOde right else assign currentNode right to currentNode call findInsertionSPot() again

Ok, thanks.
Just to be sure my approach is good and actually this is way how search with binary tree is implemented?
I'm sorry if this is annoying to someone, but this is I have to learn very quickly, I'll have it on exams

>Just to be sure my approach is good and actually this is way how search with binary tree is implemented?
If you have some reading time, I've written a basic binary search tree tutorial in the FAQ. It should help to solidify what you already know and help you build confidence in your code.

I have read the tutorial and I must say it's pretty much clear to me.
I got homework to implement different search methods, one of them was to implement search with binary tree in addition to binary search.
Basic problem was how to perform search with binary tree without having binary tree at all, just an array of some type, say integeres. So what I figure out is to make binary tree from unsortzed array and then to write some function Find() to search for the desired element.
On the other hand I had choice to sort array first and then to perform binary search (dividing into halfs) until find the desired element. I don't know what method isfaster and more optimal:
first sort array then binary search or
first create binary tree and then search that tree.
My only idea was to create tree from an array. Maybe I could also permute elements in the array (not creating structure and tree), but don't know how.
Thanks for help, especially you prelude!

>I don't know what method isfaster and more optimal
It really depends on the data. The sorting operation could very well be comparable to building a search tree, but that isn't very likely. If new data isn't going to be inserted or deleted then a sort/binary search combination on an array would probably be the more efficient method. If you'll be inserting or removing items regularly then the cost of resorting or maintaining a sorted array could easily outweigh the cost of handling a search tree and using an explicit tree structure would be more efficient.