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.
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
}Binary trees using Tclx's keyed lists: [L1 ]
Binary trees using Tcl and C via SWIG: [L2 ]
Tcl implementation of an AVL tree data structure: [L3 ]