ストラー数
この文脈におけるすべての木は、有向グラフである。葉に向かって、根から方向付けされている。言い換えれば、有向木(英語版)である。ある木のあるノードの次数は、ちょうど子の数である。ある木のすべてのノードにストラー数を割り当ててもよい。ボトムアップオーダーでは、次のようになる。
ノードが葉 (子を持ってない) なら、そのストラー数は 1 である。
ノードがストラー数 i で 1 つの子を持っており、すべてのほかの子が i より低いストラー数を持っているならば、そのノードのストラー数は i である。
ノードがストラー数 i で 2 つ以上の子を持ち、より大きい数を持つ子がいない場合、そのノードのストラー数は i+1 である。
アルゴリズム的には、これらの数は post-order による深さ優先探索を行うことで割り当てられる。同じ数が、木がステージのシーケンスで単純化される中での枝刈り過程で生成される。そこでは各ステージで、全葉ノードおよび次数 1 の深さのすべての葉につながるノードを除外する。ノードのストラー数は、ステージである。