C ++ - резьбовое дерево, упорядоченный обход

Question

Я только что реализовал многопоточное дерево в C ++, и теперь я пытаюсь cout все элементы по порядку.

Дерево было двоичным отсортированным деревом (не сбалансированным) до того, как я 'я проделал это.

Я пытался сделать это:

E min = _min(root); //returns the minimum element of the tree
E max = _max(root); //returns the maximum element of the tree

while (min != max)
{
  std::cout << min << ", ";
  min = _successor(root, min);
}
std::cout << max << ", ";
std::cout << std::endl;

, но так как дерево теперь пронизано, моя функция-преемница всегда возвращает минимум всего дерева (в основном, это происходитодин раз в правом поддереве, а затем входит в левое поддерево столько раз, сколько возможно, пока не найдет лист.) Поэтому, когда я пытаюсь вызвать эту функцию, она только cout 1 (потому что 1 является минимальным значением моегодерево).

Кроме того, я пробовал кое-что еще:

  E min = _min(root); //returns min element of the tree
  E max = _max(root); //returns max element of the tree
  Node* tmp = _getNode(root, min); //returns the node of the specified element, therefore the minimum node of the tree
  while(tmp->data < max)
  {
           std::cout << tmp->data << ", ";
           tmp = _getNode(root, tmp->data)->rightChild; //gets the right child node of tmp
  }
  std::cout << tmp->data << ", ";

Однако, делая это, есть значения, которые игнорируются.(См. Изображение ниже)

(Зеленые ссылки были добавлены после создания потока дерева.) Если вы видите, например, узел № 6 никогда не посещается из самого последнего алгоритма, потому что этоне правый потомок любого узла в дереве ...

Вот вывод предыдущей функции:

1, 2, 3, 5, 7, 8, 11, 71

Кто-нибудь имеет представление о том, как я мог это исправить, или любойСоветы по моей проблеме?

Спасибо

РЕДАКТИРОВАТЬ: В конце концов мне просто пришлось пройтись по дереву от минимума до максимума И изменить мои методы _predecessor и _successor, чтобы они не регистрировалисьподдеревья с резьбой.:)

Надеюсь, это поможет будущим читателям.

Answer 1

Попробуйте

Node* n = _min(root);
while (n->right) {
    cout << n->val << ", ";
    n = _successor(n);
}
cout << n->val << endl;

Это в основном ваш первый код (обратите внимание, что я предполагаю, что дерево непусто, как и вы). Это также не даст вам трейлинг ",".

Важно правильно настроить функцию-преемник. Так должно быть

Node* _successor(Node* n) {
    if (is_thread(o, RIGHT)) return o->right;
    return _min(o->right);
}

А для полноты

Node* _min(Node* n) {
    while (!is_thread(o, LEFT)) n = o->left;
    return n;
}

Для обоих из них все зеленые стрелки являются нитями.

Answer 2

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

1. Начать с корня.к нулю.Этот элемент является минимальным значением дерева.
2. Перейдите по всем правильным ссылкам, пока не дойдете до корня.Если вы построили дерево правильно, это должно пройти каждый элемент в возрастающем порядке.
3. Повторите шаги 2 и 3 в обратном направлении (найдите элемент max, идите назад).эти два списка с корнем посередине.

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

Answer 3

В конце концов мне просто пришлось пройтись по дереву от минимума до максимума И изменить мои методы _predecessor и _successor, чтобы они не проверяли вложенные поддеревья.:)

Надеюсь, это поможет будущим читателям.