Архив форумов ЦИТФорума

[M434F4k3R]

Пожалуйста, подкиньте нерекурсивную функцию концевого обхода дерева двоичного поиска.
Прямой, обратный обход... С этим всё ясно, а вот концевой...

Дерево задано следующей простенькой структурой:

struct BinTree
{ unsigned Key; // значение ключа
BinTree* Left; // указатель на левого потомка
BinTree* Right; // указатель на правого потомка
}

Единственный параметр функции - указатель на корень дерева.
Скорее всего понадобится стек. Его описание можно не прилагать. Просто пишем push или pop где необходимо.
Функцию желательно на C++ под дос или в крайнем случае BP7. Псевдокод - тоже хорошо.

Заранее благодарен.

[Дядя Вася]

попробуй не стек использовать, а очередь !
применяя алгоритм обхода дерева в ширину
push(root)
while(очередь не пуста){
node = pop();
if (нету потомков) { че-нить делать}
else{
push(node.left);
push(node.right);
}
}

ну вот и все, если элементы надо иметь по порядку то в {че-нить делать} нужно элемент ложить в массив , вычисляя по положению в дереве, его адрес ...