七 17
排序二叉树能解决好多问题，除了基本的插入、删除、遍历、查找键值以外，还有查找第K小（大）的数的操作。看了一天程序，总算明白了，其实本质和二分查找相似。
从根节点开始查找第r小的数，如果r<=(k的左子树节点的总个数)，那么第r小的节点一定在k的左子树，在k的左子树继续查找第r小的节点。
如果r>(k的左子树节点的总个数+节点k的重复单元个数)，那么第r小的节点一定在k的右子树，在k的右子树继续查找第r-(k的左子树节点的总个数+节点k的重复单元个数)小的节点。
如果以上都不满足，那么k就是第r小的数，返回k的键值。
（其实我很不习惯用静态数据存储二叉树，但考虑到效率和iRachex大牛的建议，还是使用了静态存储）
查找以k为根的树中，第r小的节点的值：
int find(int k,int r)
{
if (r<=p[p[k].l].size)
return find(p[k].l,r);
else if (r> p[p[k].l].size+p[k].cnt)
return find(p[k].r,r-(p[p[k].l].size+p[k].cnt));
return p[k].key;
}
原来如此简单
[回复]
饭团 回复:
四月 5th, 2010 at 23:04:00
膜拜此浏览器。。以及OS。。
[回复]
楼上的浏览器太强大了。
[回复]
Netscape Navigator 9.0.0.6……
[回复]
wecing 回复:
四月 7th, 2010 at 22:23:05
而且是win 98 SE……
[回复]
BYVoid 回复:
四月 8th, 2010 at 09:29:25
明显像是学校的老机房的配置
[回复]