Gán kế thừa Inorder (Inorder Successor) cho tất cả nút trong C++

Trong bài toán này, chúng ta được cho một cây. Cấu trúc chứa con trỏ next. Nhiệm vụ là gán con trỏ này với kế thừa Inorder (inorder successor) của nút.

struct node { 
    int value; 
    struct node* left; 
    struct node* right; 
    struct node* next; 
}

Tất cả con trỏ next ban đầu là NULL, ta phải gán con trỏ thành kế thừa Inorder của nút.

Duyệt Inorder - Duyệt theo thứ tự:

Nút trái -> Nút gốc -> Nút phải.

Kế thừa Inorder - Là nút xuất hiện sau nút hiện tại trong duyệt Inorder của cây.

Ví dụ minh họa:

Duyệt Inorder: 7 8 3 5 9 1

Gán cho mỗi nút:

Next của 5 là 9 
Next của 8 là 3 
Next của 7 là 8 
Next của 3 là 5 
Next của 9 là 1

Để giải bài toán, duyệt cây theo thứ tự Inorder ngược. Sau đó gán phần tử vừa duyệt vào next của nút hiện tại.

Chương trình minh họa

#include <iostream> 
using namespace std; 

struct node { 
    int data; 
    node *left; 
    node *right; 
    node *next; 
}; 

node* insertNode(int data) { 
    node* Node = new node(); 
    Node->data = data; 
    Node->left = NULL; 
    Node->right = NULL; 
    Node->next = NULL; 
    return(Node); 
} 

void populateTree(node* pop) { 
    static node *next = NULL; 
    if (pop) { 
        populateTree(pop->right); 
        pop->next = next; 
        next = pop; 
        populateTree(pop->left); 
    } 
} 

void printNext(node * root) { 
    node *ptr = root->left->left; 
    while(ptr) { 
        cout << "Next của " << ptr->data << " là "; 
        cout << (ptr->next ? ptr->next->data : -1) << endl; 
        ptr = ptr->next; 
    } 
} 

int main() { 
    node *root = insertNode(15); 
    root->left = insertNode(99); 
    root->right = insertNode(1); 
    root->left->left = insertNode(76); 
    root->left->right = insertNode(31); 
    cout << "Điền cây bằng cách thêm kế thừa Inorder vào next\n"; 
    populateTree(root); 
    printNext(root); 
    return 0; 
}

Kết quả

Điền cây bằng cách thêm kế thừa Inorder vào next

Next của 76 là 99 
Next của 99 là 31 
Next của 31 là 15 
Next của 15 là 1 
Next của 1 là -1