private void postTraversalProcessing ( ) { int nc1 = treeSize ; info [ KR ] = new int [ leafCount ] ; info [ RKR ] = new int [ leafCount ] ; int lc = leafCount ; int i = 0 ; // compute left-most leaf descendants // go along the left-most path, remember each node and assign to it the path's // leaf // compute right-most leaf descendants (in reversed postorder) for ( i = 0 ; i < treeSize ; i ++ ) { if ( paths [ LEFT ] [ i ] == - 1 ) { info [ POST2_LLD ] [ i ] = i ; } else { info [ POST2_LLD ] [ i ] = info [ POST2_LLD ] [ paths [ LEFT ] [ i ] ] ; } if ( paths [ RIGHT ] [ i ] == - 1 ) { info [ RPOST2_RLD ] [ treeSize - 1 - info [ POST2_PRE ] [ i ] ] = ( treeSize - 1 - info [ POST2_PRE ] [ i ] ) ; } else { info [ RPOST2_RLD ] [ treeSize - 1 - info [ POST2_PRE ] [ i ] ] = info [ RPOST2_RLD ] [ treeSize - 1 - info [ POST2_PRE ] [ paths [ RIGHT ] [ i ] ] ] ; } } // compute key root nodes // compute reversed key root nodes (in revrsed postorder) boolean [ ] visited = new boolean [ nc1 ] ; boolean [ ] visitedR = new boolean [ nc1 ] ; Arrays . fill ( visited , false ) ; int k = lc - 1 ; int kR = lc - 1 ; for ( i = nc1 - 1 ; i >= 0 ; i -- ) { if ( ! visited [ info [ POST2_LLD ] [ i ] ] ) { info [ KR ] [ k ] = i ; visited [ info [ POST2_LLD ] [ i ] ] = true ; k -- ; } if ( ! visitedR [ info [ RPOST2_RLD ] [ i ] ] ) { info [ RKR ] [ kR ] = i ; visitedR [ info [ RPOST2_RLD ] [ i ] ] = true ; kR -- ; } } // compute minimal key roots for every subtree // compute minimal reversed key roots for every subtree (in reversed postorder) int parent = - 1 ; int parentR = - 1 ; for ( i = 0 ; i < leafCount ; i ++ ) { parent = info [ KR ] [ i ] ; while ( parent > - 1 && info [ POST2_MIN_KR ] [ parent ] == - 1 ) { info [ POST2_MIN_KR ] [ parent ] = i ; parent = info [ POST2_PARENT ] [ parent ] ; } parentR = info [ RKR ] [ i ] ; while ( parentR > - 1 && info [ RPOST2_MIN_RKR ] [ parentR ] == - 1 ) { info [ RPOST2_MIN_RKR ] [ parentR ] = i ; parentR = info [ POST2_PARENT ] [ info [ RPOST2_POST ] [ parentR ] ] ; // get parent's postorder if ( parentR > - 1 ) { parentR = treeSize - 1 - info [ POST2_PRE ] [ parentR ] ; // if parent exists get its // rev. postorder } } } }
Gathers information that couldn t be collected while tree traversal .