Author : Unknown
Page : 1 Next >>
Linked lists overcome some of the problems of arrays, but they create new ones. Accessing an element in a linked list is a linear (O(n)) time operation as is searching it. The only search that is possible on a linked list is linear search. Binary trees retain the linked lists' ability to grow and shrink as required, but they also have an O(log n) average access and search time. On this page we're going to particularly concentrate on binary search trees (but I'll just keep calling them binary trees).
The binary tree node is quite similar to the linked list node at first glance. However whereas the linked list node had one successor the binary tree node has two. I'll call these left and right (you'll see why later). So the basic structure is:
struct Node
{
int data;
Node *left, *right;
};
Again the tree starts simply with a pointer to the first node. The complete class specification is:
class binaryTree
{
private:
struct Node
{
int data;
Node *left, *right;
};
Node *head;
public:
void Insert(int newdata);
void Remove(int data);
int Find(int data);
};
Again this class doesn't do that much and you won't find it in a real program, but filling in the functions gives you an idea of how to deal with this type of structure. The power of the binary tree lies in where you put the data. When you are inserting a node you place it to the left if it is less than the value of the current node and put it to the right otherwise. This means that the data is effectively sorted. The Insert function is:
void binaryTree::Insert(int newdata)
{
Node *temp = new Node;
temp->data = newdata;
temp->left = NULL;
temp->right = NULL;
if(head==NULL)
head = temp;
else
{
// find the correct location for the new node
// and insert it
int inserted = 0;
Node *locn = head;
while(!inserted)
{
if(locn->data > temp->data)
{
if(locn->left == NULL)
{
locn->left = temp;
inserted = 1;
}
else
locn = locn->left;
} else {
if(locn->right == NULL)
{
locn->right = temp;
inserted = 1;
} else
locn = locn->right;
}
}
}
}
The find function is probably the simplest of the three. It is quite similar to the binary search algorithm, but its worst case performance is O(n). It returns 1 if it finds the data, 0 otherwise.
int binaryTree::Find(int data)
{
Node *temp = head;
while(1) // infinite loop
{
if(temp == NULL)
return 0;
if(temp->data == data)
return 1;
if(temp->data temp = temp->right;
else temp = temp->left;
}
}
As with linked lists the remove function is basically a find that also tracks the previous node.
void binaryTree::Remove(int data)
{
Node *temp = head;
Node *prev = head;
while(1)
{
if(temp == NULL)
return;
if(temp->data == data)
{
int left = 0;
if(prev->left == temp)
left = 1;
// deal with the simple case(s) where one
// child is empty
if(temp->left == NULL && left)
{
prev->left = temp->right;
delete temp;
return;
}
if(temp->right == NULL && left)
{
prev->left = temp->left;
delete temp;
return;
}
if(temp->left == NULL && !left)
{
Page : 1 Next >>