** Summary ** [Richard Suchenwirth]: Binary trees are directed graphs (see [Graph theory in Tcl]) in which one node, the ''root'', has no predecessor, and all others have exactly one predecessor, and each node may have 0, 1 or 2 successors. They can be used for representing (and quickly searching) sorted information, or for representing [decision trees]. ** See Also ** [Trees as nested lists]: not necessarily binary trees ** Description ** Here are some routines that create a binary tree from a list, convert it back to a list, and search it (though I'm afraid [lsearch] will be faster and simpler in most cases...) You might find the extended use of [expr] as control structure, with multiple a?b:c operators, interesting. ====== proc btree L { if {[llength $L]>1} { set L [lsort $L] set center [expr [llength $L]/2] list [lindex $L $center] \ [btree [lrange $L 0 [expr {$center-1}]]]\ [btree [lrange $L [expr {$center+1}] end]] } else {set L} } proc bt2list bt { expr { [llength $bt]? [concat [bt2list [lindex $bt 1]]\ [list [lindex $bt 0]]\ [bt2list [lindex $bt 2]]\ ] : [list] } } proc btsearch {bt x} { set root [lindex $bt 0] expr { [llength $bt]? $root > $x? [btsearch [lindex $bt 1] $x] : $root < $x? [btsearch [lindex $bt 2] $x] : 1 : 0 } } if 0 { Test and usage examples: % btree {5 4 3 2 1 6 7} 4 {2 1 3} {6 5 7} % btree {foo bar grill this and that or not} not {foo {bar and {}} grill} {that or this} % bt2list [btree {foo bar grill this and that or not}] and bar foo grill not or that this % btsearch [btree {foo bar grill this and that or not}] grill 1 % btsearch [btree {foo bar grill this and that or not}] grille 0 } ====== <> Graph theory | Concept | Arts and Crafts of Tcl-Tk Programming