Like Tree3Likes

non-recursive free of binary tree

This is a discussion on non-recursive free of binary tree within the C Programming forums, part of the General Programming Boards category; I kind of get it but hoo boy is that weird. I don't even know if I could code that. ...

  1. #16
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    996
    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?

  2. #17
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,427
    Quote Originally Posted by MutantJohn View Post
    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.

  3. #18
    Registered User
    Join Date
    Oct 2013
    Posts
    3
    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.

  4. #19
    Registered User
    Join Date
    Oct 2013
    Posts
    3
    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

    Quote Originally Posted by iMalc View Post
    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

  5. #20
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,427
    Quote Originally Posted by cmoroney View Post
    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.

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 7
    Last Post: 03-28-2013, 05:58 PM
  2. Recursive Binary Tree
    By Sorinx in forum C Programming
    Replies: 12
    Last Post: 11-10-2012, 09:27 AM
  3. recursive vs nonrecursive binary tree traversal
    By gaurav9991 in forum C Programming
    Replies: 4
    Last Post: 05-05-2011, 12:28 PM
  4. Free Binary tree
    By wirefree101 in forum C Programming
    Replies: 1
    Last Post: 12-06-2009, 05:13 PM
  5. binary tree but iterative, not recursive!
    By budala in forum C Programming
    Replies: 2
    Last Post: 08-06-2009, 12:55 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21