二叉搜索树. keywords:return in recursive

BST.c

/*
 * =========================================================
 *       Filename:  BST.c
 *    Description:  二叉搜索树
 *
 * =========================================================
 */
#include <stdio.h>
#include <stdlib.h>
//数据集定义
typedef struct node{
    int elem;
    struct node *left;
    struct node *right;
}Node;


/*---------------------------------------------------
 *  基于二叉搜索树的方法
 *---------------------------------------------------*/
Node *BinarySearch(Node *root , int target);
Node *Insert(Node *root ,int target);
Node *FindMin(Node *root);
Node *FindMax(Node *root);
Node *Delete(Node *root ,int target);
int main(){
}

Node *BinarySearch(Node *root , int target){
    if (root == NULL)
        return NULL;
    else if (root->elem == target)
        return root;
    else if (root->elem >target)
        return BinarySearch(root->left , target);
    else
        return BinarySearch(root->right , target);
}
Node *Insert(Node *root ,int target){
    if (root == NULL){
        root = malloc (sizeof(Node));
        root->elem = target;
        root->left = root->right = NULL;
    }
    else if (target < root->elem)
        root->left = Insert(root->left, target);//这里让root->left 是否多余?
    else if (target > root->elem)
        root->right = Insert(root->right ,target);
    return root;
}
Node *FindMin(Node *root){
    if (root){
        while (root->left)
            root = root->left;
    }
    return root;
}
Node *FindMax(Node *root){
    if (root == NULL)//递归的base case
        return NULL;
    else if (root->right == NULL)
        return root;//递归中何时用return?见evernote笔记
    else
        return FindMax(root->right);
}
Node *Delete(Node *root ,int target){
    if(root == NULL)
        printf("target is not in the tree");
    else if (target < root->elem)
        root->left = Delete(root->left ,target);
    else if (target > root->elem)
        root->right = Delete(root->right ,target);
    else if (root->left && root->right){//如果要删除的节点有两个子节点
        Node *temp = FindMin(root->right);
        root->elem = temp->elem;
        root->right = Delete(root->right , root->elem);
    }
    else{//如果有最多一个节点
        Node *temp = root;
        if (root->left == NULL)
            root = root->right;
        else if (root->right == NULL)
            root = root->left;
        free(temp);
    }
    return root;
}

reference:
When to Return a Recursive Function?
Reason for return statement in recursive function call
SOF