Tuesday, January 13, 2015
Changes 1/13/15 - EIMACS Trees
Today I learned about binary trees, which are a lot like LinkedLists (in the implementation EIMACS is using) except that they have two "next node" values instead of just one: a left and a right value. This means that pretty much every method I've had to code for the exercises so far has been recursive.
Subscribe to:
Post Comments (Atom)
Ah, but trees are also not like linked lists at all! A list is a one dimensional data structure, while a tree is two dimensional. Some of the implementation details may be similar, but the algorithms used to operate them are very different. And, yes, recursion is the key to trees, which are "recursive data structures". Even the definition of a binary tree is recursive:
ReplyDeleteA binary tree is:
1. emtpy (contains no nodes), or
2. has a root node, a left binary tree, and a right binary tree
(see http://xlinux.nist.gov/dads/HTML/binarytree.html)
It's a recursive definition since 2 uses the term being defined, binary tree, in the definition. It is a perfectly fine definition, however, since just like in a recursive algorithm, it has a "base case" (the empty tree) that allows the recursion to stop.