Являются ли узлы в стеке для итеративного обхода после заказа всегда предками, и нет другого узла для какого-либо узла? - PullRequest
Новая
       19

Являются ли узлы в стеке для итеративного обхода после заказа всегда предками, и нет другого узла для какого-либо узла?

1 голос
/ 24 июля 2011

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

РЕДАКТИРОВАТЬ: Есть ли другой способ отслеживать предков? Это не BST.

Ответы [ 2 ]

0 голосов
/ 01 декабря 2011

Я думаю, что это возможно, вот мои коды: 

Node* getRightSibling(Node* parent,Node* child){
  if(parent->right == child)
    return NULL;
  else if(parent->left == child)
    return parent->right;
  return NULL;
}

void iterativePostOrder(Node* root) {
  stack<Node*> nodeStack;
  Node* current = root;

  while (true) {
    if(current != null){
      nodeStack.push(current);
      if(current->left != NULL)        //push left  sub-tree
        current = current->left;
      else if(current->right != NULL)  //push right sub-tree
        current = current->right;  
      continue;
    }

    if(nodeStack.empty()) return;

    current = nodeStack.pop();
    visitNode(current);

    Node* parent = nodeStack.top();
    Node* rightSibling = getRightSibling(parent,current);
    if(rightSibling == null) {
      //two case:
      //  1. parent has no right child
      //  2. current is the parent's right child, we complete access
      //     right sub-tree.
      //in either case we need access parent, and because parent is at
      //the top of Stack, so:

      current = NULL;

    }else{
       // we need start to access right-subtree.
       current = rightSibling;
    }
}

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

0 голосов
/ 24 июля 2011

Один из способов отслеживания предков в графе состоит в том, чтобы каждый узел сохранял указатель на своего родителя. Таким образом, с любого узла вы можете вернуться обратно к корню, просто итеративно следуя указателю родителя. Время прохождения такого пути - O (d), где d - глубина узла. Если вы точно знаете, что будете часто переходить от узлов к корню, такой подход стоит рассмотреть.

Что касается вашего исходного вопроса, да, вы можете использовать итеративный обход пост-заказа, чтобы найти путь от любого узла до корня. Любой узел в стеке будет либо самим узлом, либо каким-либо предком, и они будут в правильном порядке. Однако это существенно менее эффективно, чем просто хранить родительские указатели. Нахождение узла может занять O (n) времени в дереве с n узлами, которое плохо масштабируется с размером дерева относительно решения O (d), изложенного выше.

РЕДАКТИРОВАТЬ : Я неправильно понял, что вы имели в виду под повторяющимся порядком. Это также легко можно сделать с помощью рекурсивного обхода после заказа, когда вы передаете стек по ссылке вниз по цепочке вызовов. Вот пример на C ++: 

void RecSearchWithHistory(Node* curr, vector<Node*>& history) {
    // Base case: if the node is NULL, we're done.
    if (curr == NULL) return;

    // Mark that we've been to the current node.
    history.push_back(curr);

    // If we found what we are looking for, we now have the path
    // to the root available!
    if (/* some predicate */)
        /* ... use history ... */

    // Visit both children (assuming this is a binary tree; the
    // generalization fir multi-way trees is easy.
    RecSearchWithHistory(curr->left, history);
    RecSearchWithHistory(curr->right, history);

    // Finally, pop the stack since we are done using this node.
    history.pop_back();
}
...