二叉树 -- 二叉排序树

一、概念

二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），也称二叉搜索树。二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：

• 若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值。
• 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值。
• 左、右子树也分别为二叉排序树。

二叉排序树

二、数据结构

struct BinaryTreeNode {
    int id;
    BinaryTreeNode *left, *right;
};

三、相关操作

• 二叉排序树插入
• 二叉排序树查找
• 二叉排序树删除

二叉排序树相关操作

四、实现

#include<stdio.h>
#include<malloc.h>

struct BinaryTreeNode {  
    int id;  
    BinaryTreeNode *left, *right;  
};

BinaryTreeNode* mallocBinaryTreeNode() {
    BinaryTreeNode* node = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
    return node;
}

BinaryTreeNode* searchBST(BinaryTreeNode *node, int id) { //递归搜索，返回搜索结果结点
    if(node == NULL) { //搜索不到目标结点，返回空结点
        return NULL; 
    }

    if(id == node->id) { //搜索到目标结点，返回该结点
        return node; 
    } else if(id < node->id) {
        return searchBST(node->left, id); //递归搜索左子树，返回搜索结果结点
    } else {
        return searchBST(node->right, id); //递归搜索右子树，返回搜索结果结点
    }
}

BinaryTreeNode* insertBST(BinaryTreeNode *node, int id) { //递归插入，返回根节点
    if(node == NULL) { //当前结点为空，新结点即为根结点，返回该结点
        node = mallocBinaryTreeNode();
        node->left = NULL;
        node->right = NULL;
        node->id = id;
        return node;
    }
 
    if(id < node->id) {
        node->left = insertBST(node->left, id); //递归插入左子树，返回根结点
    } else {
        node->right = insertBST(node->right, id); //递归插入右子树，返回根结点
    }
    return node; //返回根结点
}

BinaryTreeNode* deleteBST(BinaryTreeNode *node, int id) { //递归删除，返回根结点
    if(node == NULL) { //当前结点为空，返回空结点
        return NULL;
    }
    
    if (id < node->id) { 
        node->left = deleteBST(node->left, id); //递归删除左子树，返回根结点
    } else if(id > node->id) {
        node->right = deleteBST(node->right, id); //递归删除右子树，返回根结点
    } else {
        if(node->left != NULL && node->right != NULL) { //待删除的结点有两个孩子结点
            BinaryTreeNode *p = node->right; //寻找当前结点的后继结点
            while(p->left != NULL) {
                p = p->left;
            }
            node->id = p->id;
            node->right = deleteBST(node->right, p->id); //递归删除右子树，返回根结点
        } else if(node->left == NULL && node->right == NULL){ //待删除的结点无孩子结点
            node = NULL;
        } else if(node->right == NULL) { //待删除的结点只有左孩子结点
            BinaryTreeNode *p = node;
            node = node->left;
            free(p);
        } else { //待删除的结点只有右孩子结点
            BinaryTreeNode *p = node;
            node = node->right;
            free(p);            
        }
    }
    return node;
}

void createBinaryTree(BinaryTreeNode *root) { //创建二叉排序树
    int n = 7;
    int data[100] = {4, 2, 5, 1, 3, 7, 6};
    root->id = 4;
    root->left = NULL;
    root->right = NULL;
    for(int i = 1; i < n; i++) {
        insertBST(root, data[i]);
    }
}

void preOrder(BinaryTreeNode *node) { //先序遍历二叉树
    if(node == NULL) {
        return;
    }

    printf("%d ", node->id);
    preOrder(node->left);
    preOrder(node->right);
}

void main() {
    BinaryTreeNode root;
    createBinaryTree(&root);
    preOrder(&root);
    printf("\n");

    BinaryTreeNode *p = searchBST(&root, 5);
    if(p != NULL) {
        printf("search %d\n", p->id);
    } else {
        printf("search null\n");
    }

    deleteBST(&root, 7);
    preOrder(&root);
    printf("\n");
}