第七节 二叉排序树
一、概念
所谓二叉排序树是指具有下列性质的非空二叉树
⑴ 若根结点的左子树不空，则左子树的所有结点值均小于根结点值；
⑵ 若根结点的右子树不空，则右子树的所有结点值均不小于根结点值；
⑶ 根结的左右树也分别为二叉排序树；
显然，对二叉排序树进行中序遍历，可得出结点值递增的排序序列。
|
{假设待排序的数存在数组a中}
procedure createtree;
begin
fillchar(b，sizeof(b)，0);
b[1].data:=a[1]; {二叉排序树初始化}
for i:=2 to n do
begin
b[i] .data:=a[i];
p:=1;
while true do
begin
if a[i]<b[p]．data {若a[i]<b[p]．data，顺左指针方向寻找顶点i的插入位置}
then if b[p]．l<>0
then p:=b[p]．l
else begin b[p]．l:=i;break;end
else {若a[i]≥b[p]．data 时顺右指针方向寻找顶点i的插入位置}
if b[p]．r<>0
then p:=b[p]．r
else begin b[p]．r:=i; break; end;
end;{while}
end;{for}
end;{createtree}
|