Обход дерева двоичного поиска, который сравнивает два указателя для равенства
Я читаю книгу алгоритмов Cormen (глава дерева двоичного поиска), и она говорит, что существует два способа пересечь дерево без рекурсии:
использование стека и более сложного, но изящного решения, которое не использует стека, но предполагает, что два указателя могут быть протестированы на равенство
Я реализовал первую опцию (использующий стек), но не знаю, как реализовать последнего. Это не домашняя работа, просто читая для обучения.
Какие-либо подсказки относительно того, как реализовать второй в C#?
2 ответа
Конечно. Вы не сказали, какой обход вы хотите, но вот псевдокод для обхода по порядку.
t = tree.Root;
while (true) {
while (t.Left != t.Right) {
while (t.Left != null) { // Block one.
t = t.Left;
Visit(t);
}
if (t.Right != null) { // Block two.
t = t.Right;
Visit(t);
}
}
while (t != tree.Root && (t.Parent.Right == t || t.Parent.Right == null)) {
t = t.Parent;
}
if (t != tree.Root) { // Block three.
t = t.Parent.Right;
Visit(t);
} else {
break;
}
}
Чтобы получить предварительный или пост-заказ, вы меняете порядок блоков.
Предполагая, что узлы в дереве являются ссылками, а значения - ссылками, вы всегда можете вызвать статический метод ReferenceEquals класса Object, чтобы сравнить, одинаковы ли ссылки для любых двух узлов/значений.