本题是一道二叉排序树的基础应用题,主要考察对二叉排序树的建立、插入、查找和删除等操作。
具体实现思路如下:
定义二叉排序树节点结构体,并定义插入节点函数insert()。如果二叉树为空,建立一个新节点;否则,如果插入值比当前节点小,则递归地在左子树中插入;否则,在右子树中插入。
定义查找节点函数search()。如果当前节点为空或者查找到了目标节点,则返回该节点;否则,如果目标节点的值比当前节点小,则在左子树中继续查找;否则,在右子树中继续查找。
定义删除节点函数deleteNode()。首先需要判断是否存在要删除的目标节点:如果不存在,则直接返回;否则,如果要删除的值比当前节点小,则递归地在左子树中查找并删除;否则,在右子树中查找并删除。当要删除的目标节点为叶子节点时,直接将其删除即可;当要删除的目标节点既有左孩子,又有右孩子时,需要先在右子树中寻找最小值替换该目标值(因为任意一个右孩子都大于左边所有元素),然后再递归地在右子树中删除最小节点。
在主函数中,不断向二叉树中插入新节点,然后查找目标节点和删除目标节点,最后输出结果即可。
完整代码如下: