programmingnoob

how many types of trees are there in c++? maybe one of the types would be binary tree, and then there might be subtypes ...

but basically how many types of trees are there in c++?

uman

I wasn't aware of there being different types of tree. A binary tree is a special case, of course, but it's still just a regular ol' tree. That's like saying "How many types of rectangles are there? Maybe one of the types would be squares..."

__________________
Few people deserve to be compared to (Rush) Limbaugh, most of them were convicted at the Nuremburg trials.
--WilliamSChips on Slashdot

Twilight

The special ones I can think of offhand are Binary Trees and Balanced Trees, but there really are about as many tree types as you count.

mrynit

why would some trees be specific to C++? i thought the idea was some what universal in computers science

__________________
i dont know much about programming but i try to help

Jimbo

Go here and search for tree (and see all the different names for similar or identical structures :o). And as mrynit mentioned, trees aren't specific to C++

programmingnoob

well .... i am a little confused ....

do binary trees have to store numbers in their nodes? if yes, then how do i build an abstract syntax tree for my parser?

i was also thinking about expression trees? ....

lectricpharaoh

Heap data structures are often (always?) implemented as a form of tree, too.

As for their being more types than binary, it's perfectly possible to have a hypothetical tree where each node had more than two potential child nodes. I can't see it offering any advantage except in very specific circumstances, like perhaps a radix sort, but then there are probably better structures for those purposes (hybrid hash table, for example).
Trees can store whatever you want in their nodes. Think of each node in a binary tree as an object (in the generic sense, not necessarily an instance of a class) wrapped up with a couple of pointers to the child nodes. Each pointer will be either a valid pointer to a node, or NULL. If that was all it was, it wouldn't be too useful, but when you add some methods to control how nodes are added and removed, it can be very useful.

Two common variants are the binary search tree and the heap. In the former, nodes are added/removed in such a manner that the child node that is 'less than' a parent node is on one branch, and the child node that is 'greater than' the parent is on the other branch. This is done in recursive fashion (so a child on a 'less than' node is less than its parent, and the parent's parent, and so on), and because the nodes are objects, the programmer defines the semantics of less than/greater than. This form of a tree is intended to gain the benefits of a linked list without the heavy performance penalties of arbitrary additions to the list. In the latter, the nodes are added/removed in such a way that the 'largest' (or smallest) is always on top. Again, what defines 'largest' is up to the programmer. This type of tree is often used for priority queues (where the item with highest importance gets processed first).

__________________
And once again, Probability proves itself willing to sneak into a back alley and service Drama as would a copper-piece harlot.
- Vaarsuvius, Order of the Stick

programmingnoob

what kind of data strcuture would you recommend for an abtsract syntax tree for my parser?

lectricpharaoh

Dunno. I haven't done much work with parsing, and it depends a lot on what you want to do. What do you need a parser for? More information makes us more likely to be able to help.

Also, reread my post above. I started editing it in between when I first posted it, and when you read/replied to it, and added some more info.

__________________
And once again, Probability proves itself willing to sneak into a back alley and service Drama as would a copper-piece harlot.
- Vaarsuvius, Order of the Stick

uman

Um, I am actually in the middle of writing a program that revolves around a tree that is not binary.

__________________
Few people deserve to be compared to (Rush) Limbaugh, most of them were convicted at the Nuremburg trials.
--WilliamSChips on Slashdot