Обход дерева
Сравним эффективность обходчиков при обходе полного бинарного дерева высотой N, с операциями «опуститься на уровень ниже влево», «опуститься на уровень ниже вправо» и «подняться на уровень выше».
Теоретическая оценка длины обхода снизу равна количеству дуг 2N+2-4. Эта оценка может быть достигнута, например, при обходе в симметричном порядке [].
В Таблице 2 приведены длины обходов и время их выполнения для разных обходчиков.
| N | dfsm, длина | dfsm, время | ndfsm, длина | ndfsm, время | мин. длина |
| 9 | 4088 | 6 | 2044 | 3 | 2044 |
| 10 | 8184 | 25 | 4092 | 12 | 4092 |
| 11 | 16376 | 100 | 8188 | 45 | 8188 |
| 12 | 32760 | 427 | 16380 | 190 | 16380 |
Таблица 2. Длина и время обхода дерева для разных N.
Обход дерева любопытен тем, что на нем при использовании обходчика ndfsm достигается минимальная длина обхода. Обходчик dfsm делает ровно в два раза больше проходов по дугам.
