Hi! We meet again! So tired about linked list. Well, this chapter we're going to meet one, in a different form. Oww.... That's the fate. I hope you didn't feel bored. :-) I think you should know this too. This part, at least, is more important than circular linked list. :-) Don't feel bored! You'll learn linked list until chapter 5 for this second lesson. Later on, the study about pointers is deepened, especially in the third lesson. By the way, you can skip lesson 4 and 5 if you want to. But I warn you though, this lesson is important. Don't hesitate to come back as you need to.
The use of tree nowadays is quite varied. From pull down menu to serious
data base. Do you know the file manager's tree of directories? That will
not be possible without the knowledge of tree. The pull-down menu obviously
uses tree. Serious data bases, I mean very very big for big company, cannot
be handled simply by linked list, either single or double or circular.
This is intended to speed things up. Yeah...sure! Artificial Intelligence
makes use of this very intensively, like heuristic search, and so on. In
short, tree has a lot of use. Really! :-) I know you'd always believe me.
:-)
OK, here's the fact. What I tell you here is merely the basic of the tree. Not a family tree.... :-) Quite obviously, the advanced things about it are told in the third lesson. Well, not so advanced, I think ... just intermediate lessons :-) So, don't complain about so many things you haven't got here.
In this chapter, I'm just going to explain about the basic tree structure and some binary structure stuffs. I hope that I can explain things as simple as possible yet you'd get as deep understanding as you can be. This includes all operations behind it. I also explain about binary search tree. I'm not going to explain sorting using a tree. That's useless. You've already know the fastest sorting algorithm on earth: quick sort. Although that topic is discussed quite thouroughly in academic life, I think that is pretty a waste of time. May be next time... somewhere in the future. :-) Just may be...
Why don't I explain all things about tree here? It's too long. I even
can make a book about it, only about it. Honest. :-) Well, you know, I'm
a practical guy that do practical things, not hyper-theoretic ones. :-)
That's why. This part is used a lot in programming life while others are
not. The others I do not mention here are commonly used for a specific
things, like Artificial Intelligence stuffs or a very big data bases. I
don't know what they use in the future but now, they have a little use
for daily life. :-) Yeah... that's as far as I know.
Not like classic books about tree, I'm not going to explain the tree
in general first. I'd rather explain the simplest first, binary tree, than
the complex one. I think that helps most of the students, including many
of my friends. I hope it helps you too. :-) OK, let's begin....
Remember the tree of factors we've learnt in the primary school? If
you don't, take a look at this picture:
12
/ \
3 4
/ \
2 2
It's the decomposing factor's tree. Ahh... you remember now! 12 is 3 x 4, and 4 is 2 x 2.
Now, it's not the mathematics I'm going to explain but the underlying structure. The structure is ... tree :-) (yeah of course). It has a parent and two children. In the picture above, 12 is the parent and the children are 3 and 4. Nevertheless, 4 is also a parent with its children 2 and 2. 3 and 4 is the children of 12, both 2 is the children of 4.
There are no grand children though :-) not like humans... :-) The grand children, great children, great great children and so on all the descendants are called siblings. However, in tree here we know brothers (or sisters, just for the emancipation :-) ). The brother of 3 is 4. If both members are the same, just like 2 and 2, are called twins. :-) They are like humans, right?
Don't ask me where is the father or the mother, they just get one parent. That's all. :-) They are not married and they followed the Indonesian planned-family programme (two children are enough) :-)
The lines that connect 12 and 3, then 12 and 4, is called descendant lines. I don't know why they are called so, but yeah... just call it so, OK. :-) However, just like linked list, each item is called node. 12, 3, 4, 2, and its twins 2 each is a node. You can say anything above that node is called ancestors, and anything below it is called descendants. Besides brothers, all nodes at the same level of that node is called cousins. Just like cousins in human life. :-) 12 is the root node, because it has no parents. All children and siblings are below it.
That's the history of 12 ... :-) Just kidding! Because all of the parents have only two children each, the tree is called binary tree. Just like binary number, that is based on 2. So, binary means two. Enough about semantics or jargons...
How can we model this into programming languages? The descendant lines
is perfectly subtituted by pointers, so the definition is like this:
type
pBintree = ^tBintree; { Just like linked list definition }
tBintree = record
num : integer; { Any data here, as long as you want }
bigbro,
youngbro : pBintree;
end;
I use bigbro and youngbro here because there are two childrens. It's a matter of distinguishing one from another. Just like brotherhood in human life has big brother(s) and younger brother(s). :-) The field num here can be replaced by any data. Here, I use a plain integer. Simple. :-)
The operation in binary tree is the same as that in a normal-but-complex tree. They are:
Some people said mounting a node instead of adding. Yes, you can edit nodes too. But you are not allowed insert nodes. The two things that people often do is adding and destroying. Deleting is seldomly used and displaying is hardly used, very very seldom. Inserting nodes can be done, actually, but it has no practical use. You can review it later and you'll understand why. Also, in binary tree, editing nodes is very seldom used. Why? It's because the binary tree is done for deterministic actions only.
I'll explain it one by one here. It resembles the one in simple queue but has significant changes. You can just view queue as tree, but has only one child. Now, you've got two children to handle. :-)
OK, now how to add nodes. Follow these steps:
Easy steps, eh? Now, how to put these in a function? Here you are:
function add(var parent : pBintree; content : tBintree; firstson : boolean):boolean;
var cur : pBintree;
begin
{ Step 1 }
add:=false;
if parent<>nil then
begin
if (firstson) and (parent^.bigbro<>nil) then exit;
if (not firstson) and (parent^.youngbro<>nil) then exit;
end;
{ Step 2 }
new(cur);
cur^.num:=content.num;
{ Step 3 }
cur^.bigbro:=nil;
cur^.youngbro:=nil;
{ Step 4 }
if parent=nil then
begin
parent:=cur; exit;
end;
if firstson then parent^.bigbro:=cur else parent^.youngbro:=cur;
{ Step 5 }
add:=true;
end;
How can it be? We can make it bear the second son first? If we just follow the fate, say... bigbro is born first, what's the use? Well, that is practically no use. However, if we can select which son to be born first, we can make a great use of binary tree. In binary tree, bigbro is not always born first. :-) This time, computer science has gone farther than biology. :-) Why must we make the add procedure so that we can choose which son can be born first? It is for the sake of flexibility. As the rule of thumb, the more flexible the routine, the more useful it can be.
For you who have learnt binary tree before and you protest that this is different, I say to you, this is the more flexible binary tree. Why? This allows better implementation in the future. Usually, what lecturers taught binary trees is around the binary search tree. The adding part is quite different. Listen, mine is more flexible. You can implement this everywhere instead of just binary search tree. You can even make an expert system using yes-no knowledge base. But, I will also explain about the binary search tree below. Just be patient and compare mine to other theoricist.
The main use of binary tree is for binary searching. It's easier and somewhat faster if done properly. The other use of binary tree is for Huffman compression method. Sometimes it also used for 3-D graphics to determine the edge of the rooms. And so on. That things use the you-can-select-which-son-to-be-born-first binary tree's add procedure.
Now, the display part. It is quite tricky. It needs recursive procedure
instead of simple looping. Do you know why? It's because the tree has two
chilren instead of one. Yes! You're clever! :-) How'd we do it? Remember
the quick sort routine I taught in the first lesson? The structure is quite
the same. Look at this:
procedure display(head : pBintree);
procedure shownode(what : pBintree; x,y : byte);
begin
gotoxy(x,y); writeln(what^.num);
if what^.bigbro<>nil then shownode(what^.bigbro,x-5,y+1);
if what^.youngbro<>nil then shownode(what^.youngbro,x+5,y+1);
end;
begin
if head<>nil then shownode (head,40,1);
end;
You got it? Yeah! Now the destroy part. Destroy part must be implemented in recursive way. The same reason applies. Check this code:
procedure destroy(var head : pBintree);
procedure del_one(what : pBintree);
begin
if what^.bigbro<>nil then del_one(what^.bigbro);
if what^.youngbro<>nil then del_one(what^.youngbro);
dispose(what);
end;
begin
if head<>nil then del_one(head);
head:=nil;
end;
To put it up together, we still need to know what the program would be. OK, we pick up binary search tree. Since binary search tree implementation is a little bit different, so we need to modify the routines. The only part that is quite different is the adding part. However, the add function we've built so far can be reused.
The rule of adding in binary search tree is like this. First data is placed, say it is 40. Then the second data arrives, 50. 50 is then placed in the youngbro section. Then 30 comes. It is below 40, so it is placed to the left of 40, to the bigbro link.How'd we find 45? 45 is placed to the bigbro link of 50. And so on. The bigbro link value is always less than current node value and the youngbro part is always more than current node value.
OK, I'm not going to explain the adding part so detail but look at this
code and run it. Of course you need to join the declaration part and the
other codes above so that the program may work. This will run the adding
part and then display it step by step so that you can understand the underlying
process. Here's the addBST procedure:
procedure addBST(var head : pBintree; content : tBintree);
function findparent(what : pBintree; content : tBintree) :pBintree;
begin
if what^.num>content.num then
begin
if what^.bigbro=nil then
findparent:=what
else
findparent:=findparent(what^.bigbro,content);
end
else
begin
if what^.youngbro=nil then
findparent:=what
else
findparent:=findparent(what^.youngbro,content);
end;
end;
var cur : pBintree;
begin
if head=nil then add(head,content,true)
else
begin
cur:=find(head,content);
if cur^.num>content.num then
add(cur,content,true)
else
add(cur,content,false);
end;
end;
To put it all together, put this code to the end. Don't forget to paste all the code above and put the uses crt statement.
var head : pBintree;
x : string[3];
temp : tBintree;
e : integer;
begin
clrscr;
head:=nil;
repeat
write('Enter a number : '); readln(x);
if x='' then break;
val(x,temp.num,e);
if e>0 then halt;
addBST(head,temp);
clrscr;
display(head);
writeln;
until false;
clrscr;
writeln ('Total tree:');
display(head);
readkey;
destroy(head);
end.
The entire program will be in the zipped file of my second lessonin the file tree.pas. Run this program and you can see the adding process step by step.
Now, how about the searching. It's easy to figure out. The process is
like this: Compare the searched number with the head's content.
If it is lower, then go to the bigbro section, then repeat comparison.
If it is higher, go to the youngbro section, then repeat comparison.
That's all. We need to incorporate the recursive loop. How can we do it?
Here:
function search(head : pBintree; what : tBintree): pBintree;
function insearch(cur : pBintree; what : tBintree): pBintree;
begin
if cur^.num=what.num then { Found }
begin
insearch:=cur; exit;
end
else
if cur^.num<what.num then { Too small? Go to youngbro }
begin
if cur^.youngbro=nil then
begin
insearch:=nil; exit; { If youngbro is a nil then not found }
end { otherwise, search on }
else insearch:=insearch(cur^.youngbro,what);
end
else
begin { Too big? Go to bigbro }
if cur^.bigbro=nil then
begin
insearch:=nil; exit; { If bigbro is a nil then not found }
end
else insearch:=insearch(cur^.bigbro,what);
end;
end;
begin
search:=insarch(head,what);
end;
Try to add searching function to your program and make a good search engine. Do you know the Borland Pascal's help index? I think they use this too, but in an advanced manner. Try make one.
After you know binary tree, it's about the time you learn the tree itself in general. The difference in abstract structure is that tree in general has as many sons as it would be, instead of 2 in binary tree. Gee, seems that this structure never learn the Indonesian planned-family programme. :-) Tree in general is allowed to have either just one child, or two, or three, or even 100. So, the programming matter here is quite different than that in binary tree.
Here, I'm not going to discuss the entire detail about tree in general. I'm sure you are smart enough to make your own routine instead I'm "dictating" one. However, I will discuss the concept quite thoroughly so that you can follow me. I'm sure, after learning lessons this far, you can figure out all the process explained here.
OK, now the declaration part. The different matter about general tree is that the parent has only one link to its first son. It is done because we don't know yet how much the son will be. However, each son has a link to its parent. Every son in the same level of brotherhood is linked through either single link or double link. It's up to you how to do it. It is called the brotherhood link. Here's a diagram shows a tree link relations with queue relations along the brotherhood:
15 | 3 --> 4 --> 7 --> 12 --> nil
The diagram above is not quite perfect. It doesn't draw the link from each son to its parent, 15. So, actually 15 points to 3. Every son, that is 3, 4, 7, and 12 has a link to their parent, 15. Because 3, 4, 7, and 12 is linked through queue (that has nil at the end), the brotherhood link here is queue.
Adding part is quite similar to binary tree except that it accepts more than 2 sons. So the adding part is roughly like this:
That's quite simple, right? Yeah! How about display part? Ever see the file manager's directory tree? That's how to display. The display part is quite the same as display part of binary tree combined with the display part of other linked list (depends on which brotherhood link). It uses recursive technique, too.
Destroying is pretty similar to display part. It is like combining both the destroy part of binary tree and the destroy part of other linked list. Searching part is the same.
By implementing tree, you shall now be able to make your own file manager. You can make pull-down menu interface, too!
Ahhhh! Finally, we came to the end of the lesson. Pretty lengthy, huh? Yeah! You finally made it! :-) OK, that's all for now. Shall we go to the quiz or the next lesson?
Back to main page
Back to Pascal Tutorial Lesson 2 contents
To the quiz
To Chapter 5 about multi-dimensional list
My page of programming link
Contact me here
By: Roby Joehanes, © 1997, 2000