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

Question

Я читал книгу алгоритмы CORMEN (бинарное дерево поиска главы) и он говорит, что есть два способа обхода дерева без рекурсии:

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

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

Любые подсказки относительно того, как реализовать второй в 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 method on the Object class, чтобы сравнить, являются ли ссылки для любых двух узлов/значений одинаковыми.