cs_tdfs.c
Go to the documentation of this file.00001 #include "cs.h" 00002 /* depth-first search and postorder of a tree rooted at node j */ 00003 int cs_tdfs (int j, int k, int *head, const int *next, int *post, int *stack) 00004 { 00005 int i, p, top = 0 ; 00006 if (!head || !next || !post || !stack) return (-1) ; /* check inputs */ 00007 stack [0] = j ; /* place j on the stack */ 00008 while (top >= 0) /* while (stack is not empty) */ 00009 { 00010 p = stack [top] ; /* p = top of stack */ 00011 i = head [p] ; /* i = youngest child of p */ 00012 if (i == -1) 00013 { 00014 top-- ; /* p has no unordered children left */ 00015 post [k++] = p ; /* node p is the kth postordered node */ 00016 } 00017 else 00018 { 00019 head [p] = next [i] ; /* remove i from children of p */ 00020 stack [++top] = i ; /* start dfs on child node i */ 00021 } 00022 } 00023 return (k) ; 00024 }