用C语言的递归写个二叉搜索树(二叉排序树)

桃浪十七丶
• 阅读 1350

不会递归的程序员不是好程序员,虽然鄙人尚未毕业,是个无知的大学生。但这追去真理的上进心不可小量。 二叉树的每一个节点,与其左右子树都可以组成一个二叉树,利用这思路,可以写个递归形式的二叉树。

#include<stdio.h>
#include<stdlib.h>

typedef struct treeNode
{
    int data;
    struct treeNode* LeftChild;
    struct treeNode* RightChild;
}*LPBST,*LPNode,Node;

//createNode这个函数可以自己画个图练习一下
//每一个指针都由指针域和数据域构成
LPNode createNode(int data)
{
    LPNode newNode = (LPNode)malloc(sizeof(Node));
    if (newNode != NULL)
    {
        newNode->data = data;
        newNode->LeftChild = NULL;
        newNode->RightChild = NULL;
    }
    return newNode;
}

LPBST InsertNode(LPBST tree, int data)
{
    if (tree == NULL)
    {
    //如果树为空,则创建二叉树
        tree = createNode(data);
    }
    else
    {
        if (tree->data > data)
        {
        //对比插入的数据和该节点的数据,
        //若小于节点数据则进入左子树,大于则进入右子树,并调用自身函数
        //如此递归下去
            tree->LeftChild = InsertNode(tree->LeftChild, data);
        }
        else if (tree->data < data)
        {
            tree->RightChild = InsertNode(tree->RightChild, data);
        }
    }
    return tree;
}

LPNode SearchNode(LPBST tree, int data)
{
    if (tree == NULL)
    {
        return NULL;
    }
    else
    {
        //对比搜索的数据和该节点的数据,
        //若小于节点数据则进入左子树,大于则进入右子树,并调用自身函数
        //如此递归下去
        if (tree->data > data)
        {
            return SearchNode(tree->LeftChild, data);
        }
        else if(tree->data < data)
        {
            return SearchNode(tree->RightChild, data);
        }
        else
        {
            return tree;
        }
    }
}

LPNode FindMin(LPBST tree)
{
    if (tree == NULL)
    {
        return NULL;
    }
    else
    {
    //左子树为空 ,则该数据是最小数据。
        if (tree->LeftChild == NULL)
        {
            return tree;
        }
        else
        {
        //左子树不为空,则继续进入左子树查找
            return FindMin(tree->LeftChild);
        }
    }
}

LPNode FindMax(LPBST tree)
{
    if (tree == NULL)
    {
        return NULL;
    }
    else
    {
    //与FindMin函数的道理相反
        if (tree->RightChild == NULL)
        {
            return tree;
        }
        else
        {
            return FindMax(tree->RightChild);
        }
    }
}

void MidOrderTralersal(LPBST tree)
{
    if (tree != NULL)
    {
        MidOrderTralersal(tree->LeftChild);
        printf("%d\t", tree->data);
        MidOrderTralersal(tree->RightChild);
    }
}

LPBST DeleteNode(LPBST tree, int data)
{
    LPNode tempNode;
    if (tree == NULL)
    {
        return NULL;
    }
    //前面的递归部分都是道理相同的,比较目标数据与节点然后进行操作
    else if (tree->data > data)
    {
        tree->LeftChild = DeleteNode(tree->LeftChild, data);
    }
    else if (tree->data < data)
    {
        tree->RightChild = DeleteNode(tree->RightChild, data);
    }
    else
    {
        if (tree->LeftChild && tree->RightChild)
        {
            //在右子树中找到最小节点填充到被删除节点
            tempNode = FindMin(tree->RightChild);
            tempNode->data = tree->data;
            //在删除的节点的右子树中删除最小元素
            tree->RightChild = DeleteNode(tree->RightChild, tree->data);    
        }
        else
        {
            tempNode = tree;
            //有右子树或者无子节点
            if (tree->LeftChild == NULL)
            {
                tree = tree->RightChild;
            }
            //有左子树或者无子节点
            else if (tree->RightChild == NULL)
            {
                tree = tree->LeftChild;
            }
            free(tempNode);
        }
    }
    return tree;
}

int main()
{
//记着初始化变量,不管是指针变量还是普通变量
    LPBST tree=NULL;
    int array[8] = { 4,76,24,99,57,30,13,169 };
    for (int i = 0; i < 8; i++)
    {
        tree = InsertNode(tree, array[i]);
    }
    MidOrderTralersal(tree);
    printf("\n");
    LPNode MinNode = FindMin(tree);
    LPNode MaxNode = FindMax(tree);
    LPNode positionNode = SearchNode(tree, 169);
    printf("%d\t%d\t%d\n", MinNode->data, MaxNode->data, positionNode->data);

    tree = DeleteNode(tree, 13);
    MidOrderTralersal(tree);
    system("pause");
    return 0;
}

这篇博客不求点赞,只是随笔(强烈暗示)

点赞
收藏
评论区
推荐文章
blmius blmius
1年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Stella981 Stella981
1年前
Opencv中Mat矩阵相乘——点乘、dot、mul运算详解
Opencv中Mat矩阵相乘——点乘、dot、mul运算详解2016年09月02日00:00:36 \牧野(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fme.csdn.net%2Fdcrmg) 阅读数:59593
Easter79 Easter79
1年前
swap空间的增减方法
(1)增大swap空间去激活swap交换区:swapoff v /dev/vg00/lvswap扩展交换lv:lvextend L 10G /dev/vg00/lvswap重新生成swap交换区:mkswap /dev/vg00/lvswap激活新生成的交换区:swapon v /dev/vg00/lvswap
Stella981 Stella981
1年前
Linux查看GPU信息和使用情况
1、Linux查看显卡信息:lspci|grepivga2、使用nvidiaGPU可以:lspci|grepinvidia!(https://oscimg.oschina.net/oscnet/36e7c7382fa9fe49068e7e5f8825bc67a17.png)前边的序号"00:0f.0"是显卡的代
Wesley13 Wesley13
1年前
JAVA递归实现线索化二叉树
JAVA递归实现线索化二叉树基础理论首先,二叉树递归遍历分为先序遍历、中序遍历和后序遍历。先序遍历为:根节点左子树右子树中序遍历为:左子树根节点右子树后序遍历为:左子树右子树根节点(只要记住根节点在哪里就是什么遍历,且都是先左再右)线索化现在有这么一棵二叉树,它的数据结
Stella981 Stella981
1年前
KVM调整cpu和内存
一.修改kvm虚拟机的配置1、virsheditcentos7找到“memory”和“vcpu”标签,将<namecentos7</name<uuid2220a6d1a36a4fbb8523e078b3dfe795</uuid
Easter79 Easter79
1年前
Twitter的分布式自增ID算法snowflake (Java版)
概述分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的。有些时候我们希望能使用一种简单一些的ID,并且希望ID能够按照时间有序生成。而twitter的snowflake解决了这种需求,最初Twitter把存储系统从MySQL迁移
Wesley13 Wesley13
1年前
Java日期时间API系列36
  十二时辰,古代劳动人民把一昼夜划分成十二个时段,每一个时段叫一个时辰。二十四小时和十二时辰对照表:时辰时间24时制子时深夜11:00凌晨01:0023:0001:00丑时上午01:00上午03:0001:0003:00寅时上午03:00上午0
Stella981 Stella981
1年前
PostgreSQL的递归查询(with recursive)
开发有需求,说需要对一张地区表进行递归查询,Postgres中有个withrecursive的查询方式,可以满足递归查询(一般2层)。测试如下:createtabletb(idvarchar(3),pidvarchar(3),namevarchar(10));insertintotb
helloworld_34035044 helloworld_34035044
7个月前
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为