C 二叉搜索树 Binary Search Tree

C 二叉搜索树 Binary Search Tree

代码如下:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct tree_node{  // 以结构的形式来声明一个BST结点
    int data;                  // 结点的数据域,用于存储数据
    struct tree_node * left;   // 结点的指针域,指向左孩子的结点
    struct tree_node * right;  // 结点的指针域,指向右孩子的结点
};
typedef struct tree_node BST_node; // 这里结点结构被声明为single_node了

// 下面是创建一个链表结点的函数
BST_node * create_BST_node(int data){
    BST_node * node = NULL;  // 首先定义一个指向结点类型的指针
    node = (BST_node *)malloc(sizeof(BST_node));  // 为node动态分配内存
    memset(node, 0, sizeof(BST_node)); // 为新分配的内存进行初始化  (归零)

    node -> data = data;  // 数据域赋值
    node -> left = NULL;  // 指针域赋值,指向空
    node -> right = NULL;  // 指针域赋值,指向空
    return node;  // 返回一个指向node类型的指针
}

// 下面是主函数
int main(void){
    int data = 1;
    BST_node * node_ptr  = create_BST_node(8);  // 创建一个结点,得到一个结点指针
    BST_node * node_ptr1 = create_BST_node(5);  // 创建一个结点,得到一个结点指针
    BST_node * node_ptr2 = create_BST_node(2);  // 创建一个结点,得到一个结点指针
    BST_node * node_ptr3 = create_BST_node(6);  // 创建一个结点,得到一个结点指针
    BST_node * node_ptr4 = create_BST_node(7);  // 创建一个结点,得到一个结点指针
    BST_node * node_ptr5 = create_BST_node(1);  // 创建一个结点,得到一个结点指针
    BST_node * node_ptr6 = create_BST_node(4);  // 创建一个结点,得到一个结点指针
    BST_node * node_ptr7 = create_BST_node(3);  // 创建一个结点,得到一个结点指针

    insertion(node_ptr,node_ptr1);
    insertion(node_ptr,node_ptr2);
    insertion(node_ptr,node_ptr3);
    insertion(node_ptr,node_ptr4);
    insertion(node_ptr,node_ptr5);
    insertion(node_ptr,node_ptr6);
    insertion(node_ptr,node_ptr7);
    preorder_traversal_node(node_ptr);
    printf("\n");
    inorder_traversal_node(node_ptr);
    printf("\n");
    postorder_traversal_node(node_ptr);
    printf("\n");
    printf("%d",node_ptr->data);
    free(node_ptr); // 释放内存
    return 0;
}

// 下面是在将结点插入树的函数
void insertion(BST_node * header, BST_node * new){
    if(new->data>header->data) //如果该键值大于根值,往右添加
    {
        if(header->right!=NULL)
            insertion(header->right,new);
        else
            header->right=new;
    }
    else if(new->data<header->data) //如果该键值小于根值,往左添加
    {
        if(header->left!=NULL)
            insertion(header->left,new);
        else
        {
            header->left=new;
        }
    }
    else //如果该键值已出现过,删除
    {
        free(new);
        new = NULL;
    }
}

//下面是先序遍历的函数(根、左、右)
void preorder_traversal_node(BST_node * header){
    printf("%d",header->data);//输出根键值
    if(header->left!=NULL)
        preorder_traversal_node(header->left);//先序遍历左子树
    if(header->right!=NULL)
        preorder_traversal_node(header->right);//先序遍历右子树
}

//下面是中序遍历的函数(左、根、右)
void inorder_traversal_node(BST_node * header){
    if(header->left!=NULL)
        inorder_traversal_node(header->left);//中序遍历左子树
    printf("%d",header->data);//输出根键值
    if(header->right!=NULL)
        inorder_traversal_node(header->right);//中序遍历右子树
}

//下面是后序遍历的函数(左、右、根)
void postorder_traversal_node(BST_node * header){
    if(header->left!=NULL)
        postorder_traversal_node(header->left);//后序遍历左子树
    if(header->right!=NULL)
        postorder_traversal_node(header->right);//后序遍历右子树
    printf("%d",header->data);//输出根键值
}

//下面是查找值为data的结点的函数。num输入0,值位检索次数
void search_node(BST_node * header, int data,int num){
    num++;
    if(header!=NULL)
    {
        if(data==header->data)
        {
            printf("%d",num);
        }
        else if(data>header->data)
            search_node(header->right,data,num);
        else if(data<header->data)
            search_node(header->left,data,num);
    }
    else
        printf("none");
}

//下面是删除值为data的结点的函数
void delete_node(BST_node * header, int data){
    int lr_flag=0;  // -1:left 1:right
    BST_node * prev  = NULL;
    BST_node * current = NULL;
    current=header;
    while(data!=current->data)
    {
        prev=current;
        if(data<current->data)
        {
            current=current->left;
            lr_flag=-1;
        }
        else
        {
            current=current->right;
            lr_flag=1;
        }
    }
    if(current==NULL)
        return ;
    if(current->left==NULL&&current->right==NULL)
    {
        if(lr_flag==1)
        {
            prev->right=NULL;
        }
        if(lr_flag==-1)
        {
            prev->left=NULL;
        }
        free(current);
    }
    else if(current->left!=NULL&&current->right!=NULL)
    {
        BST_node * root  = current;
        current=current->left;
        while(current->right!=NULL)
        {
            prev=current;
            current=current->right;
        }
        prev->right=current->left;
        root->data=current->data;
        free(current);
    }
    else if(current->left!=NULL)
    {
        if(lr_flag==1)
        {
            prev->right=current->left;
        }
        if(lr_flag==-1)
        {
            prev->left=current->left;
        }
        free(current);
    }
    else if(current->right!=NULL)
    {
        if(lr_flag==1)
        {
            prev->right=current->right;
        }
        if(lr_flag==-1)
        {
            prev->left=current->right;
        }
        free(current);
    }
}

void destroy_BST_node(BST_node * header)
{
    if (header==NULL)
        return ;

    if (header->left != NULL)
        destroy_BST_node(header->left);
    if (header->right != NULL)
        destroy_BST_node(header->right);

    free(header);
}

版权声明:本文为 溪月阁 | MoBrook 博主「 皓月 」的原创文章遵循用 CC BY-NC-SA 4.0 版权协议进行许可,转载请附上原文出处链接及本声明。

本文链接https://mobrook.cn/index.php/kanni-106/

没有了,已经是最后文章

没有了,已经是最新文章