Задача с обходом Эйлера-дерева на основе стека

Question

Мне нужна функция, которая пересекает двоичное дерево с обходом Эйлера (, как это работает ).Конечно, это легко достижимо с помощью рекурсии - я знаю, как это работает.Но теперь я хочу реализовать итеративную версию этого алгоритма, используя стек вместо рекурсии.Моя идея состояла в том, чтобы сохранить направление, в котором мы движемся в стеке.Мой код не работает, и я как-то не могу обдумать эту проблему.Можете ли вы дать мне какие-либо советы о том, как решить эту проблему?Вот мой код:

#define LEFT (struct Node*) 0xBADF00D
#define RIGHT (struct Node*) 0xDEADBEEF

struct Node { 
    int data; 
    struct Node* parent; 
    struct Node* left; 
    struct Node* right; 
}; 

void eulerTree(struct Node* root) 
{ 
    stack<struct Node*> s;

    s.push(root);
    s.push(RIGHT);
    s.push(root);
    s.push(LEFT);

    while(!s.empty()) {
        struct Node* direction = s.top(); s.pop();
        struct Node* node = s.top(); s.pop();

        visit(node);

        if(direction == LEFT) {
            if(node->left) {
                s.push(node->left);
                s.push(RIGHT);

                s.push(node->left);
                s.push(LEFT);
            }
        } 

        if(direction == RIGHT) {
            if(node->right) {
                s.push(node->right);
                s.push(RIGHT);

                s.push(node->right);
                s.push(LEFT);
            }
        }
    }
}

Answer 1

Рекурсивная реализация может выглядеть так:

void euler(Node *n) {
    visit(n);
    if (n->left) {
        euler(n->left);
        visit(n);
    }
    if (n->right) {
        euler(n->right);
        visit(n);
    }
}

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

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

Мы, конечно, должны помнить, над каким узлом мы работали, но также есть два рекурсивных вызова, поэтому есть 2 возможных места, которые нам, возможно, придетсяВернуться к.Когда мы возвращаемся из рекурсивного вызова, то либо:

1. Мы только что сделали вызов n->left и должны продолжить проверять n->right;ИЛИ
2. Мы только что позвонили n->right и должны продолжить с последним визитом n

Мы могли бы сохранить некоторую дополнительную информацию остек, чтобы различать эти два случая, но это не обязательно для этого конкретного алгоритма.Из приведенного выше описания видно, что мы можем различать эти случаи на основе узла, с которого мы возвращаемся - это либо n->left, либо n->right.

Итак, просто сохраняем ожидающий узел вСтек, мы можем написать итерационную версию, как это:

int state=0; // 0 => initial visit, 1 => just did left, 2 => just did right
Node *n = root;
while (n) {
    visit(n);

    if (n->left && state<1) {
        stack.push(n);
        n=n->left;
        state=0;
        continue;
    }

    if (n->right && state<2) {
        stack.push(n);
        n=n->right;
        state=0;
        continue;
    }

    if (stack.empty())
        break; // done

    Node *child=n;
    n = stack.pop();
    state = (child == n->left ? 1 : 2);
}

Answer 2

Подумайте о простом двоичном дереве, с которого нужно начать:

           1
        2     3

Обход Эйлера для этого: 1 2 1 3 1

Здесь вы видите шаблон: root, root->left, root, root->right, root

Таким образом, ваш порядок стеков должен быть:

root
root->left
root
root->right
root

Но что, если ваш корень - лист?затем ничего не нажимайте, просто напечатайте значение.

Также, как только вы нажмете узлы слева, направо, убедитесь, что вы установили их как 0 для корня, чтобы вы не продолжали нажимать их вечно.

С учетом вышесказанного код в cpp будет:

Редактировать:

Предыдущий код, который я разместил, содержит ошибку.Ниже приведен правильный код:

void eulerTree(struct Node* root) 
{ 
    stack<struct Node*> s;

    s.push(root);


    while(!s.empty()) {

        struct Node* node = s.pop();

        visit(node);

        if(node->right) {
          s.push(node);
          s.push(node->right);
        }

        if(node->left) {
          s.push(node);
          s.push(node->left);
        }
        node->left = 0;
        node->right = 0;
    }
}

Без разрушения дерева:

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

1. Если лист остается дочерним от родителя и правым дочерним от этого родителяимеет значение null

   (или)

   если лист является правым потомком

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

2. Если лист является левым дочерним элементом, а правый дочерний элемент не нулевым

   - после печати этого листа выведите только его непосредственного родителя.

Чтобы проиллюстрировать это, посмотрите на дерево ниже.

1 2 3 4 5 6 7

Если лист равен 5, то после его печати распечатайте всех родителей до 1.

Если лист равен 4, то после его печати выведите только его непосредственного родителя 2.

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

void eulerTree(struct Node* root) {
  stack<struct Node*> s;
  s.push(root);
  struct Node* original = root;
  stack<struct Node*> p;

  while(!s.empty()) {
    struct Node* node = s.top();
    s.pop();

    visit(node);

    if ( !node->right && !node->left && !p.empty() ) {
      struct Node* pNode = p.top();
      if ( pNode->left == node && !pNode->right  || pNode->right == node ) {
        while ( !p.empty() ) {
          visit(p.top());
          p.pop();
        }
        p.push(original);
      } else {
        visit(pNode);
      }
    }

    if(node->left || node->right) {
      p.push(node);
    }

    if(node->right) {
      s.push(node->right);
    }

    if(node->left) {
      s.push(node->left);
    }
  }
}