二叉排序树
一、二叉排序树(创建、增删改查)学习
#include<stdio.h>
#include<stdlib.h>
typedef struct BSTNode{
int key;
struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;
//在二叉排序树插入关键字为k的新结点（递归实现），时间复杂度：O(h)-O(n)之间
int BST_Insert(BSTree &T,int k){
if(T==NULL){//原树为空，则新插入的结点为根结点
T=(BSTree)malloc(sizeof(BSTNode));
T->key=k;
T->lchild=T->rchild=NULL;
return 1;//返回1，插入成功
}else if(k==T->key){//树中存在相同的关键字的结点，则插入失败
return 0;
}else if(k<T->key){//插入到T的左子树
return BST_Insert(T->lchild,k);
}else{//插入到T的右子树
return BST_Insert(T->rchild,k);
}
}
//按照str[] 数组中的关键字序列建立二叉排序树
void Creat_BST(BSTree &T,int str[],int n){
T=NULL;//初始时T为空树
int i=0;
while(i<n){//依次将每个关键字插入到二叉排序树
BST_Insert(T,str[i]);
i++;
}
}
//非递归查找算法1：查找对应结点
BSTNode *BST_Search1(BSTree T,int key){
while(T!=NULL&&T->key!=key){//若树空或等于根节点值，则结束查找
if(key<T->key){
T=T->lchild;//小于，在左子树查找
}else{
T=T->rchild;//大于，则在右子树上查找
}
}
return T;
}
//非递归查找算法2：查找对应结点的父结点
BSTNode *BST_Search2(BSTree T,int key){
while(T!=NULL){//若树空或等于根节点值，则结束查找
if(T->lchild!=NULL&&T->lchild->key==key){
return T;
}
if(T->rchild!=NULL&&T->rchild->key==key){
return T;
}
if(key<T->key){
T=T->lchild;//小于，在左子树查找
}else{
T=T->rchild;//大于，则在右子树上查找
}
}
return T;
}
//非递归查找算法3：查找右子树最小结点删除，并将其key返回
int BST_Search_Del_min(BSTree &T){
BSTree temp=T;//辅助指针
while(temp->lchild!=NULL){//查找到右子树最左结点为止(最小结点)
temp=temp->lchild;
}
//删除该结点
BST_Delete(T,temp->key);
return temp->key;
}
//递归查找算法
BSTNode *BSTSearch(BSTree T,int key){
if(T==NULL||T->key==key){
return T;
}else if(key<T->key){
T=BSTSearch(T->lchild,key);
}else{
T=BSTSearch(T->rchild,key);
}
return T;
}
//删除结点
bool BST_Delete(BSTree &T,int key){
BSTree cur=BST_Search1(T,key);//查找当前结点
BSTree parent=BST_Search2(T,key);//查找当前结点的父结点
if(cur==NULL){//没找到该节点
return false;
}else if(cur->lchild==NULL&&cur->rchild==NULL){//叶子结点
if(parent==NULL){//该结点为根节点
//不做操作，反正最后这个结点要free
}else if(parent->lchild!=NULL&&parent->lchild->key=key){//该结点为左子结点
parent->lchild=NULL;
}else{//该结点为右子结点
parent->rchild=NULL;
}
free(cur);
}else if(cur->rchild==NULL){//只有右子树
if(parent==NULL){//该结点为根节点
cur=cur->rchild;
}else if(parent->lchild!=NULL&&parent->lchild->key=key){//该结点为左子结点
parent->lchild=cur->rchild;
free(cur);
}else{//该结点为右子结点
parent->rchild=cur->rchild;
free(cur);
}
}else if(cur->lchild==NULL){//只有左子树
if(parent==NULL){//该结点为根节点
cur=cur->lchild;
}else if(parent->lchild!=NULL&&parent->lchild->key=key){//该结点为左子结点
parent->lchild=cur->lchild;
free(cur);
}else{//该结点为右子结点
parent->rchild=cur->lchild;
free(cur);
}
}else{//左右子树都有：查找左子树最大或右子树最小结点，现采用后者，先将删除右子树最小结点，再将原结点填充
int min=BST_Search_Del_min(cur->rchild);
cur->key=min;//替换值
}
return true;
}
int main(){
BSTree t1=(BSTree)malloc(sizeof(BSTNode));
BSTree t2=(BSTree)malloc(sizeof(BSTNode));
BSTree t3=(BSTree)malloc(sizeof(BSTNode));
BSTree t4=(BSTree)malloc(sizeof(BSTNode));
BSTree t5=(BSTree)malloc(sizeof(BSTNode));
t1->key=2;t1->lchild=t2;t1->rchild=t3;
t2->key=1;t2->lchild=NULL;t2->rchild=NULL;
t3->key=4;t3->lchild=t4;t3->rchild=t5;
t4->key=3;t4->lchild=NULL;t4->rchild=NULL;
t5->key=5;t5->lchild=NULL;t5->rchild=NULL;
//非递归查找算法测试
printf("非递归查找算法1结果：%d\n",BST_Search1(t1,3)->key);
printf("递归查找算法结果：%d\n",BSTSearch(t1,3)->key);
printf("非递归查找算法2结果：%d\n",BST_Search2(t1,3)->key);
}
|