C++10.3 查找第 k 小元素10.4 二叉排序树①

目录

10.3 查找第 k 小元素!

10.4 二叉排序树①

(1) 二叉排序树

(2) 插入一个元素

(3) 删除一个元素*

(4) 查找一个元素

---

10.3 查找第 k 小元素!

和快速排序相近。不同的是，在“递归”这一阶段只需对“有第 k 小数据”的一部分进行排序，另一部分就不用管了。理想情况下，该算法的复杂度能达到线性水平。

int part(int *a, int start, int end)
{
int low=start, high=end;
int temp, check=a[start];
do
{
while (a[high]>=check&&low<high)
high--;
if (a[high]<check)
temp=a[high], a[high]=a[low], a[low]=temp;
while (a[low]<=check&&low<high)
low++;
if (a[low]>check)
temp=a[high], a[high]=a[low], a[low]=temp;
}
while (low!=high);
a[low]=check;
return low;
}
int find(int *a, int start, int end, int k)
{
if (start==end)
return a[start];
int p = part(a, start, end);
int q = p-start+1; // 计算p位置的“排名”
// 只对包含第k小元素的部分进行查找和排序。
if (k <= q)
return find(a, start, p, k);
else
return find(a, p+1, end, k-q);
}

如果 k 不太大，可以用堆（优先队列）解决。

10.4 二叉排序树①

(1) 二叉排序树

二叉排序树的两个重要性质：
 设 R 为任意结点，则 R 的左儿子＜R，R 的右儿子≥R。（如果你需要，可以把不等号的方向调换一下）
 对二叉排序树进行中序遍历，得到的一定是从小到大排好的结果。
在本节，二叉树使用一般的定义方法，即之前的 struct node。

(2) 插入一个元素

插入时从顶端的根结点开始。假设插入的值为 a，对于结点 p，如果 a＜p，就向左走，否则向右走，直到“无路可走”。

node * insert(int v, node * p) // 调用方法：head = insert(x, head);
{
if (p==NULL)
{
NEW(p);
p->value = v;
}
else
if (v < p->value)
p->leftchild=insert(v, p->leftchild);
else
p->rightchild=insert(v, p->rightchild);
return p;
}

(3) 删除一个元素*

删除的难点在于删除某一个结点之后，必须保持二叉排序树的性质。解决这个问题的最简单办法是用另外一个数来替换被删除的数，说得具体一点，就是用右子树中的最小值来替换被删除的值。

// 删除最小值（查找最小值，只需一路向左）。
// 注意：这个最小值a要么是叶子，要么只有右儿子。
// 如果a有右儿子，那么只需把a的右儿子放到a的位置上。
node * removemin(node * p, int &t) // 调用：head = removeitem(head, x);
{
if (p->leftchild == NULL)
{
t = p->value;
return p->rightchild;
}
else
p->leftchild = removemin(p->leftchild, t);
return p;
}
node * removeitem(int value, node * p) // 调用：head = removeitem(x, head);
{
if (p==NULL) return NULL;
if (value < p->value)
p->leftchild = removeitem(value, p->leftchild);
else if (value > p->value)
p->rightchild = removeitem(value, p->rightchild);
else
{
if (p->leftchild == NULL) // 如果只有右儿子，就直接替换
return p->rightchild;
else if (p->rightchild == NULL) // 如果只有左儿子，也直接替换
return p->leftchild;
else
p->rightchild = removemin(p->rightchild, p->value);
}
return p;
}

(4) 查找一个元素

和插入的过程类似。如果要找的值就是结点，停止；如果要找的值比结点小，就往左走，否则往右走。

// 如果找到了，就返回一个包含结点的指针；如果找不到，就返回NULL。
node * find(int value, node * p)
{
if (p==NULL) return NULL;
if (value == p->value)
return p;
else if (value < p->value)
return find(value, p->leftchild);
else
return find(value, p->rightchild);
}