后序遍历的递归算法和非递归算法

发布网友发布时间：2022-06-19 20:16

共1个回答

热心网友时间：2024-11-29 09:29

随便手写一下

struct node_s { data_t data; size_t nchildren; struct node_s *children[MAX]; };

// recursive traverse
// given callback function _access_ with arbitary data _ctx_
void traverse_r( struct node_s *root, void (*access)( struct node_s *node, void *ctx ), void *ctx ) {
int i;
if ( !root ) return;
for ( i=0; i<root->nchildren; i++ )
traverse_r( root->children[i], access, ctx );
access( root, ctx );
}

// needed stack operations
#define stackdef(s,sz) struct elem_s s#_base[sz]; size_t s#_top = 0
#define empty(s) (s##_top==0)
#define push(s,p,i) do{\
struct elem_s *s##_cur = &s##_base[s##_top++];\
s##_cur->node = (p), s##_cur->inext = (i);\
}while(0)
#define pop(s,pp,pi) do{\
struct elem_s *s##_cur = &s##_base[--s##_top];\
*(pp) = s##_cur->node, *(pi) = s##_cur->inext;\
}while(0)
// and data type.
struct elem_s { struct node_s *node; size_t inext; };

// non-recursive traverse
// given callback function _access_ with arbitary data _ctx_
void traverse_s( struct node_s *root, void (*access)( struct node_s *node, void *ctx ), void *ctx ) {
stackdef( s, MAXDEPTH );
struct node_s *cursor; size_t index;
push( s, root, 0 );

while ( ! empty( s ) ) {
pop( s, &cursor, &index );
if ( !cursor ) continue;
if ( cursor->nchildren <= index )
access( cursor, ctx );
else {
push( s, cursor, index + 1 );
push( s, cursor->children[0], 0 );
}
}
}