#pragma once
#include <string.h>
//23树
template<class T>
class myTTT{
    struct Node{
        int        count;        //标记当前节点类型   2 3 4
        T        data[3];    //2节点只用[0]  3节点用 [0]和[1] 4节点都用
        Node*    pArray[4];    //2节点只用[0] 和[1] 3节点用 [0]和[1]，[2] 4节点都用
        Node(){
            count = 0;
            memset(data, 0, sizeof(T)* 3);
            memset(pArray, 0, sizeof(Node*)* 4);
        }
    };
    Node*        pRoot;//指向根节点的指针
public:
    myTTT(){ pRoot = NULL; }
    ~myTTT(){}//析构函数先不写

    //插入一个节点到树中
    void insertNode(const T& data);

private:
    //新节点数据data，当前节点node，当前节点父节点pParent
    void _insertNode(Node* node, Node* pParent, const T& data);
};
template<class T>
//插入一个节点到树中
void myTTT<T>::insertNode(const T& data){
    if (pRoot){//pRoot不为NULL
        _insertNode(pRoot, NULL, data);
    }
    else{//pRoot为NULL
        pRoot = new Node;
        pRoot->count = 1;
        pRoot->data[0] = data;
    }
}

template<class T>
//新节点数据data，当前节点node，当前节点父节点pParent
void myTTT<T>::_insertNode(Node* node, Node* pParent, const T& data){
    if (NULL == node) return;//防呆
    if (0 == node->count){//当前节点是新建的    0节点
        pRoot->count++;
        pRoot->data[0] = data;
        return;
    }
    if (1 == node->count){//12节点变成3节点
        if (data > node->data[0]){//往右边添加
            if (node->pArray[0]){//有孩子
                _insertNode(node->pArray[1], node, data);
            }
            else{//没有孩子
                node->data[1] = data;
                node->count++;
            }
        }
        else{//往左边添加
            if (node->pArray[0]){//有孩子
                _insertNode(node->pArray[0], node, data);
            }
            else{//没有孩子
                node->data[1] = node->data[0];//往右边移
                node->data[0] = data;
                node->count++;
            }
        }
    }
    else{//3节点变成4节点
        if (data < node->data[0]){//往最左边添加
            if (node->pArray[0]){//有孩子
                _insertNode(node->pArray[0], node, data);
            }
            else{//没有孩子
                node->data[2] = node->data[1];//往右边移
                node->data[1] = node->data[0];//往右边移
                node->data[0] = data;
                node->count++;
            }
        }
        else if (data < node->data[1]){//往中间添加
            if (node->pArray[1]){//有孩子
                _insertNode(node->pArray[1], node, data);
            }
            else{//没有孩子
                node->data[2] = node->data[1];//往右边移
                node->data[1] = data;
                node->count++;
            }
        }
        else{//往右边添加
            if (node->pArray[2]){//有孩子
                _insertNode(node->pArray[2], node, data);
            }
            else{//没有孩子
                node->data[2] = data;
                node->count++;
            }
        }
    }


    if (3 == node->count){//4节点拆分
        //1 先拆成 3个 2节点
        //1.1 创建两个新节点
        Node* node1 = new Node;
        Node* node2 = new Node;

        //1.2 node1是node左边那个
        node1->data[0] = node->data[0];
        node1->count = 1;
        node1->pArray[0] = node->pArray[0];
        node1->pArray[1] = node->pArray[1];
        //1.3 node2是node右边那个
        node2->data[0] = node->data[2];
        node2->count = 1;
        node2->pArray[0] = node->pArray[2];
        node2->pArray[1] = node->pArray[3];

        //2 3个2节点中的父节点对当前节点的父节点作插入
        
        T temp = node->data[1];//2.1 临时存储中间那个（3个2节点中的父节点）

        //2.2 判断有无父节点
        if (pParent){//2.2.1 有父节点
            //2.2.1.1 找位置
            if (temp < pParent->data[0]){//最左边
                if (pParent->pArray[2]){//最右边有孩子
                    //数据
                    pParent->data[2] = pParent->data[1];
                    pParent->data[1] = pParent->data[0];
                    pParent->data[0] = temp;
                    //指针
                    pParent->pArray[3] = pParent->pArray[2];
                    pParent->pArray[2] = pParent->pArray[1];
                    pParent->pArray[1] = node2;
                    pParent->pArray[0] = node1;
                }
                else if (pParent->pArray[1]){//中间有孩子
                    //数据
                    pParent->data[1] = pParent->data[0];
                    pParent->data[0] = temp;
                    //指针
                    pParent->pArray[2] = pParent->pArray[1];
                    pParent->pArray[1] = node2;
                    pParent->pArray[0] = node1;
                }
            }
            else if (pParent->count == 1 ||
                (pParent->count == 2) &&  (temp < pParent->data[1])){//中间
                if (pParent->pArray[2]){//最右边有孩子
                    //数据
                    pParent->data[2] = pParent->data[1];
                    pParent->data[1] = temp;
                    //指针
                    pParent->pArray[3] = pParent->pArray[2];
                    pParent->pArray[2] = node2;
                    pParent->pArray[1] = node1;
                }
                else if (pParent->pArray[1]){//中间有孩子
                    //数据
                    pParent->data[1] = temp;
                    //指针
                    pParent->pArray[2] = node2;
                    pParent->pArray[1] = node1;
                }
            }
            else if (pParent->count == 2 ||
                (pParent->count > 2) && (temp < pParent->data[2])){//右边
                if (pParent->pArray[2]){
                    //数据
                    pParent->data[2] = temp;
                    //指针
                    pParent->pArray[3] = node2;
                    pParent->pArray[2] = node1;
                }
            }

            pParent->count++;
            delete node;//释放当前节点，因为已经插入到父节点中了
        }
        else{//2.2.2 没有父节点
            //2.2.2.1 当前节点数据改变
            memset(node->data, 0, sizeof(T) * 3);//清空
            node->data[0] = temp;
            node->count = 1;
            //2.2.2.2 两个孩子指针指向两个新节点
            memset(node->pArray, 0, sizeof(Node*) * 4);//清空
            node->pArray[0] = node1;
            node->pArray[1] = node2;
        }
    }


}