Как одновременно пройти через двоичное дерево, используя рекурсию, и сохранить ключ в массив? - PullRequest
Новая
       105

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

0 голосов
/ 21 декабря 2018

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

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

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;
}

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

Ответы [ 2 ]

0 голосов
/ 21 декабря 2018

Вам необходимо внести изменения в 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 голосов
/ 21 декабря 2018

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

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
    }
}
...