1#include <iostream>
  2using namespace std;
  3
  4class Node {
  5public:
  6    int val[2];     // 存放节点中的值，最多两个
  7    Node* child[3]; // 存放子节点，最多三个
  8    bool isTwoNode; // 标记是否为2节点
  9
 10    Node(int value) {
 11        val[0] = value;
 12        val[1] = -1; // -1表示没有第二个值
 13        for (int i = 0; i < 3; i++) {
 14            child[i] = nullptr;
 15        }
 16        isTwoNode = true; // 初始为2节点
 17    }
 18
 19    bool isLeaf() {
 20        return (child[0] == nullptr && child[1] == nullptr && child[2] == nullptr);
 21    }
 22};
 23
 24class TwoThreeTree {
 25private:
 26    Node* root;
 27
 28    // 插入节点
 29    Node* insert(Node* node, int value) {
 30        if (node == nullptr) {
 31            return new Node(value);
 32        }
 33
 34        if (node->isLeaf()) {
 35            return splitAndInsert(node, value);
 36        }
 37
 38        if (value < node->val[0]) {
 39            node->child[0] = insert(node->child[0], value);
 40        } else if (node->isTwoNode || value < node->val[1]) {
 41            node->child[1] = insert(node->child[1], value);
 42        } else {
 43            node->child[2] = insert(node->child[2], value);
 44        }
 45
 46        return node;
 47    }
 48
 49    // 节点分裂与插入
 50    Node* splitAndInsert(Node* node, int value) {
 51        if (node->isTwoNode) {
 52            if (value < node->val[0]) {
 53                node->val[1] = node->val[0];
 54                node->val[0] = value;
 55            } else {
 56                node->val[1] = value;
 57            }
 58            node->isTwoNode = false;
 59            return node;
 60        } else {
 61            int middleValue;
 62            Node* newLeft;
 63            Node* newRight;
 64
 65            if (value < node->val[0]) {
 66                middleValue = node->val[0];
 67                newLeft = new Node(value);
 68                newRight = new Node(node->val[1]);
 69            } else if (value < node->val[1]) {
 70                middleValue = value;
 71                newLeft = new Node(node->val[0]);
 72                newRight = new Node(node->val[1]);
 73            } else {
 74                middleValue = node->val[1];
 75                newLeft = new Node(node->val[0]);
 76                newRight = new Node(value);
 77            }
 78
 79            if (node == root) {
 80                root = new Node(middleValue);
 81                root->child[0] = newLeft;
 82                root->child[1] = newRight;
 83                return root;
 84            } else {
 85                Node* parent = new Node(middleValue);
 86                parent->child[0] = newLeft;
 87                parent->child[1] = newRight;
 88                return parent;
 89            }
 90        }
 91    }
 92
 93public:
 94    TwoThreeTree() {
 95        root = nullptr;
 96    }
 97
 98    void insert(int value) {
 99        root = insert(root, value);
100    }
101
102    void print(Node* node, int level = 0) {
103        if (node == nullptr) return;
104        print(node->child[2], level + 1);
105        if (!node->isTwoNode) {
106            for (int i = 0; i < level; i++) cout << "    ";
107            cout << node->val[1] << endl;
108        }
109        print(node->child[1], level + 1);
110        for (int i = 0; i < level; i++) cout << "    ";
111        cout << node->val[0] << endl;
112        print(node->child[0], level + 1);
113    }
114
115    void display() {
116        print(root);
117    }
118};
119
120int main() {
121    TwoThreeTree tree;
122    int values[] = {10, 20, 5, 6, 12, 30, 7, 17};
123    
124    for (int value : values) {
125        tree.insert(value);
126    }
127
128    tree.display();
129    
130    return 0;
131}