二叉搜索树的创建、插入、遍历、删除

二叉搜索树

本文主要记录自己完成学校课程布置的有关“二叉搜索树”的代码闯关题的代码和思路心得，部分内容有借鉴身边大佬，借鉴部分会有标注。

• 二叉搜索树的结构体定义

struct node
{
    int data ;
    struct node *lchild ,*rchild ;
};

typedef struct node *pTree;

• 创建 插入结点 以及三种遍历方式

/*1.创建一个二叉树结点,值为element*/ 
pTree createTreeNode(int element)
{ pTree T=(pTree)malloc(sizeof(struct node));
 T->data=element;
 T->lchild=NULL;
 T->rchild=NULL;
 return T;


}


/*2.在二叉排序树中插入一个数据元素,若二叉树为空，则新建根节点*/
pTree insertData(int x , pTree T)
{
if(T==NULL){
	T=createTreeNode(x); 
}
else if(x<T->data){
	if(T->lchild==NULL)
	T->lchild=insertData(x,T->lchild);
	else insertData(x,T->lchild);
}
else if(x>T->data){
	if(T->rchild==NULL){
		T->rchild=insertData(x,T->rchild);
	
	}
	else insertData(x,T->rchild);
}
return T;
}

/*3.先序遍历和中序遍历函数*/
void preOrder( pTree T)
{
if(T!=NULL){
	printf("%d ",T->data);
preOrder(T->lchild);
preOrder(T->rchild);
} 

else return ;
}
void inOrder( pTree T)
{

if(T!=NULL)
{
	inOrder(T->lchild);
printf("%d ",T->data);
inOrder(T->rchild);
}
else return ;
}

测评平台给的第一关主函数：（眼看手不能动的那种）

int main()
{
int a ,num;

pTree T =NULL;
 scanf("%d",&num);
for(int i=0;i<num;i++)
 {
     scanf("%d",&a);
     T = insertData(a, T);
 }
 inOrder(T);
 printf("\n");
 preOrder(T);

}

• 最小值、最大值以及特定值的查找

/*第二关*/
/*1.在二叉排序树T中查找最小值，返回该结点*/
pTree findMin(pTree T)
{
	if(T==NULL) return NULL;
//只要没到尽头，就一直访问左子树
if(T->lchild==NULL){
	return T;
}
else return findMin(T->lchild);

}

/*2.在二叉排序树T中查找最大值，返回该结点*/
pTree findMax(pTree T)
{
	if(T==NULL) return NULL;
if(T->rchild==NULL){
	return T;
}
else findMax(T->rchild);



}


/*3.在二叉排序树T中查找指定数据元素，若找到，返回对应结点，未找到，则插入该元素，并返回结点*/
//二叉查找树特点：左<根<右 
//思路：如果树是空的，直接返回；否则，如果找到了，返回，否则递归搜索左子树
//否则递归搜索右子树
//在否则就插入元素 
// 
pTree findData(pTree T, int element)
{
if(T==NULL){
	return NULL;
} 
else{
	if(T->data==element) return T;
 if(findData(T->lchild,element)) return findData(T->lchild,element);
else if(findData(T->rchild,element)) return findData(T->rchild,element);
else return insertData(element,T->lchild);


}
}

**这里我需要特别注明一下：**以上代码符合注释里的要求：“未找到，则插入该元素，并返回结点”，但是并不能使我通过主函数的评测，因为给定的主函数是这样的：

int main()
{
int a ;

pTree T =NULL;
int num;
scanf("%d",&num);
for(int i=0;i<num;i++)
 {
     scanf("%d",&a);
     T = insertData(a, T);
 }
 pTree p = findMin(T);
 if(p)
printf("%d\n",p->data);
else
printf("未找到\n");
p = findMax(T);
if(p)
printf("%d\n",p->data);
else
printf("未找到\n");

scanf("%d",&a);
p = findData(T,a);
if(p)
printf("%d\n",p->data);
else
printf("未找到指定元素\n");


}

其中，如果按照注释的要求写，永远不会出现倒数一二行中的else的情况。

于是，为了顺利完成作业，只能把代码改成：

pTree findData(pTree T, int element)
{
if(T==NULL){
	return NULL;
} 
else{
	if(T->data==element) return T;
 if(findData(T->lchild,element)) return findData(T->lchild,element);
else if(findData(T->rchild,element)) return findData(T->rchild,element);
else return NULL;


}
}

• 结点的删除

阅读《数据结构与算法分析——c语言描述 （原书第二版）》后，可写出如下代码：

/*第三关*/
//教科书式写法 
/*在二叉排序树T中删除指定元素的结点,若删除成功则返回该结点，否则返回NULL*/
pTree deleteData(pTree T,int element)
{
//针对只有一个节点或有一个子节点的情况:父节点绕过其并删除，针对有两个子节点的情况:标记并且递归删除 
pTree tmp;
if(T==NULL){
	printf("tree is not found!error!");
	return NULL;
}
else if(element<T->data){
	T->lchild=deleteData(T->lchild,element);
}
else if(element>T->data){
	T->rchild=deleteData(T->lchild,element);
}
else if(T->lchild&&T->rchild){
	tmp=findMin(T->rchild);
	T->data=tmp->data;
	T->rchild=deleteData(T->rchild,element);
}
else{//one or zero children 
	tmp=T;
	if(T->lchild==NULL){
		T=T->rchild;
	}
	else if(T->rchild==NULL){
		T=T->lchild;
	}
	free(tmp);
}
return T;
}

但是该方法无法通过平台中 直接删除头结点 的测试样例，因为用于作替换的数据将会重复输出。

于是，有位大佬给出了这样一种精妙的解法：

个人觉得最精妙之处在于：（帮助我通过了测试） 不需要用到递归，大大降低了时间复杂度。

（众所周知，递归是一种好方法，毕竟很多题目找不到非递归的写法，这表明了递归的不可替代性；

但递归又不是好方法，尤其是数据量大的时候，它的劣势就体现出来了。

再者，在代码中如果没有透彻理解递归，而对其使用不当的话，有可能造成灾难性后果）

不过稍有不足的是，细心的朋友可能也看出来了，对于稍微复杂一些的树这种写法也不适用。

pTree deleteData(pTree T,int element){
pTree p=T;
int f=0;
while(p!=NULL){
if(p->data==element){
		f=1;
		break;
	}

else if(element<p->data){
			p=p->lchild;
		}
else p=p->rchild;	
}
if(f==0) return NULL;
else{
	p->data=p->rchild->data;
	p->rchild=p->rchild->rchild;
}
return p;
}

最后附上本关主函数：

 int main()
{
int a ;

pTree T =NULL;
int num ;
scanf("%d",&num);
for(int i=0;i<num;i++)
 {
     scanf("%d",&a);
     T = insertData(a, T);
 }

scanf("%d",&a);

pTree p = deleteData(T,a) ;

printf("删除后中序遍历结果:");
inOrder(T);
printf("\n删除后先序遍历结果:");
preOrder(T);


}

---

写在最后的碎碎念：

最近进入了结课考试周，一堆没完成的ddl，还要准备期末复习，不过还是专门腾出了一点时间来记录一下这个系列题目。主要是觉得在它上面耗费的时间精力多，不写点什么似乎对不起自己已经付出的时间；同时收获也挺大，有了很多体悟和思考。

第三关最后闯关成功的代码是一位大佬写的，简直是为这个测试集量身定做。当时卡住我的就是直接删除根节点的例子，而最新的方法首先解决的就是这个问题。思想就是既然题目没说清楚是怎么删除的，就观察输出样例，写成符合的样子。但是其并不适用于根节点的右节点的左节点非空的情况。一般而言，还是用我最初的那种通用的思路和方法比较合适（虽然它没有能很好地解决在根节点删除这个问题），但是对于更一般的情况反而更适用。

只能说，学习算法的伊始，掌握其思想精髓是关键，莫要让一些细枝末节的东西打扰到自己，从而对自己产生怀疑。

其实一道题，要做到满足测试集不难，但是能写出普适的代码就不简单了。

再其实，有时候和评测平台也有关系。个人认为，非完成任务需要，不要在某平台上验证代码，应该找一些权威靠谱些的平台，比如leetcode等等。现在某平台就是这样，老师们出的题目里有些注释要求和测评要求完全不像是由同一个人想出来的，做个题还得揣摩揣摩、靠猜靠撞，心很累，有这时间可以多学几条新解题思路了。（手动汗颜）

最后，这只是个人的学习笔记，牢骚话多于正文。如果你能刷到这篇文章还能坚持翻到这里的话，真的很感谢你的耐心与支持！