Populate Inorder Successor สำหรับทุกโหนดใน C++

ในปัญหานี้ เราได้รับต้นไม้ โครงสร้างมี pointer next งานของเราคือเติม pointer นี้ด้วย inorder successor ของโหนด

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

Pointer next ทั้งหมดถูกตั้งค่าเป็น NULL และเราต้องตั้งค่า pointer ให้เป็น inorder successor ของโหนด

Inorder traversal - ท่องในรูปแบบต่อไปนี้:

Left node -> root Node -> right node.

Inorder successor - inorder successor คือโหนดที่มาหลังโหนดปัจจุบันใน inorder traversal ของต้นไม้

มาดูตัวอย่างเพื่อเข้าใจปัญหา:

The in-order traversal is 7 8 3 5 9 1

Populating each node -

Next of 5 is 9
Next of 8 is 3
Next of 7 is 8
Next of 3 is 5
Next of 9 is 1

เพื่อแก้ปัญหานี้ เราจะท่องต้นไม้แต่ในรูปแบบ reverse inorder จากนั้นเราจะวางองค์ประกอบที่เยี่ยมชมล่าสุดไปที่ next ของตัวเลข

ตัวอย่าง

โปรแกรมแสดงการนำโซลูชันของเราไปใช้งาน:

#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 of " << ptr->data << " is ";
        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 << "Populating the Tree by adding inorder successor to the next\n";
    populateTree(root);
    printNext(root);
    return 0;
}

ผลลัพธ์

Populating the Tree by adding inorder successor to the next

Next of 76 is 99
Next of 99 is 31
Next of 31 is 15
Next of 15 is 1
Next of 1 is -1