Вопрос о древовидной структуре данных: Как мы можем заполнить все указатели преемников inorder всех узлов дерева?

Question

Узел дерева содержит 3 указателя * влево, * вправо и * преемник.

Struct node{
     int data;
     struct node *left;
     struct node *right;
     struct node *successor; 
}; 


        A
       /  \
      B    C
     / \  / \
    D   E F  G

Обход INORDER: DBEAFCG * Примечание: * Преемниками наследства являются F, C и G.

  **Function prototype:** void  FillSuccessorNodes( struct node *root);

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

случай 1) некоторые из указателей-преемников могут быть NULL . В этом случае вы должны заполнить этот указатель немедленным преемником Inorder.

Пример: если A-> Successor == NULL, тогда заполните A-> Successor = F

вариант 2) некоторые указатели наследника могут уже указывать на правильных наследников. В этом случае вам не нужно изменять указатели-преемники.

Пример: 1) A-> successor = F действителен

     2) A->successor = C is valid

     3) A-successor = G is valid  . All these three cases you no need to modify successor pointer since these already pointing to correct successor nodes.  

case 3) Некоторые из указателей преемника не NULL , но эти указатели указывают на преемников INVALID, т. Е. Это может быть преемник неупорядоченного значения или какое-либо значение мусора. В этом случае вы должны заполнить эти узлы непосредственными преемниками.

Пример: * * тысяча двадцать-восемь

     1) A->successor = B is invalid since B is not successor node , so we have to correct it to A->successor = F.

     2) A->successor = 0x23237463478 is invalid since it is pointing to garbage value. So we we have to correct it to A->successor = F. 

1) Интервьюер спросил меня, эффективное время в O (N) времени сложности. Допускается дополнительное пространство. 2) она дала намек, то есть мы можем использовать HASHing.

Если вы знаете решение этой проблемы, пожалуйста, дайте мне знать.

Answer 1

Требуется лишь небольшая модификация обхода порядка, вы должны запомнить предшественник и установить значение precessot-> successor = current.

stack<node*> s;
node* t = root ,*pred=NULL;
while(true)
{
    if(t){
            s.push(t);
            t= t->left; 
            continue;
    }           
    if(s.empty()) { break;}
    t= s.top();
    if(NULL != pred && pred->succesor != t)
    {
        pred->succesor = t;     
    }
    pred  = t; 
    s.pop();        
    cout<<t->c;
    t= t->right; 
}

Answer 2

Вопрос и подсказка кажутся мне вводящими в заблуждение. Поскольку вы все равно должны проверить все узлы, чтобы проверить, являются ли их преемники недействительными, и поскольку вам нужно вычислить преемника, чтобы узнать, что означает недопустимый, вы могли бы также использовать стандартный O (n) -обход обхода, например ::

#include <utility>
using namespace std;

typedef pair<node*, node*> node_pair;

node_pair setInOrderSuccessors(node* root)
{
    node_pair result(root, root);

    if (root->left) {
        const node_pair pair = setInOrderSuccessors(root->left);
        result.first = pair.first;
        pair.second->successor = root;
    }

    if (root->right) {
        const node_pair pair = setInOrderSuccessors(root->right);
        result.second = pair.second;
        root->successor = pair.first;
    }

    return result;
}

void  FillSuccessorNodes(node *root)
{
    const node_pair pair = setInOrderSuccessors(root);
    pair.second->successor = 0;
}