Richard Suchenwirth - Binary trees are directed graphs in which one node, the root, has no predecessor, and all others have exactly one predecessor and 0, 1 or 2 successors. They can be used for representing (and quickly searching) sorted information.
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 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
}