So I started this so that the use of "trees" in TI-BASIC programs and an explanation on how they work.

I'd use trees for a dynamic dungeon leading to multiple endings.

You could also make a magic tree, like in Diablo II, if you don't know what it looks like, I will post an image when I get home.

I know what it looks like, bro. I own Diablo II.
Tis a great game.

Now, were you going to post an explanation of tress here or... I was confused on what this topic was for.

I feel that a tree in TI-BASIC would just be arduous. Because of the nature of a tree, linked-lists tend to be the easiest way to make them, but BASIC doesn't really provide that kind of functionality easily. You could do an array-based tree, but that is tedious. Another issue is that most tree algorithms are recursive, and without a stack (which DCS actually provides for BASIC programmers, one of the reasons I wanted it was for recursion) that's not very simple either.

Wait, what? A linked list resembles a computer tree in the same sense that a telephone pole without any of the accoutrement resembles a physical tree.


Only for some types of trees. Heaps are trees, and almost always implemented as an array. Anything that is guaranteed to stay balanced should be relatively easy to implement as an array.


We have all sorts of stack-capable data structures to make recursion easy. I usually use a list, but a string would give you an even deeper stack.

Anyway, here's my own implementation of a binary search tree in Basic. It's been a while since I wrote it though, so it may be a tad buggy. http://www.ticalc.org/archives/files/fileinfo/393/39374.html

I meant a linked-list type structure, my bad. That is, nodes pointing to other nodes. A linked-list is a tree, just a degenerate case. So generalize that a little more and say you can have any number of nodes coming from a node, as long as there're no cycles, and you've got a tree. Now say you can have cycles and you've got a graph. The easiest way to think about graphs is as nodes connected to other nodes, which lends itself pretty clearly to that type of reference structure.

I agree with your second point; if it's a specialized case of a tree that lends itself easily to array-based implementation, it isn't too bad. However, for any general tree (that is, any graph without cycles), arrays are going to have more book-keeping than a simple linked-list structure. You could have one node with 500 children, and each of those children could have 200 children, and each of those could have any number of children. Not let's say you want to add a node as a child of an existing node, this is a very straight-forward thing to do with a linked list. If your array is already full you need to resize, rearrange, etc. Maybe not too bad with some slicing mechanisms, but I think the linked-list approach is easier.

Stack-capable data structures aren't stacks. You have to do all the bookkeeping yourself, once again. I'm aware you can use a list or string or even a matrix if you really want to make your own stack, but that doesn't mean it's not easier with a pre-built stack.

I never said it was impossible, just arduous.

So a question, is it possible to have a list link to other lists, which can link to another, or strings, etc. a very small example being the game Shadow the Hedgehog, I don't know if all of you have played it, but I will post a link to an image showing how it works.
Shadow the Hedgehog

Sonlen, sure, but you'd have to know what the stored data meant and interpret it in the context of your program.


At that point (more than a handful of children) you're probably better off using a map of some kind with integer keys. For example a TreeMap, so your insertion time is logarithmic instead of linear on the number of children.


sure,
Code:
would be easier than
Code:
,
but it's still such trivial code that I can't understand calling it arduous.

I know that, I just was checking to see if that kind of something is implementable.

I agree. As far as efficiency is concerned, there are some better ways to handle more specific trees. Or even more general graphs. But I'm not talking about efficiency of that structure or the algorithm, simply the ease of implementation and understanding.

I'm calling the entire process of an array-based tree arduous compared to a linked structure. Not just maintaining your own stack. My argument has never been that it can't be done, just that it's not as easy to think about or implement given the calc's structures.

A binary tree is still relatively trivial if you use one for data, and a complex list to store indices to the child nodes. You don't have to do much slicing either, just treat the list as memory cells and the secondary list as pointers.

You could always use the Doors CS AnsStack features:

http://dcs.cemetech.net/index.php?title=BasicLibs:PushAnsStack
http://dcs.cemetech.net/index.php?title=BasicLibs:PopAnsStack
http://dcs.cemetech.net/index.php?title=BasicLibs:ClearAnsStack

It seems to me that this topic would be most complete with a discussion of graphs, trees, queues, stacks, and linked lists (doubly or singly) at the very least.

Hmm, I never really thought of that. And since any arbitrary tree can be represented as a binary tree, that's really not too bad. I'd still rather do it with pointers or something more advanced than an array, but I see your point. It's not as hard as I had thought.

Right, which I mentioned. That's a big reason I pushed the AnsStack when we were talking DCSBLibs.

I'm spoiled by high-level languages, I don't want to have to do anything

I'm starting to get spoiled by my pseudocode in my Algorithms class. What's that, I need a Queue with arbitrary methods? Yay, there it is! What's that? A list with constant-time insertion and removal? Here it is! We'll imagine that it's implemented as a bitfield! \o/

If you want to really break your brain, you can try using a double-linked list to represent an N-ary tree, where each node is linked to its parent and to an element that starts a sublist of pointers to children (which must use the back-link for the children and the forward-link for the next element of the sublist with the next child, or NULL for the last child).