Как исправить 'функцию InorderWalk' для обхода inorder для Red Black Tree?

Question

Я использовал подход вставки красного черного дерева, как описано в CLRS. Это было хорошо для Insertion и Insertion_Fixup, пока я не попытался пройти по дереву, используя InorderWalk, который показал мне только листья моего дерева.

#include <iostream>
using namespace std; 

const unsigned short int RED = 1;
const unsigned short int BLACK = 0;

struct RedBlackTreeNode {

    int data;
    struct RedBlackTreeNode *leftChild;
    struct RedBlackTreeNode *rightChild;
    struct RedBlackTreeNode *parent;
    unsigned short int COLOR; 
} NIL { -999, NULL, NULL, NULL, BLACK};

struct RedBlackTreeNode *pNIL = &NIL;

typedef RedBlackTreeNode RedBlackTreeNode;

RedBlackTreeNode *createNode(int data) {

    RedBlackTreeNode *newNode = new RedBlackTreeNode;
    newNode -> data = data;
    newNode -> leftChild = pNIL;
    newNode -> rightChild = pNIL;
    newNode -> COLOR = RED;

    return newNode;
}


RedBlackTreeNode *LeftRotate(RedBlackTreeNode *root, RedBlackTreeNode *x) {

    RedBlackTreeNode *y = x -> rightChild;
    x -> rightChild = y -> leftChild;

    if(y -> leftChild != pNIL) {
        y -> leftChild -> parent = x;
    }

    y -> parent = x -> parent;

    if(x -> parent == pNIL) {
        root = y;
    }

    else if(x == x -> parent -> leftChild) {
        x -> parent -> leftChild = y;
    }

    else {
        x -> parent -> rightChild = y;
    }

    y -> leftChild = x;
    x -> parent = y;

    return y;
}

RedBlackTreeNode *RightRotate(RedBlackTreeNode *root, RedBlackTreeNode *y) {

    RedBlackTreeNode *x = y -> leftChild;
    y -> leftChild = x -> rightChild;

    if(x -> rightChild != pNIL) {
        x -> rightChild -> parent = y;
    }

    x -> parent = y -> parent;

    if(y -> parent == pNIL) {
        root = x;
    }

    else if(y == y -> parent -> rightChild) {
        y -> parent -> rightChild = x;
    }

    else {
        y -> parent -> leftChild = x;
    }

    x -> rightChild = y;
    y -> parent = x;

    return x;
}


RedBlackTreeNode *InsertionFixup(RedBlackTreeNode *root, RedBlackTreeNode *node) {

    RedBlackTreeNode *uncle = pNIL;

    while(node -> parent -> COLOR == RED) {

        if(node -> parent == node -> parent -> parent -> leftChild) {
            uncle = node -> parent -> parent -> rightChild;

            if(uncle -> COLOR == RED) {
                node -> parent -> COLOR = BLACK;
                uncle -> COLOR = BLACK;
                node -> parent -> parent -> COLOR = RED;
                node = node -> parent -> parent;
            }

            else if(node = node -> parent -> rightChild) {
                node = node -> parent;
                node -> parent= LeftRotate(root, node -> parent);
            }

            else {
                node -> parent -> COLOR = BLACK;
                node -> parent -> parent -> COLOR = RED;
                node -> parent -> parent = RightRotate(root, node -> parent -> parent);
            }
        }

        else {

            uncle = node -> parent -> parent -> leftChild;

            if(uncle -> COLOR == RED) {
                node -> parent -> COLOR = BLACK;
                uncle -> COLOR = BLACK;
                node -> parent -> parent -> COLOR = RED;
                node = node -> parent -> parent;
            }

            else if(node == node -> parent -> leftChild) {
                node = node -> parent;
                node = RightRotate(root, node);
            }

            else {
                node -> parent -> COLOR = BLACK;
                node -> parent -> parent -> COLOR = RED;
                node -> parent -> parent = LeftRotate(root, node -> parent -> parent);
            }
        }

    }

    root -> COLOR = BLACK;

    return root;
}

RedBlackTreeNode *Insertion(RedBlackTreeNode *root) {

    int data;
    cout << "\nEnter the data to fill in the node: ";
    cin >> data;

    RedBlackTreeNode *newNode = createNode(data);

    RedBlackTreeNode *y = pNIL;

    RedBlackTreeNode *x = root;

    while(x != pNIL) {
        y = x;
        if(newNode -> data < x -> data) {
            x = x -> leftChild;
        }

        else {
            x = x -> rightChild;
        }
    }

    newNode -> parent = y;

    if(y == pNIL) {
        root = newNode;
    }

    else if(newNode -> data < y -> data) {
        y -> leftChild = newNode;
    }

    else {
        y -> rightChild = newNode;
    }

    root = InsertionFixup(root, newNode);

    return root;
}

void InorderWalk(RedBlackTreeNode *root) {

    if(root != pNIL) {

        InorderWalk(root -> leftChild);

        cout << root -> data << "(";
        if(root -> COLOR == RED) {
            cout << "RED)";
        }
        else {
            cout << "BLACK)";
        }

        InorderWalk(root -> rightChild);
        }

}

int main(void) {

    int option;

    RedBlackTreeNode *root = pNIL;

    cout << "\nEnter the option\n: ";
    cin >> option;

    while(option != 0) {
        root = Insertion(root);
        cout << "\nEnter the option\n: ";
        cin >> option;
    }

    InorderWalk(root);
}

Выход для входа 12 23 34 45 ожидается равным 12[BLACK] 23[BLACK] 34[BLACK] 45[RED], но получился только 12[BLACK] 45[RED].