首页 > 其他分享 >二叉排序链表C语言代码实现

二叉排序链表C语言代码实现

时间:2023-05-29 17:37:20浏览次数:37  
标签:lchild current C语言 tree 二叉 链表 rchild NULL data

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

typedef struct BSTNode{
    int data;
    struct BSTNode * lchild;
    struct BSTNode * rchild;
}BSTNode,* BSTree;

BSTNode * InitNode(int data){
    BSTNode * node = (BSTNode *)malloc(sizeof(BSTNode));
    if(node==NULL)exit(0);
    node->data=data;
    node->lchild=NULL;
    node->rchild=NULL;
    return node;
}


bool Insert(BSTree *tree,int data){
    BSTNode * node = InitNode(data);
    if(*tree == NULL){
       *tree= node;
       return true;
    }
    if(data<(*tree)->data){
        Insert(&((*tree)->lchild),data);
    }else{
        Insert(&((*tree)->rchild),data);
    }
}



void VisitInOrder(BSTree * tree){
    if(*tree==NULL)
    {
        printf("This is a invalid tree.");
        return;
    }
    if((*tree)->lchild !=NULL){
        VisitInOrder(&((*tree)->lchild));
    }
    printf("%d \n",(*tree)->data);
    if((*tree)->rchild !=NULL){
        VisitInOrder(&((*tree)->rchild));
    }
}

BSTNode * Query(BSTree tree,int data){
    if(tree==NULL)return NULL;
    if(tree->data == data){
       return tree;
    }
    if(data<tree->data)
    {
       return Query(tree->lchild,data);
    }
    else
    {
       return Query(tree->rchild,data);
    }
}

BSTNode * FindParent(BSTNode * tree,BSTNode * node){
    if(tree==NULL || node == NULL)return NULL;
    if((tree->lchild && tree->lchild==node)||(tree->rchild && tree->rchild == node)){
        return tree;
    }
    if(tree->lchild)return FindParent(tree->lchild,node);
    if(tree->rchild)return FindParent(tree->rchild,node);
}




bool DeleteData(BSTree* tree,int data){
    if(tree==NULL || *tree == NULL)return false;
    BSTNode * current = Query(*tree,data);
    if(current==NULL){
        printf("Data does not exist");
        return false;
    }

    BSTNode * q=NULL;
    BSTNode * s=NULL;
    if(current->lchild==NULL && current->rchild==NULL){
        if(current== *tree){//如果是根节点,直接赋值为空树即可。
           *tree=NULL;
           free(current);
           return;
        }
        BSTNode * p = FindParent(*tree ,current);//如果是叶子节点,需要找到父节点并把其child指针置空。
        if(p && p->lchild == current){
            p->lchild=NULL;
        }
        if(p && p->rchild==current){
            p->rchild=NULL;
        }
        free(current);
    }else if(current->lchild!=NULL && current->rchild==NULL){
        q=current->lchild;
        current->data=q->data;
        current->lchild=q->lchild;
        current->rchild=q->rchild;
        free(q);
    }else if(current->lchild==NULL && current->rchild!=NULL){
        q=current->rchild;
        current->data=q->data;
        current->lchild=q->lchild;
        current->rchild=q->rchild;
        free(q);
    }else{
        s=current->lchild;
        q=current;
        while(s->rchild){
            q=s;
            s=s->rchild;
        }
        current->data=s->data;
        if(current!=q){//根节点下有多层
            q->rchild=s->lchild;
        }else{//根节点下只有一层
            q->lchild=s->lchild;
        }
        free(s);
    }
}

    int main()
    {
        BSTree tree= NULL;
        int data=-1;
        printf("Entering data to create a node:\n");
        scanf("%d",&data);
        while(data!=-1){
           Insert(&tree,data);
           printf("Entering data to create a node:\n");
           scanf("%d",&data);
        }
        VisitInOrder(&tree);
        printf("enter a char to delete:\n");
        scanf("%d",&data);
        while(data!=-1){
           bool result = DeleteData(&tree,data);
           printf("delete result:%d\n",result);
           VisitInOrder(&tree);
           printf("enter a char to delete:\n");
           scanf("%d",&data);
        }
        return 0;
    }

 

标签:lchild,current,C语言,tree,二叉,链表,rchild,NULL,data
From: https://www.cnblogs.com/quota/p/17441116.html

相关文章

  • C语言课程设计题目[2023-05-29]
    C语言课程设计题目[2023-05-29]C语言课程设计题目一、设计要求与设计报告设计要求1.任意选定以下一个题目完成2.模块化程序设计3.锯齿型程序书写格式4.必须上机调试通过设计报告格式1.设计目的2.总体设计(程序设计组成框图、流程图)3.详细设计(模块功能说明(如函数功能、入......
  • LeetCode 700. 二叉搜索树中的搜索
    题目链接:LeetCode700.二叉搜索树中的搜索题意:给定二叉搜索树(BST)的根节点 root 和一个整数值 val。你需要在BST中找到节点值等于 val 的节点。返回以该节点为根的子树。如果节点不存在,则返回 null 。解题思路:递归法递归遍历二叉树,寻找与val相等的节点,找到即返回......
  • LeetCode 617. 合并二叉树
    题目链接:LeetCode617.合并二叉树题意:给你两棵二叉树:root1和root2。想象一下,当你将其中一棵覆盖到另一棵之上时,两棵树上的一些节点将会重叠(而另一些不会)。你需要将这两棵树合并成一棵新二叉树。合并的规则是:如果两个节点重叠,那么将这两个节点的值相加作为合并后节点的新......
  • 二叉排序树的三种遍历方式和实现源代码
    二叉排序树(BinarySearchTree)是一种特殊的二叉树,它满足以下性质:对于树中的每个节点,其左子树中的所有节点的值都小于该节点的值,而右子树中的所有节点的值都大于该节点的值。这种特性使得对于二叉排序树的遍历具有一定的规律。前序遍历(PreorderTraversal)是一种遍历二叉树的方法。......
  • c语言,函数的址传递例子
    编码如下:#include<stdio.h>voidswap(int*x,int*y){inttmp;tmp=*x;*x=*y;*y=tmp;};intmain(){inta=4;intb=5;printf("befer\n");printf("a=%d\n",a);printf("b=%d\n",b);swap(&am......
  • 代码随想录算法训练营第二十天|654. 最大二叉树、617. 合并二叉树、700. 二叉搜索树
    【参考链接】654.最大二叉树【注意】1.构造二叉树,都需要用前序遍历。2.二叉树的根是数组中的最大元素。3.没必要构造新数组,通过下标控制左右区间。运行效率会高很多。【代码】1#Definitionforabinarytreenode.2#classTreeNode(object):3#def__init......
  • 剑指 Offer 06. 从尾到头打印链表
    剑指Offer06.从尾到头打印链表</br></br>题目:输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。示例:输入:head=[1,3,2]输出:[2,3,1]限制:0<=链表长度<=10000</br></br>思路一:使用reverse函数完成链表的逆序打印。我们通过遍历将链表中的值插......
  • c语言代码怎么输入文字
    在C语言中,可以使用printf函数来输出文本信息到终端。如果需要从用户那里获取输入的文本信息,则可以使用scanf函数。以下是一个简单的示例代码:#include<stdio.h>intmain(){charname[20];printf("请输入您的姓名:");scanf("%s",name);printf("您好,%......
  • 用C语言为python写C扩展2
    spammodule.c#include<Python.h>staticPyObject*spam_system(PyObject*self,PyObject*args){constchar*command;intsts;if(!PyArg_ParseTuple(args,"s",&command))returnNULL;sts=system(command);......
  • C语言编程—枚举
    枚举是C语言中的一种基本数据类型,用于定义一组具有离散值的常量。它可以让数据更简洁,更易读。枚举类型通常用于为程序中的一组相关的常量取名字,以便于程序的可读性和维护性。定义一个枚举类型,需要使用enum关键字,后面跟着枚举类型的名称,以及用大括号{}括起来的一组枚举常量。......