+
+Rosetta example:https://rosettacode.org/wiki/Tree_traversal
+
+
+
+
+
+
+
+Implement a binary tree structure, with each node carrying an +integer as a node label, and four traversal strategies: pre-order, +in-order, postorder, and levelorder traversals.
+
+
+
package req nxThe class Tree implements the basic binary composite structure (left, right).
+
+
+
nx::Class create Tree { + :property -accessor public value:required + :property -accessor public left:object,type=[current] + :property -accessor public right:object,type=[current] + + :public method traverse {order} { + set list {} + :$order v { + lappend list $v + } + return $list + } + + # Traversal methods + :public method preOrder {varName script {level 0}} { + upvar [incr level] $varName var + set var ${:value} + uplevel $level $script + if {[info exists :left]} {${:left} preOrder $varName $script $level} + if {[info exists :right]} {${:right} preOrder $varName $script $level} + } + + :public method inOrder {varName script {level 0}} { + upvar [incr level] $varName var + if {[info exists :left]} {${:left} inOrder $varName $script $level} + set var ${:value} + uplevel $level $script + if {[info exists :right]} {${:right} inOrder $varName $script $level} + } + :public method postOrder {varName script {level 0}} { + upvar [incr level] $varName var + if {[info exists :left]} {${:left} postOrder $varName $script $level} + if {[info exists :right]} {${:right} postOrder $varName $script $level} + set var ${:value} + uplevel $level $script + } + :public method levelOrder {varName script} { + upvar 1 $varName var + set nodes [list [current]] + while {[llength $nodes] > 0} { + set nodes [lassign $nodes n] + set var [$n value get] + uplevel 1 $script + if {[$n eval {info exists :left}]} {lappend nodes [$n left get]} + if {[$n eval {info exists :right}]} {lappend nodes [$n right get]} + } + } +}
This is a factory method to build up the object tree recursively
+from a nested Tcl list. Note that we create left and right childs by
+nesting them in their parent, this provides for a cascading cleanup
+of an entire tree (there is no need for an explicit cascading of
+destroy methods down the composite).
+
+
+
Tree public object method newFromList {-parent l} { + lassign $l value left right + set n [:new {*}[expr {[info exists parent]?[list -childof $parent]:""}] -value $value] + set props [list] + if {$left ne ""} {lappend props -left [:newFromList -parent $n $left]} + if {$right ne ""} {lappend props -right [:newFromList -parent $n $right]} + $n configure {*}$props + return $n +}
Run the required tests:
+
+
+
set t [Tree newFromList {1 {2 {4 7} 5} {3 {6 8 9}}}] +% $t traverse preOrder +1 2 4 7 5 3 6 8 9 +% $t traverse inOrder +7 4 2 5 1 8 6 9 3 +% $t traverse postOrder +7 4 5 2 8 9 6 3 1 +% $t traverse levelOrder +1 2 3 4 5 6 7 8 9