[алгоритм]нерекурсивный обход всего двоичного дерева(упорядоченный)

Alexander08

сабж подскажите, а то что-то не соображу...
упорядоченный - значит слева направо для каждого поддерева...

vall

либо свой стэк либо пометки на дереве надо ставить

Alexander08

хм.. про пометки - нет возможности ставить, как со стеком? можешь поподробнее?

yolki

если стек - то рекурсия.
неважно, что стек свой, а не системный.
ну например. пусть у каждого элемента Tree есть Tree->Left, Tree->Right.
тогда обход с рекурсией на системном стеке:

void TreeWalk(Tree*t)

{

  DoSomething(t);

  if(t->Left) TreeWalk(t->Left);

  if(t->Right) TreeWalk(t->Right);

}

Рекурсия на своём стеке. Пусть есть стек Stack элементов Tree.
тогда это выглядит примерно так:

void TreeWalk(Tree *t)

{

  Stack *stack=new Stack;

  Tree *e;

  

  stack->Push(t);

  while(!stack->Empty)

  {

    e=stack->Pop;

    DoSomething(e);

    if (e->Right) stack->Push(e->Right);

    if (e->Left) stack->Push(e->Left);

  }

}

vall

кладёшь в стек вершину и идём в левое её поддерево. если идти некуда - достаём из стека и идём в её правое поддерево.

banderon

Если есть Tree->Left, Tree->Right, Tree->Parent, то можно без стека. Идея примерно такая:

Tree v;

for (v=root; v->Left; v=v->Left); // Находим самый левый элемент

while (v) {

  DoSomething(v);  // Обрабатываем

  if (v->Right) {

     for (v=v->Right; v->Left; v=v->Left); // Находим самый левый элемент в правом поддереве

  } else {

     while v->Parent) && (v->Parent->Right==v v = v->Parent; // Находим корень уже обработанного поддерева

     v = v->Parent; // и переходим к его родителю

  }

}

Работоспособность кода не проверял, но идею постарался передать

Dasar

еще через очередь можно обходить (так называемый обход в ширину)

koly

Только вот в хорошо сбалансированном дереве (наиболее частый случай) размер очереди при обходе в ширину будет превышать размер стека при обходе в глубину.