Trees Tutorial
Howdy people, I guess that many people heard of trees and such but don't have a clue of how implement those. In this article I'll try to explain step by step how it's done. I will start with linked lists structures because this kind of a structure is a very basic thing to know for implementing binary trees. Next I'll teach recursion, which gives the programmer a lot of power. And the final thing is the binary tree. All example code will be C/C++.
Linked Lists
Linked lists is basically a chain of nodes in memory pointing on each other, check TAD's article in Hugi #15 for how it looks.
Let's make an example:
struct node
{
int number; // it could be any data
node *next;
};
For a linked list we need the root of the list and the current node.
node *root, *current;
root=NULL; // at the begining root points to NULL
When inserting the first element it needs to be inserted to the root, so let's insert another element to the list:
node *temp;
temp=(node*)malloc(sizeof(node));
temp->number = 10; // just a random number
temp->next = NULL; // doesn't point on anything
if (root==NULL)
root=temp;
else
current->next = temp;
current = temp;
That's the routine for inserting an element, I think it's pretty obvious and no explanation is needed, but if things aren't clear yet, let them be:
That is our list when it's ready: A next points to B, B next points to C, etc.
next next next
A----> B----> C----> NULL
(root)
A is the root. That's what the list looks like, simple as pi.
Recursion
Recursion is when a function or procedure calls itself like:
void a()
{
a();
}
That call will never stop unless we put some kind of statement whether the function should stop or continue, or we could just break it.
Recursion Qualities:
1. There must be some base, some kind of parameter that there won't be any more calls of the function and recursion will end.
2. Each call to the function must happen in smaller order to the bigger order or bigger order to the smaller order and each time get the recursion closer to the base.
Now that we know how we should do it, let's make a small example, a program that sums positive numbers. If you call a=sum(4); it will compute: a=1+2+3+4.
int sum(n)
{
if (n==1) return(1); // that's our base
else
return(n+sum(n-1));
}
In our case a=4+3+2+1. Recursion happens from the higher order to the smaller order. It's a bit hard to explain. One more example before we start building binary trees. We are going to make a routine that shows the string reversed.
By the way, one small explanation about pointers, if we have
int *a, b;
then
b is a local variable that will die at the end of the call,
& gives the adress of the variable in memory
* is the value inside that cell in memory, like in asm:
mov esi,10
sets the adress of esi to 10, while mov [esi],20 sets the value 20 into that cell in memory.
b=5;
a=&b;
Now a points to b. If you cout << a; you won't see 5, you'll see its address in memory, but if you do cout << *a; then you will see 5, the value.
void reverse(char *s)
{
if (*s)
{
reverse(s+1);
cout << *s;
}
}
char string[10]="1234";
reverse(string);
Output: 4321
Some explanation: "if (*s)" means, if it's not NULL yet let's do it. "reverse(s+1);" is a recursion call which is done till we get to NULL. When we get to NULL, the recursion call stops, in our example when *s='4', and prints it out on the screen, gets one step back, *s='3', and prints it on the screen, etc., gets back to the first call and that's it.
Binary Trees
For understanding binary trees we'll make an example of inserting data into the tree. For simplicity purposes we'll insert just numbers, but that could be any type of data.
We'll insert these numbers: 25, 72, 32, 65, 21, 19, 81, 20, 76
First we insert 25 and it's going to be our root:
25
/\
NULL NULL
Then when we are about to insert 72, we check if it's bigger than the root (25), if it is then we put it to the right, otherwise to the left. 72 is bigger so we put it to the right.
25
/\
NULL 72
Then 32, it's bigger than the root (25) so it goes to the right, we compare it again with 72, it's smaller, so we put it to the left side of 72.
25
/\
NULL 72
/\
32 NULL
/\
NULL 65
And so on. I think you got it by now.
When searching in tree for some data, you always search by some id-key. Our node is defined as:
----------------
| ID |
|--------------|
| | |
| LEFT | RIGHT |
| | |
|------|-------|
³ ³
³ ³
³ ³
³ ³
³ ³
\-/ \-/
struct NODE
{
int ID;
NODE *left, *right;
NODE(int num) {
ID=num;
left=NULL;
right=NULL;
};
void print() { cout << "ID=" << ID; }
};
NODE(int num) { .... }; is a constructor which is executed when we define NODE objects, it set all the values to default, left=NULL, right=NULL, and sets the ID.
E.g.: NODE a(10);
Our tree structure is defined as:
struct TREE
{
NODE *r;
void insert(NODE *CUR, NODE *NEW);
tree() { r=NULL; }
void print(NODE *CUR);
};
NODE *r; is the root, insert is a recursive procedure which inserts a node to the tree, and tree() { r=NULL;} sets root point to NULL.
Note: All the recursion thing might be very confusing, so if you don't get it at the first time re-read it few times.
void TREE::insert(NODE *CUR, NODE *NEW)
{
First thing we check if our root is empty. If it is, we set it to NEW and exit from the procedure.
if (r==NULL)
{
r=NEW;
return;
}
Then we check if the current we node we are in (CUR) is empty. If it is we set it to NEW like we did in the first check and return.
if (CUR==NULL)
{
CUR=NEW;
return;
}
Now we need to check to which side we shall add the NEW node.
if (NEW->ID >= CUR->ID)
{
if (CUR->right==NULL)
{
CUR->right = NEW;
return;
}
else
{
insert(CUR->right, NEW);
return;
}
}
if (NEW->ID <= CUR->ID)
{
if (CUR->left==NULL)
{
CUR->left = NEW;
return;
}
else
{
insert(CUR->left, NEW);
return;
}
}
}
Here's a small procedure that prints all the nodes:
void TREE::print(NODE *CUR)
{
print(CUR->left);
CUR->print();
print(CUR->right);
}
As always it's a recursion call, oh and by the way, there might be typos here, as all came straight from my head. It should work though.
Well folks, it's about it, our journey to the world of trees has ended. I hope that from now on you won't be scared when hearing the word tree.
Greetz in random order
frenzy, kalms, sarwaz, salami, dvb, tnse^1999, altair, absent, faktorii, greco, action, adept, submissive, kombat, sunday, katrikan, silvatar, tomh, mirek, vastator, nick-s, mrz, adok, veloctiy, v-man, coaxcable, sol_hsa, cube, yoyo, borzom, parody, graffik, attack, matja, sarix, silent breed, kutepixel, xerxes, c-bus, mali, midnight, scriptum, psychic symphony, ex, rodex, raiden, sagacity, good-day, adversary, ica, mads.
All Winter in July and Mistery members.
EFnet: #coders, #math
IRCNet: #pixel, #coders and #3dcoders of course
Customer: "I'm running Windows '95."
Tech Support: "Yes."
Customer: "My computer isn't working now."
Tech Support: "Yes, you said that."