Как одновременно пройти через двоичное дерево с помощью рекурсии и сохранить ключ в массив?

Question

Как одновременно пройти через двоичное дерево с помощью рекурсии и сохранить ключ в массив?

Мой код должен найти значение в дереве AVL, которое строго выше, чем введенное значение. Я попытался использовать подход обхода inorder он застрял при сохранении данных в массив

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

void TreeSet::inorderRec(AVLNode *root, int *arr, int pos) {
if (root) {
inorderRec(root->left, arr, pos);
arr[pos++] = root->key;
inorderRec(root->right, arr, pos + 1);
}
}

int TreeSet::higher(int val) {
// TODO
AVLNode *temp = root;
int *arr = new int[count];
int pos = 0;
if (root) {
inorderRec(root, arr, pos);
for (int i = 0; i < count; i++)
if (arr[i] > val)
return arr[i];
}
return -1;
}

Я ожидал получить массив в порядке и найти значение, которое я хочу

-4

avl-tree binary-tree c++dsa inorder

Решение

Другие решения

Если я правильно понимаю ваш код, ожидается переопределение:

void TreeSet::inorderRec(AVLNode *root, int *arr, int pos) {
// lets be pos = 0
if (root) {
inorderRec(root->left, arr, pos); // call with pos = 0
arr[pos++] = root->key;           // write to arr[0], then set pos = 1
inorderRec(root->right, arr, pos + 1); // call with pos = 2
}
}

Таким образом, левая большая часть вашего дерева всегда записывает в arr [0].
Я ожидаю, что вы только заполните каждый второй массив новыми значениями.

Может быть, вы хотите использовать указатель на pos?

void TreeSet::inorderRec(AVLNode *root, int *arr, int* pos) {
// lets be pos = 0
if (root) {
inorderRec(root->left, arr, pos); // call with *pos = 0, pos is set to n
arr[(*pos)++] = root->key;           // write to arr[n], then set *pos = n+1
*pos = *pos +1;
inorderRec(root->right, arr, pos); // call with *pos = n+2
}
}

0

Источник

Accepted Answer

Вам нужны изменения в pos распространять обратно вверх по стеку вызовов

// note that we pass pos by reference
void TreeSet::inorderRec(AVLNode *root, int *arr, int& pos) {
if (root) {
inorderRec(root->left, arr, pos);
arr[pos++] = root->key;
inorderRec(root->right, arr, pos);
}
}

Или вы можете устранить pos и просто обновить arr

void TreeSet::inorderRec(AVLNode *root, int *& arr) {
if (root) {
inorderRec(root->left, arr);
*arr++ = root->key;
inorderRec(root->right, arr);
}
}

Что обобщает на любой OutputIterator

template <typename OutputIterator>
void TreeSet::inorderRec(AVLNode *root, OutputIterator & it) {
if (root) {
inorderRec(root->left, it);
*it++ = root->key;
inorderRec(root->right, it);
}
}

0