Двоичный поиск дерева, который сравнивает два указателя на равенство

Question

Я читаю книгу алгоритмов Кормена (глава о бинарном дереве поиска), в которой говорится, что существует два способа обхода дерева без рекурсии:

используя стек и более сложный, но элегантный Решение, которое не использует стек, но предполагает, что два указателя могут быть проверено на равенство

Я реализовал первый вариант (с использованием стека), но не знаю, как реализовать последний. Это не домашнее задание, просто чтение, чтобы научиться.

Есть какие-нибудь подсказки относительно того, как реализовать второй в C #?

Answer 1

Конечно. Вы не сказали, какой тип обхода вы хотели, но вот псевдокод для обхода в порядке.

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;
  }
}

Чтобы получить предварительный или последующий заказ, необходимо изменить порядок блоков.

Answer 2

Предполагая, что узлы в дереве являются ссылками, а значения являются ссылками, вы всегда можете вызвать статический метод ReferenceEquals для класса Object , чтобы сравнить, чтобы увидеть, являются ли ссылки для любых двух узлов / значений то же самое.