#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; } } }
标签:node,count,23,pArray,pParent,data,节点 From: https://www.cnblogs.com/yewu1/p/17397162.html