下面代码输出结果为-|||-TreeMap<lnteger, String?map=new Tre

TreeMap 会自动对其存储的元素进行排序。TreeMap 内部采用红黑树的数据结构来存储元素，红黑树是一种自平衡的二叉搜索树，保证了元素在 TreeMap 中按照键的自然顺序或者指定的比较器进行排序。在 TreeMap 中，添加新元素时会自动按照键的顺序将其插入到红黑树中，这样保证了 TreeMap 中的元素始终是有序的。因此，TreeMap 是一种可以自动排序的 Map 数据结构。

就会个第一题(因为第一题上已经给出了大致思路)

思路:用map容器(它的内部数据结构是一颗红黑树，查找和插入数据速度非常快)

map<int,st>a//key(int)：设置为1~n的数value(st):设置为key的前驱和后继；

这样一来就可以像链表快速插入数据，又可以像数组随机访问元素(key,就相当于数组的下标)

下面是代码和运行截图；

看代码前建议先了解一下map容器的具体用法

#include<iostream>

#include<map>

#include<vector>

using namespace std

struct st{//两个成员变量用来储存前驱和后继

int left//0

int right//1

st()

{

left=0

right=0

}

}

void input(map<int,st>&a)//输出

{

st t

int s=0

map<int,st>::iterator it//迭代器(指针)

for(it=a.begin()it!=a.end()it++)//循环迭代

{

t=it->second

if(t.left==0)//左边等于0,说明该数是第一个数

{

s=it->first//记录key

break

}

}

t=a[s]

cout<<s<<" "

while(t.right!=0)//循环找当前数的右边的数(右边的为0，就说明该数是最后一个数)

{

cout<<t.right<<" "

t=a[t.right]

}

}

int  main()

{

st t,t_i,t_x,t_k,s

map<int,st>a

map<int,st>::iterator it

int n,x,p,x_l,x_r

cin>>n

for(int i=1i<=ni++)//map容器赋初值(i,t)

//i:(key)下标t:(value)结构体变量

{

a.insert(make_pair(i,t))

}

for(int i=2i<=ni++)

{

cin>>x>>p

if(p==0)//x的左边插入i

{

t=a[x]

if(t.left==0)//x的左边没有数

{

t_x.left=i

t_i.right=x

a[x]=t_x

a[i]=t_i

}

else//x的左边有数

{

int x_left

t_x=a[x]

x_left=t_x.left

t_k=a[x_left]

t_i.right=x

t_i.left=t_x.left

t_k.right=i

t_x.left=i

a[x]=t_x

a[i]=t_i

a[x_left]=t_k

}

}

else//x的右边插入i

{

t=a[x]

if(t.right==0)//x的右边没有数

{

t_x.right=i

t_i.left=x

a[x]=t_x

a[i]=t_i

}

else//x的左边有数

{

int x_right

t_x=a[x]

x_right=t_x.right

t_k=a[x_right]

t_i.left=x

t_i.right=t_x.right

t_k.left=i

t_x.right=i

a[x]=t_x

a[i]=t_i

a[x_right]=t_k

}

}

}

for(it=a.begin()it!=a.end()it++)//循环迭代打印各个数之间的关系

{

cout<<it->first<<" "

cout<<"左边:"

cout<<it->second.left<<" "

cout<<"右边:"

cout<<it->second.right<<endl

}

input(a)//打印序列

return 0

}

/*

4

1 0

2 1

1 0

2 3 4 1

*/

1、首先，需要定义红黑树的节点这样的结构。

2、定义结构的顺序。

3、然后，就能在这里定义的根节点的结构体。

4、此时，可以暂时这棵红黑树的根命名为rb_root。

5、这时，利用刚刚定义的红黑树节点定义新节点。

6、最后，我们便可以为其重新命名为RBRoot即可。

---