Как одновременно пройти через двоичное дерево с помощью рекурсии и сохранить ключ в массив?
Мой код должен найти значение в дереве 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;
}
Я ожидал получить массив в порядке и найти значение, которое я хочу
Решение
Вам нужны изменения в 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);
}
}
Другие решения
Если я правильно понимаю ваш код, ожидается переопределение:
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
}
}