二叉查找树的实现 - c++编程基础

InOrderTraverse(T->rchild);
}
}

BiTree BSTMinNode(BiTree T){
BiTree p = T;
while(p->lchild)
p = p->lchild;
return p;
}

BiTree BSTMaxNode(BiTree T){
BiTree p = T;
while(p->rchild)
p = p->rchild;
return p;
}

BiTree BSTSearchSuccessor(BiTree T){
if(T->rchild)
return BSTMinNode(T->rchild);
BiTree p = T->parent;
while(p!=NULL && T == p->rchild){
T = p;
p = p->parent;
}
return p;
}

BiTree BSTSearchPredecessor(BiTree T){
if(T->lchild)
return BSTMaxNode(T->lchild);
BiTree p = T->parent;
while(p!=NULL && T == p->lchild){
T = p;
p = p->parent;
}
return p;
}

#define LEN 10
int generate_array(int *array){
int i=0;
srand((unsigned)time(NULL));
for(i=0;i

array[i]=rand()%100;
printf("%d ",array[i]);
}
printf("\n");
return 0;
}

int main(void){
int num[LEN];
generate_array(num);
BiTree T = NULL;
int i;
for(i=0;i BSTInsert(&T,num[i]);
}
printf("中序遍历二叉查找树：\n");
InOrderTraverse(T);
printf("查找：\n");
for(i=0;i<100;i++){
if(BSTSearch2(T,i))
printf("树中存在：%d\n",i);
}
printf("最大的结点值为：%d\n",BSTMaxNode(T)->data);
printf("最小的结点值为：%d\n",BSTMinNode(T)->data);
printf("%d",num[4]);
BiTree p;
if(p=BSTSearchPredecessor(BSTSearch2(T,num[4]))){
printf("的前驱结点为：%d \n",p->data);
}
else
printf("没有前驱结点\n");
if(p=BSTSearchSuccessor(BSTSearch2(T,num[4]))){
printf("后继结点为：%d \n",p->data);
}
else
printf("没有后继结点\n");
printf("删除小于50的结点：\n");
for(i=0;i<50;i++){
if(BSTDelete(&T,i))
printf("删除结点：%d\n",i);
}
printf("删除后中序遍历：\n");
InOrderTraverse(T);

}

二叉查找树的实现 (二)