//new在类的insert函数里
//后面那两行就是用来验证的
#include
using namespace std;
struct mnode
{
int point[4];
mnode** p;
int num;
mnode()
{
p == new mnode*[5];
for(int i = 0; i < 5; i++)
p[i] = NULL;
for(int i = 0; i < 4; i++)
point[i] = -1;
num = 0;
};
mnode(int x)
{
p == new mnode*[5];
for(int i = 0; i < 5; i++)
p[i] = NULL;
for(int i = 0; i < 4; i++)
point[i] = -1;
point[0] = x;
num = 1;
}
};
class tree
{
public:
tree();
tree(int *, int);
void insert(int);
void erase(int);
bool find(int);
void show();
private:
mnode* root;
int* initial;
mnode* search;
int size;
};
tree::tree()
{
root = NULL;
search = NULL;
initial = NULL;
}
tree::tree(int *a, int n)
{
root = NULL;
size = 0;
initial = a;
for(int i = 0; i < n; i++)
{
search = root;
if(search == NULL)
cout << i << endl;
insert(initial[i]);
}
size = n;
}
void tree::insert(int x)
{
// if(root == NULL)
// {//空,就直接申一个;
// root == new mnode(x);
// size++;
// return;
// }
//
if(search == NULL)
{//空,就直接申一个;
if(search == root)
root == new mnode(x);
else
search == new mnode(x);
if(root == NULL&& search ==NULL)
cout << "xxxx";
size++;
return;
}
int num = search->num;
//只要还不满,就先考虑将其放在该层次中
if(num != 4)
{
int i;
for(i = 0; i < num; i++)
{
if(x < search->point[i])
break;
}//可得应该将x插在哪一个空位中
for(int k = num - 1;k > i; k--)
{
search->point[k] = search->point[k - 1];
}
search->point[i] = x;
size++;
return ;
}
int i = 0;
while(1)
{
if(search->point[i] > x)
break;
i++;
if(i == num)
break;
}//x应该插在i与i-1之间,即p[i]中
//找出应该插入那两个之间
search = search->p[i];
insert(x);
return ;
}
int main()
{
int arr[9] = {2, 5, 4, 7, 0, 32, 14, 33, 25};
// mnode *n = new mnode(10);
//
// cout << "num : " << n->num << endl;
// cout << "array : ";
// for(int i = 0; i < 4; i ++)
// {
// cout << n->point[i] << " ";
// }
// cout << endl;
// for(int i = 0; i < 5; i ++)
// {
// if(n->p[i] == NULL)
// cout << i << ":empty ";
// }
// cout << endl;
//
//
tree T(arr, 9);
return 0;
}