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

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

#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;
}

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

评论

h
hw_8058

对程序片段的解释和理解都在注释里了🤪

赞 0