binary trees

Ok... I just finished learning Linked Lists... Ok, not really finished, but I know enough for now... I know binary trees have 2 pointers to nodes, rather than 1, but how do they work, and how are they used?

thanks,
Dennis

[Krushstone]

Well, they kinda work like a linked list, but with 2 links... :-)
They work better when they are sorted in some way
for example : the node to the left is smaller than the root and the node to the right is bigger than the root (or its father).
Like :

------12
-----/----\
----5-----23
---/--\----/---\
-2----8-13---45

If you want to add the node 6 to the tree, you will have:
6 < 12
6 > 5
6 < 8
so 6 will be the left child of 8

Normally, you only have a pointer to the root of the tree, and you seek recursively to the value that you want.
This is recursive because each node can be considered as a root of a sub-tree.

One advantage is that if you want to know the bigger value (45) you only have to go through 3 nodes, instead of 7 in a one-way sorted linked list.

They can be used for almost anything but keep in mind that if the tree is very big and that you need to remode nodes randomly in it, it may take a lot of time to re-equilibrate the tree...

I hope this anwser your questions

Krushstone

thanks :D
I just read part of my C++ book, and it said that a linked list with two nodes tather than one, was called a double linked list, and anything with more was called a Binary Tree.


Thanks,
Dennis

[Krushstone]

hem... I don't agree totaly with that...

you said:

"and anything with more (more than 2 nodes)was called a Binary Tree."

I prefer : "... called a Tree."

A tree is not necessarily binary.
Binary means 2, so a tree in which the roots is linked to 3 nodes is called a tertiary tree.

In a binary tree, a node can't link to more than 2 other nodes.

It was just a little precision

Krushstone

Doh!

I meant to type that, but I was in a hurry because my teacher was coming... and I am not exactly sure if he would approve of me being active in a public forum while using the school computer :rolleyes:

I thought I said a "Tree" not "Binary Tree"..... :eek:

[HarryW]

Does a node in a tree always have a pointer to its parent node then, like a doubly linked list? I would have thought that in many cases you wouldn't need to traverse up the heirarchy, only down.

[Krushstone]

Not always

it depends on the structure of your nodes

In C you could have:
typedef struct node
{
int value;
struct node * leftchild;
struct node * rightchild;
}node;

but if you also want to have a pointer to the parent, you only have to add
struct node * father;

So it's you who decide how your tree will work.

Krushstone