1
2
3
4
5
6
7
8
struct node {
int *left_p;//前一个父节点
int *right_p;//后一个父节点
int *left_c;//前一个节点
int *right_c;//后一个节点
int idx; // 通过这个字段排序
int *val;
}
尾部的节点一定有父节点，除非是最上层链。如果需要向最后添加节点可以让尾节点的父节点指向新添加的节点，然后检查原来的尾节点。 检查方法： left_p 为 -1时代表当前节点有父节点，否则记录前一个父节点 right_p 记录后一个父节点，或者自己的父节点
每插入一个节点有五种情况
1
2
3
4
5
6
o --> o
o -1> o -2> o
o --> o
o -3> o -4> o -5> o
只有 3、4、5 这是三种情况需要新建节点，并且需要判断在谁头上新建节点。
