Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

Code Snippets / [DBP] - Tree Data Structure

Author
Message
Mr Kohlenstoff
16
Years of Service
User Offline
Joined: 7th Jun 2006
Location: Germany
Posted: 20th Feb 2012 18:54 Edited at: 20th Feb 2012 18:58
Hi,

I just realized that there seemingly is no code snippet implementing trees in Dark Basic - at least I did not find a thread on that topic.
Consequently I wrote a small library doing just that: allowing you to build and manipulate trees with arbitrary branching factor (i.e. it is not limited to binary trees).

The following functions are available:

Quote: "
tree_init() - has to be called once, before using any other tree-function
rootnode = tree_new(key) - creates a new tree
node = tree_addNode(parent, key) - adds a node to the given parent-node
tree_DeleteLeafNode(node) - removes a childless node from a tree
tree_DeleteSubtree(root) - deletes a complete subtree defined by the given root
tree_CutSubtree(root) - Removes a subtree from the tree it's currently in and makes a separate tree out of it
tree_SetParent(node, newParent) - takes a subtree and puts it somewhere else
n = tree_getChildcount(node)
node = tree_GetFirstChild(node) - returns the first child of an inner node (0 if node is a leaf)
node = tree_GetNextChild(node) - returns 0 if there are no more childs in the list
bool = tree_isPredecessor(node1, node2) - returns 1 if node1 is predecessor of node2 (i.e. node1 is element of the transitive closure of node2 induced by its parent-attribute)
string = tree_toString(root) - can be used for debugging purposes, it takes a (sub)tree and converts it to a string of the form "key_of_node [ keys_of_children ] keys_of_siblings"
"



Note that I've not fully tested all those functions yet, but in case something is wrong with them I'll probably notice that since I'm going to rely on this library quite heavily in a project I'm currently working on.
So if I encounter a bug I'll make sure to fix it and update the code below, so you can be (almost) sure that it works well.


Now about the application: You obviously cannot just make trees for the sole purpose of having trees of numbers - they are actually pretty handy in certain situations.
For instance, the reason why I made this library in the first place is, as indicated above, my current project. Part of this project is an interface including windows, frames and so on. Those can be structured in a tree-like way: One frame lies within another frame, which is child of a window.
The tree-library provides the required functionality: I simply create a container()-array which includes all those windows, frames etc. as well as their attributes. Furthermore each container is associated to a node, and the array-ID of the container is used as the node's key. This way I can structure the whole arrangement of containers.
The tree is then used when, for instance, drawing the scene. I initially created a tree using "containerTree = tree_new(0)", all following containers are children of either this containerTree or of other containers. So drawing can be done recursively, with an approach similar to "drawMyself first, then draw my Children" which can be realized with tree_GetFirstChild and tree_GetNextChild.

On top of that I use the library for another purpose at the same time - a command history. Using an "undo"-feature traces back inside this history-tree, another action then opens up a new branch. Using a tree instead of a list here allows me to show the user the complete history of his/her actions, allowing him/her to go back to any previous state of the document. As consequence it is impossible to lose changes by undoing them, which can easily happen with, say, usual text editing software.


OK then, enough about that.

Here's the code:





I hope it helps.

Thanks for your interest.
Questions, comments, suggestions and criticism are welcome.

Have a nice day,
MrK

noobnerd
12
Years of Service
User Offline
Joined: 30th Nov 2010
Location:
Posted: 20th Feb 2012 20:40
looks interesting, i will have to check this through more thoroughy sometime, as i havent ever used "trees" before

but good job ! (probably)
Zotoaster
17
Years of Service
User Offline
Joined: 20th Dec 2004
Location: Scotland
Posted: 20th Feb 2012 22:29
Nice one Mr K, trees are useful in many areas of programming. They are so simple yet such a natural way to organise things. DBP should have come with built-in abilities to make trees, so this will be useful to the community. Good job!

"everyone forgets a semi-colon sometimes." - Phaelax
MrValentine
AGK Backer
11
Years of Service
User Offline
Joined: 5th Dec 2010
Playing: FFVII
Posted: 21st Feb 2012 02:12
Can someone dumb this down for me? I can not understand WHAT it does...



Zotoaster
17
Years of Service
User Offline
Joined: 20th Dec 2004
Location: Scotland
Posted: 21st Feb 2012 03:04
MrValentine,

A tree is just a data structure. It's built up of nodes, with one node as the root. Each node has pointers to other nodes, and a piece of associated data.

MrK's example is a very good one of how trees are useful. The root node would be the window, which would contain child-nodes, say, a textbox and a panel, which in turn contains further child nodes such as buttons and listboxes.

"everyone forgets a semi-colon sometimes." - Phaelax
MrValentine
AGK Backer
11
Years of Service
User Offline
Joined: 5th Dec 2010
Playing: FFVII
Posted: 21st Feb 2012 03:20
So ... I say... I have a box... with objects on it and there can be variables within child nodes to say reflect conditions inflicted on those objects auch as height data?

Mr Kohlenstoff
16
Years of Service
User Offline
Joined: 7th Jun 2006
Location: Germany
Posted: 21st Feb 2012 11:02 Edited at: 21st Feb 2012 11:06
Generally a tree is used to represent hierarchical data inside a program.

A window containing stuff (which then again may contain more stuff and so on) is one example. The idea is that each node of the tree (representing an element of whatever it is you're using the tree for) has references to only those other nodes that it is directly related to.

DBP allows you only to work with a data structure comparable to linked lists (well, multidimensional arrays as well, but let's ignore them for the moment), i.e. the elements are ordered linearly and every element has exactly two neighbours (apart from the first and last element who have one).
But in practice there are many cases where this kind of hiererchy does not suffice - be it a window-based GUI, a menu system (as in MS Word, where File, Edit, View, Extras etc. are children of the hypothetical root of the menu, then the elements New, Load, Save, Save As etc. are children of the File-Node and so on), a quad-tree for the optimization of certain 2D or 3D drawing operations, or a search tree.

To get back to the GUI system, the tree structure makes certain actions a lot easier. For instance, when I want a window as everything inside to be hidden, this behaviour can be achieved without any effort.

Consider the following drawing function:



This function would draw a container and then call the same drawing function for all its children (i.e. the container's content) recursively. Now if I want a container as well as all its children to be hidden, I can do this:



...which will lead to the desired behaviour.

I hope the purpose of those functions gets clear now, otherwise I guess only some informative images will help.

MrValentine
AGK Backer
11
Years of Service
User Offline
Joined: 5th Dec 2010
Playing: FFVII
Posted: 21st Feb 2012 11:29
IMAGES IMAGES

But I think the FILE MENU kinda hit it on the nail head...

I suppose an actual application of this would be even better but I suppose there are more than one ways to do this right?

Zotoaster
17
Years of Service
User Offline
Joined: 20th Dec 2004
Location: Scotland
Posted: 21st Feb 2012 12:11
A quick read on wikipedia should fill you in on the details.

http://en.wikipedia.org/wiki/Tree_(data_structure)

But yes, play around with the menus at the top of your applications. You will see trees in action.

"everyone forgets a semi-colon sometimes." - Phaelax
MrValentine
AGK Backer
11
Years of Service
User Offline
Joined: 5th Dec 2010
Playing: FFVII
Posted: 21st Feb 2012 12:21
thank you

Mr Kohlenstoff
16
Years of Service
User Offline
Joined: 7th Jun 2006
Location: Germany
Posted: 21st Feb 2012 12:51
Another great example is the file system of your computer.

Take this image for example:



The left part of the image actually displays a tree:
Desktop is the root here, and has two children (at least two are visible in the screenshot): My Documents and My Computer.
My Computer then again has children, the different disk drives and so on.

Parts of the tree are hidden in this view, indicated by the "+"-symbol next to the tree elements: this symbol means that you can expand this element, showing the subtree belonging to the respective folder.

What you see on the right side is one level of the tree, in this case all the child nodes (or directories) of "Program Files", which is a node of the tree and child of "C:".


Working with such structures using usual arrays is somewhat painfull and prone to errors. As consequence a function library providing a tree structure with usual operations can come in quite handy.
Those operations are quite intuitive in the given context:
-creating a new node -> creating a new folder in your file system
-deleting a subtree -> deleting a folder as well as all its content.
-deleting a leaf node -> deleting an empty folder (i.e. the according tree element has no children) (...or a file for that matter, because a file has no subordinated tree elements)
-changing the parent of a node -> moving a folder to another place
...and so on.

You (hopefully) can imagine that those operations would be quite difficult to implement without using a tree structure.

MrValentine
AGK Backer
11
Years of Service
User Offline
Joined: 5th Dec 2010
Playing: FFVII
Posted: 21st Feb 2012 12:54
[Sorry could not resist... I guess you have DivX converter installed right? lol]

I have that filter installed too lol

So essentially they work like truth table in some logical sense with that invisible example given earlier... its a sort of SKIP THIS thing too? right?

Mr Kohlenstoff
16
Years of Service
User Offline
Joined: 7th Jun 2006
Location: Germany
Posted: 21st Feb 2012 13:51
Quote: "[Sorry could not resist... I guess you have DivX converter installed right? lol]

I have that filter installed too lol"


I have no idea what you're talking about. If you are referring to the screenshot, it's not by me, it was just the first one google gave me.


Quote: "So essentially they work like truth table in some logical sense with that invisible example given earlier... its a sort of SKIP THIS thing too? right?"


Not sure what exactly you mean with truth table. The "invisible"-example was just one instance where trees make life easier. They provide general advantages with managing data - e.g. when searching the tree (for example a search for a file on your HDD will use the tree-structure for navigation through the directories), changing it (creating, deleting or re-allocating directories/files), or drawing it to the screen (where the option to hide parts of the tree can be used to keep it small - if there was no such possibility, your windows explorer would show you a list of all 100.000+ files and directories existing on your hard disk).

MrValentine
AGK Backer
11
Years of Service
User Offline
Joined: 5th Dec 2010
Playing: FFVII
Posted: 21st Feb 2012 14:31
Ooook... I see... kinda Fragmented structure or FAMILY TREE style sorting...

Login to post a reply

Server time is: 2022-11-30 12:58:43
Your offset time is: 2022-11-30 12:58:43