There is a standard trinity tree. Add items to it:

TT_insert( tree, "a" ); TT_insert( tree, "aa" ); TT_insert( tree, "b" ); TT_insert( tree, "bb" );

When traversing this tree through nodes "less-equal-more" (well, or left-middle-right, LMR), we encounter elements in this order:

 "aa" "a" "bb" "b"

When walking in the opposite direction (RML), respectively:

 "bb" "b" "aa" "a"

And how to get the items in that order?

 "a" "aa" "b" "bb"

Except how to reverse the array obtained in the second version, nothing comes to mind for the night looking.

PS Laid out the source of the tree . For example:

 #include "ttree.h" static void t_print( TernaryTreeNode node, void * data ) { printf( "%s\n", node->key ); } int main() { TernaryTree t = TT_create( TT_DEFAULTS, NULL ); TT_insert( t, "a", NULL ); TT_insert( t, "aa", NULL ); TT_insert( t, "b", NULL ); TT_insert( t, "bb", NULL ); TT_dump( t, stdout ); TT_reverse_walk( t, t_print, NULL ); TT_destroy( t ); return 0; }

At the exit:

 [21:13:03] Debug $ ./ttree nodes: 5, keys: 4 +-a => [a] |-a => [aa] +-b => [b] +-b => [bb] bb b aa a

Or (this has already added array reversal):

 #include "ttree.h" int main() { TernaryTree t = TT_create( TT_DEFAULTS, NULL ); TT_Data data; size_t keys, i; TT_insert( t, "a", NULL ); TT_insert( t, "aa", NULL ); TT_insert( t, "b", NULL ); TT_insert( t, "bb", NULL ); data = TT_sorted_data( t ); keys = TT_keys( t ); for( i = 0; i < keys; i++ ) printf( "%s\n", data[i].key ); free( data ); TT_destroy( t ); return 0; }

Output:

 a aa b bb
  • Hm What does the structure of your tree look like? - VladD
  • Yes, the most standard threefold :) I posted the source, see the update. - user6550
  • In traversal orders, somewhere the root is lost - not? - Qwertiy ♦
  • No, the root is not lost anywhere, just in the dump is not taken into account. - user6550
  • @klopp: And what is the role of splitter ? (I do not know.) - VladD

1 answer 1

If your tree looks like this:

  a / | \ / | \ * aa b /|\ / | \ * bb *

then you need such a detour:

 static void _TT_walk_preorder( TernaryTreeNode node, TT_Walk walker, void * data ) { if( node ) { walker( node, data ); _TT_walk_preorder( node->left, walker, data ); _TT_walk_preorder( node->mid, walker, data ); _TT_walk_preorder( node->right, walker, data ); } }

PS: Maybe such a detour may also come in handy (for the case when you want the list to be posted):

 static void _TT_walk_inorder( TernaryTreeNode node, TT_Walk walker, void * data ) { if( node ) { _TT_walk_inorder( node->left, walker, data ); walker( node, data ); _TT_walk_inorder( node->mid, walker, data ); _TT_walk_inorder( node->right, walker, data ); } }