08-24-2004, 09:40 PM
PM User |
Join Date: May 2002
Location: Marion, IA USA
Thanked 80 Times in 79 Posts
Originally Posted by sad69
A tree is not a linked list. A tree (be it binary, or n-ary..) can be implemented using linked nodes, similar to a linked-list; or using an array and indices to reference the children and parent (i/2=parent, 2i=left_child, 2i+1=right_child, I think..), and there are other ways still.
The term Tree refers to the idea of a tree structure, independent of implementation. The term Linked-List (they can be singly or doubly-linked) refers specifically to the notion of nodes being linked to one another to give a linear list of nodes.
If a binary tree is implemented as linked nodes, then it is somewhat similar to the implementation of a doubly-linked list. A linked-list in this case is almost identical to a binary tree where each node only has left children. However, once that tree acquires a right child, it is no longer a linked list (as long as the right child is not the node's parent! But then, it wouldn't be a tree any longer, but a graph with cycles..).
Sorry to elaborate, but that was a nice refresher in my mind as well!
Thank your for elaborating my point. I didn't feel like arguing. I had to go through all of that during my data structures and discrete structures courses in college and didn't feel like going back and digging up the details. We went into great depth on the subject but that was years ago and I was pretty sure my memory of it was correct.
CodingForums Supreme Overlord
All Hail Spookster
Who gave you that Ugging infraction? Yeah that's right it was me!