4

I have a Tree containing a Large Number of nodes, and I Trying to get The Best post-order Traversal Algorithm.

NOTE:

  1. The Algorithm Shouldn't consider Recursion Due to large number of Nodes may cause StackOverFlow Exception.
  2. The Algorithm Shouldn't consider a view Flag.
  3. The Algorithm Shouldn't mess with the Tree. i want it as it is.
  4. Algorithm should use memory wisely.
  5. In a node I can get my parent.
Aboelnour
  • 1,423
  • 3
  • 17
  • 39
  • 1
    Unless your tree is literally thousands of levels deep, recursion shouldn't be a problem. – biziclop Feb 18 '12 at 21:38
  • What Did You already Consider and Attempted to Do, by The Way? If the Tree is Deep Enough to Eat up All your Stack, Continuation Passing is your Friend. Consider Answers to the Following Stack OverFlow Question: http://stackoverflow.com/questions/9323036/tail-recursive-function-to-find-depth-of-a-tree-in-ocaml – kkm inactive - support strike Feb 18 '12 at 22:06
  • Just Traversing an Abstract Syntax Tree.. + I read this and I'm asking if anyone solve it for post-order Traversal "In 1968, Knuth posed the problem of designing a stack-free, tag-free, non-recursive algorithm that traversed the tree in in-order while leaving it unaltered in the end." – Aboelnour Feb 18 '12 at 22:27

2 Answers2

3

availability of parent allows to iterate, without a stack: this algorithm assume each node has Parent, FirstChild, NextSibling

#include <stdio.h>

struct Node {
    int Data; Node *FirstChild, *NextSibling, *Parent;
};

void use_data(Node *node) {
    printf("%d\n", node->Data);
}

int main_visit_post(int, char **) {
    Node G[] = {
        {0, G+1,   0,   0},
        {1, G+2, G+3, G+0},
        {2,   0, G+4, G+1},
        {3, G+8,   0, G+0},
        {4, G+5, G+7, G+1},
        {5,   0, G+6, G+4},
        {6,   0,   0, G+4},
        {7,   0,   0, G+1},
        {8, G+9,   0, G+3},
        {9,   0,   0, G+8},
    };

    Node *node = G, *next;
    while (node) {
        next = node->FirstChild;
        if (!next) {
            use_data(node);
            next = node->NextSibling;
            if (!next) {
                while (node->Parent) {
                    next = node->Parent;
                    use_data(next);
                    if (next->NextSibling) {
                        next = next->NextSibling;
                        break;
                    }
                    else {
                        node = next;
                        next = 0;
                    }
                }
            }
        }
        node = next;
    }
    return 0;
}

this tree get this sequence: 2,5,6,4,7,1,9,8,3,0

enter image description here

CapelliC
  • 59,646
  • 5
  • 47
  • 90
0

One way of solving this without using flag or recursion is simply to use stack. For postorder, we can use two stacks. One stack for operating on input and other one to generate output.

You find the details of the code here

saurcery
  • 2,025
  • 2
  • 14
  • 10