Thread: non-recursive free of binary tree

I kind of get it but hoo boy is that weird. I don't even know if I could code that. It's hard enough just to do on paper. Talk about messing with my mind.

Also, is it possible to rotate higher order trees? Like an octree or a quadtree? A google search seems to indicate that there isn't a way, is there?

Originally Posted by MutantJohn

I kind of get it but hoo boy is that weird. I don't even know if I could code that. It's hard enough just to do on paper. Talk about messing with my mind.

Also, is it possible to rotate higher order trees? Like an octree or a quadtree? A google search seems to indicate that there isn't a way, is there?

The general term for describing a tree with n children per node is n-ary (or k-ary, k-way, etc); when the number of children is known, you can say a 4-ary or 8-ary tree. Quadtrees and octrees are generally understood to be specific kinds of 4-ary and 8-ary trees, respectively, that are used for partitioning (e.g. 2-d and 3-d regions respectively). Note, an n-ary tree can also refer to a tree where each node is allowed to have any number of children. Also, remember, a tree is more or less just a graph with no cycles (usually a directed graph with each node having just one parent, and the root of the tree has no incoming edges).

For trees with more than two children per node, it's less clear on what a rotate would consist of. Since there's not just a left and right child, which of the 3, 4, 8, etc, children would you rotate to the root? Which node does the former root become a child of? Theoretically you could reorder any tree, moving a child node up to the root and moving the root down (it's just swapping some pointers around), but I'm not sure I would call it a "rotate". Perhaps a "restructure" would be more appropriate. Whether the resulting tree is of any use is another question. A big part of whether you can usefully restructure a tree, and how you would do so, would depend on the constraints of your tree: ordering of nodes in your tree, balance requirements, relationships between parent and child nodes, etc. A quadtree or octree can not be be restructured (short of swapping sibling nodes, which is trivial and does not fundamentally alter the tree) and maintain it's spatial hierarchy. Other trees, maybe. It would take me a while to churn through a bunch of n-ary tree structures to see if I can find an example that is restructure-able. Not sure if I'll have time today.

Yes, it is NASA code, but for something as mundane as an earth-observing satellite. Sorry, nothing as exciting as a space shuttle or rover. And nothing falls out of the sky if this code doesn't work, as it's part of the ground processing system.

Thank-you. All coded, tested to the n-th degree, and it works like a charm! Very clever solution and very simple also. That's the best kind!

Catherine

Originally Posted by iMalc

Actually, this is dead-easy. Simple pseudocode follows:

Code:

While the root is not null
    if the left node of the root is not null
        perform a right rotation about the root
    else
        delete the root, replacing it with what was the right child of root
Done

Originally Posted by cmoroney

Yes, it is NASA code, but for something as mundane as an earth-observing satellite. Sorry, nothing as exciting as a space shuttle or rover. And nothing falls out of the sky if this code doesn't work, as it's part of the ground processing system.

I figured this was some library available to the public, and you were just using it for some personal project. Not mundane. Satellites are way more awesome than the stuff I work on normally.