二叉搜尋樹中序後代

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node *left, *right;
    Node(int x) {
        this->data = x;
        this->left = this->right = NULL;
    }
};

Node* insert(Node* root, int key)
{
    if (root == NULL) {
        return new Node(key);
    }
    if (key < root->data) {
        root->left = insert(root->left, key);
    }
    else {
        root->right = insert(root->right, key);
    }
    return root;
}

Node* getNextleft(Node* root)
{
    while (root->left) {
        root = root->left;
    }

    return root;
}

void inorderSuccessor(Node* root, Node*& succ, int key)
{

    if (root == NULL) {
        succ = NULL;
        return;
    }

    if (root->data == key)
    {
        if (root->right) {
            succ = getNextleft(root->right);
        }
    }

    else if (key < root->data)
    {
        succ = root;
        inorderSuccessor(root->left, succ, key);
    }
    else {
        inorderSuccessor(root->right, succ, key);
    }
}

int main()
{
    int keys[] = { 1, 5, 8, 2, 6, 3, 7, 4 };
    Node* root = NULL;
    for (int key : keys) {
        root = insert(root, key);
    }
    for (int key : keys)
    {
        Node* prec = NULL;
        inorderSuccessor(root, prec, key);
        if (prec) {
            cout << "Inorder successor of node " << key << " is " << prec->data;
        }
        else {
            cout << "No inorder Successor of node " << key;
        }

        cout << '\n';
    }

    return 0;
}