Двоичное дерево - Обратный обход с прямым итератором? - PullRequest
Новая
       53

Двоичное дерево - Обратный обход с прямым итератором?

0 голосов
/ 12 апреля 2020

Я реализовал struct Node<class A, class B> с ключом A и данными B, содержащими узлы left, right и parent.

Для дерева, которое может быть построено с узлами Я хочу реализовать класс итератора BTIT, также как шаблон с A и B. Я реализовал begin и rbegin, возвращая самые левые и самые правые узлы в дереве соответственно. end и rend возвращают BTIT(nullptr), чтобы знать, когда в конце.

operator++ для класса итератора реализован как 

BTIT<A, B>& operator++() {
  curr = curr->nodeN();
  return *this;
}

вместе с алгоритмом для поиска следующего узла в дереве следующим образом 

Node<A, B>* nextN() {
  Node<A, B> *curr = this;
  if (curr == nullptr) {
    return curr;
  };
  if (curr->right != nullptr) {
    curr = curr->right;
    while(curr->left != nullptr) {
      curr = curr->left;
    };
  }
  else {
    Node<A, B> *par = curr->parent;
    while (par != nullptr && curr == par->right) {
      curr = par;
      par = par->parent;
    };
    curr = par;
  };
  return curr;
};

Это прекрасно работает для итерации в for-l oop, используя begin и end для печати значений данных дерева B в приказ. Тем не менее, operator++ также должен работать в обратном порядке, то есть для rbegin и rend, но тогда он печатает только самый правый узел и останавливается. Я вижу, как алгоритм выше не будет работать для обратного порядка. Мой вопрос, как это может быть увеличено, чтобы работать как для begin / end и rbegin / rend? В чем идея? Мне трудно разобраться с этим и с чего начать.

РЕДАКТИРОВАТЬ: Я реализовал алгоритм обратного обхода следующим образом 

Node<A, B>* prevN() {
  Node<A, B> *curr = this;
  if (curr == nullptr) {
    return curr;
  };
  if (curr->left != nullptr) {
    curr = curr->left;
    while(curr->right != nullptr) {
      curr = curr->right;
    };
  }
  else {
    Node<A, B> *par = curr->parent;
    while (par != nullptr && curr == par->left) {
      curr = par;
      par = par->parent;
    };
    curr = par;
  };
  return curr;
};

, который работает для итерации в for-l oop с rbegin и rend с уменьшением (--it) объекта итератора. Теперь я хочу работать, печатая в обратном порядке, используя также 

for (auto it = root->rbegin(); it != root->rend(); ++it) {
    cout << *it << endl;

. Возможно ли это?

...