精华内容
下载资源
问答
  • 二叉排序树 C语言实现

    千次阅读 多人点赞 2019-09-22 18:47:04
    二叉排序树,又称二叉搜索树(Binary search tree),是一种拥有排序的二叉树结构。其特点有: 结点k的所有左子树结点,都小于等于结点k 结点k的所有右子树结点,都大于等于结点k k的子树也都是二叉排序树(递归) ...

    基础知识

    • 二叉排序树,又称二叉搜索树(Binary search tree),是一种拥有排序功能的二叉树结构。其特点有:
    1. 结点k的所有左子树结点,都小于等于结点k
    2. 结点k的所有右子树结点,都大于等于结点k
    3. k的子树也都是二叉排序树(递归)

    显然,BST的中序遍历输出即为有序递增序列
    二叉树的搜索,插入等操作是基于二分法的,所以时间复杂度为logn

    • 二叉树的节点定义
    typedef struct BST{
    	int key;
    	struct BST *lchild;
    	struct BST *rchild;
    }BST;
    

    构建BST

    创建

    利用插入操作进行创建,首个节点在insert中分配,并将它赋值给指针bst,因为在insert中,要改变的是
    bst指向的内存的内容,而不改变指针的位置,即将指针传递给函数,并在函数中修改指针的值,所以这里用了二级指针。

    //创建 
    void create(BST **bst, int *key, int n){
    	int i=0;
    	for(i=0; i<n; i++){
    		insert(bst, key[i]);	
    	}//这里不需要返回值
    }
    

    插入

    在插入元素x时,从根节点开始,让x与节点的key比较,如果x < key,则将x递归插入到key 的左子树中,否则将x递归插入到key的右子树中; 如果子树不存在(到了叶节点),则分配内存,并将x放入。

    //插入 
    int insert(BST **bt, int key){
    	if(*bt == NULL){
    		*bt = (BST*)malloc(sizeof(BST));
    		if(*bt == NULL){
    			printf("分配内存失败\n");
    			return 0;
    		}
    		(*bt)->key = key;
    		(*bt)->lchild = (*bt)->rchild = NULL;
    		return 1;
    	}
    	if(key == (*bt)->key){//如果已存在,则插入失败 
    		printf("%d已存在!\n", key);
    		return 0;
    	}
    	else if(key < (*bt)->key)
    		insert(&(*bt)->lchild, key);
    	else
    		insert(&(*bt)->rchild, key);	
    	return 0;
    }
    

    查找

    查找元素x,方式为二分查找,从根节点开始,让x与节点的key比较,如果x < key,则在key 的左子树中查找,否则在key的右子树中查找。若找到,返回x对应的指针,否则查找失败

    //查找, 返回值是BST指针 
    BST *search(BST *bt, int key){
    	if(bt == NULL){
    		printf("查找失败!\n");
    		return bt;
    	}
    	else{
    		if(bt->key == key){
    			return bt;
    		}//递归查找
    		else if(key < bt->key)
    			return search(bt->lchild, key);	
    		else
    			return search(bt->rchild, key);
    	}	 
    }
    

    删除节点

    删除节点比较复杂,大体分4种情况

    1. 左右子树都为空
      直接清空指针内容即可,*p = NULL;
      在这里插入图片描述
    2. 左子树为空,右子树不为空
      在这里插入图片描述
    3. 右子树为空,左子树不为空
      在这里插入图片描述
    4. 左右子树都不为空
      若将节点p删除,代替它的应该是中序遍历中p的直接前驱s,只需要找到s,将其值赋给p,然后将s删除掉即可,而且对于s,一定符合上面两种情况,删除较容易。
      根据中序遍历规则,s的位置一定是下面两种情况
      在这里插入图片描述
      在这里插入图片描述
      为了便于操作,我们另p为s的父节点。
      (a). q != p在这里插入图片描述
      (b). q == p
      在这里插入图片描述
      代码如下:
    //删除节点 
    int delnode(BST **p){
    	//删除节点有4种情况
    	BST *s, *q;	
    	if((*p)->lchild == NULL && (*p)->rchild == NULL){ //左右子树都为空!
    		*p = NULL;  //二级指针下,可以直接令*p = NULL 
    		return 1; 	
    	}
    	else if(!(*p)->lchild){//左子树为空 
    		q = *p;  //让q指向p的右子树,然后把p的右子树挪到p的位置 
    		*p = (*p)->rchild;  
    		free(q);  
    		return 1;
    	}
    	else if(!(*p)->rchild){//右子树为空 
    		q = *p;
    		*p = (*p)->lchild;
    		free(q);
    		return 1;	
    	}
    	else{   //左右子树都不为空 
    		s = (*p)->lchild;
    		q = *p;
    		while(s->rchild){ //找到中序遍历中p的直接前驱s 
    			q = s;
    			s = s->rchild;
    		}
    		(*p)->key = s->key;  //把前驱的值赋值给p
    	
    		if(q != (*p))//如果q = *p,则while没执行,即p->lchild = s 
    			q->rchild = s->lchild; //叶子节点置空,必须使其父节点指向空,不能直接对叶子结点操作 
    		else //如果q = s 
    			q->lchild = s->lchild;//q不存在,p->lchild即为s 	
    		free(s);			
    	} 
    	return 1;
    } 
    

    删除

    递归删除

    //删除
    int del(BST **bt, int key){
    	if(*bt == NULL){
    		printf("未找到%d\n", key);
    		return 0;
    	}	
    	if((*bt)->key == key){
    		if(delnode(&(*bt)))
    			printf("已删除%d\n", key);
    		return 1;
    	}
    	else if((*bt)->key > key)
    		return del(&(*bt)->lchild, key);//因为bt中的值要改变,所以这里必须传入实值,定义为二级指针 
    	else
    		return del(&(*bt)->rchild, key);
    	
    }
    

    摧毁

    //摧毁树
    int destroy(BST *bst){
    	if(bst == NULL){
    		printf("树为空!\n");
    		return 0;
    	}
    	while(bst){
    		del(&bst, bst->key);	
    	}
    	free(bst);
    	printf("树已摧毁!\n");
    	return 1;
    }
    

    测试

    int main(void){
    	int *key;
    
    	int n, i=0;
    	int num, search_key, del_key;
    	printf("输入n:\n");
    	scanf("%d", &n);
    	key = (int *)malloc(sizeof(int)*n);
    	printf("输入数字:\n");
    	for(i=0; i<n; i++){
    		scanf("%d", &key[i]);
    	}
    	//创建 
    	BST *bst = NULL;
    	create(&bst, key, n);//这个数组传入指针即可
    	//中序遍历 
    	printf("中序遍历:\n");
    	inorder(bst);
    	//插入元素 
    	printf("输入插入元素:\n");
    	scanf("%d", &num);
    	insert(&bst, num);
    	printf("中序遍历:\n");
    	inorder(bst);
    	//查找元素 
    	printf("输入查找元素:\n");
    	scanf("%d", &search_key);
    	BST *result = NULL;
    	result = search(bst, search_key); //返回值是bt指针 
    	if(result)
    		printf("查找元素的指针是:result->key = %d\n", result->key); //这里的result即为BST指针 
    	//删除元素
    	printf("输入要删除的元素:\n");
    	scanf("%d", &del_key); 
    	del(&bst, del_key);
    	printf("中序遍历:\n");
    	inorder(bst);
    	//摧毁,摧毁后要想使用必须重建bst 
    	printf("摧毁树\n");
    	destroy(bst);
    	//printf("*bst = %d\n", *bst);
    	
    	return 0;
    }
    

    完整可运行代码

    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct BST{
    	int key;
    	struct BST *lchild;
    	struct BST *rchild;
    }BST;
    
    void create(BST **bst, int *key, int n);
    int insert(BST **bt, int key);
    void inorder(BST *bt);
    BST *search(BST *bt, int key);  
    int delnode(BST **p);
    int del(BST **bt, int key);
    int destroy(BST *bst); 
    
    int main(void){
    	int *key;
    	
    	int n, i=0;
    	int num, search_key, del_key;
    	printf("输入n:\n");
    	scanf("%d", &n);
    	key = (int *)malloc(sizeof(int)*n);
    	printf("输入数字:\n");
    	for(i=0; i<n; i++){
    		scanf("%d", &key[i]);
    	}
    	//创建 
    	BST *bst = NULL;
    	create(&bst, key, n);//这个数组传入指针即可
    	//中序遍历 
    	printf("中序遍历:\n");
    	inorder(bst);
    	//插入元素 
    	printf("输入插入元素:\n");
    	scanf("%d", &num);
    	insert(&bst, num);
    	printf("中序遍历:\n");
    	inorder(bst);
    	//查找元素 
    	printf("输入查找元素:\n");
    	scanf("%d", &search_key);
    	BST *result = NULL;
    	result = search(bst, search_key); //返回值是bt指针 
    	if(result)
    		printf("查找元素的指针是:result->key = %d\n", result->key); //这里的result即为BST指针 
    	//删除元素
    	printf("输入要删除的元素:\n");
    	scanf("%d", &del_key); 
    	del(&bst, del_key);
    	printf("中序遍历:\n");
    	inorder(bst);
    	//摧毁,摧毁后要想使用必须重建bst 
    	printf("摧毁树\n");
    	destroy(bst);
    	//printf("*bst = %d\n", *bst);
    	
    	return 0;
    }
    //创建 
    void create(BST **bst, int *key, int n){
    	int i=0;
    	for(i=0; i<n; i++){
    		insert(bst, key[i]);	
    	}
    }
    //插入 
    int insert(BST **bt, int key){
    	if(*bt == NULL){
    		*bt = (BST*)malloc(sizeof(BST));
    		if(*bt == NULL){
    			printf("分配内存失败\n");
    			return 0;
    		}
    		(*bt)->key = key;
    		(*bt)->lchild = (*bt)->rchild = NULL;
    		//printf("(*bt)->key=%d\n",(*bt)->key);
    		return 1;
    	}
    	if(key == (*bt)->key){//如果已存在,则插入失败 
    		printf("%d已存在!\n", key);
    		return 0;
    	}
    	else if(key < (*bt)->key)
    		insert(&(*bt)->lchild, key);
    	else
    		insert(&(*bt)->rchild, key);	
    	return 0;
    }
    //查找  返回值是BST指针 
    BST *search(BST *bt, int key){
    	if(bt == NULL){
    		printf("查找失败!\n");
    		return bt;
    	}
    	else{
    		if(bt->key == key){
    			return bt;
    		}
    		else if(key < bt->key)
    			return search(bt->lchild, key);	
    		else
    			return search(bt->rchild, key);
    	}	 
    }
    //删除节点 
    int delnode(BST **p){
    	//删除节点有4种情况
    	BST *s, *q;
    		
    	if((*p)->lchild == NULL && (*p)->rchild == NULL){ //左右子树都为空!
    		*p = NULL;  //二级指针下,可以直接令*p = NULL 
    		return 1; 	
    	}
    	else if(!(*p)->lchild){//左子树为空 
    		q = *p;  //让q指向p的右子树,然后把p的右子树挪到p的位置 
    		*p = (*p)->rchild; 
    		free(q); 
    		return 1;
    	}
    	else if(!(*p)->rchild){//右子树为空 
    		q = *p;
    		*p = (*p)->lchild;
    		free(q);
    		return 1;	
    	}
    	else{   //左右子树都不为空 
    		s = (*p)->lchild;
    		q = *p;
    		while(s->rchild){ //找到中序遍历中p的直接前驱 
    			q = s;
    			s = s->rchild;
    		}
    		(*p)->key = s->key;  //把前驱的值赋值给p
    	
    		if(q != (*p))//如果q = *p,则while没执行,即p->lchild = s 
    			q->rchild = s->lchild; //叶子节点置空,必须使其父节点指向空,不能直接对叶子结点操作 
    		else //如果q = s 
    			q->lchild = s->lchild;//q不存在,p->lchild即为s 
    			
    		free(s);			
    	} 
    	return 1;
    } 
    //删除
    int del(BST **bt, int key){
    	if(*bt == NULL){
    		printf("未找到%d\n", key);
    		return 0;
    	}	
    	if((*bt)->key == key){
    		if(delnode(&(*bt)))
    			printf("已删除%d\n", key);
    		return 1;
    	}
    	else if((*bt)->key > key)
    		return del(&(*bt)->lchild, key);//因为bt中的值要改变,所以这里必须传入实值,定义为二级指针 
    	else
    		return del(&(*bt)->rchild, key);
    } 
    //摧毁树
    int destroy(BST *bst){
    	if(bst == NULL){
    		printf("树为空!\n");
    		return 0;
    	}
    	while(bst){
    		del(&bst, bst->key);	
    	}
    	free(bst);
    	printf("树已摧毁!\n");
    	return 1;
    }
    //中序遍历
    void inorder(BST *bt){
    	if(bt!=NULL){
    		inorder(bt->lchild);
    		printf("%d\n",bt->key);
    		inorder(bt->rchild);
    	}
    }
    
    展开全文
  • C语言实现数据结构 二叉排序树C语言实现数据结构 二叉排序树C语言实现数据结构 二叉排序树C语言实现数据结构 二叉排序树
  • 二叉排序树C实现代码

    2018-03-05 22:25:25
    二叉排序树C语言的简单实现,包含如下操作: 1.创建二叉排序树; 2.销毁二叉排序树; 3.清空二叉排序树; 4.插入指点结点至二叉排序树; 5.删除二叉排序树指点结点; 5.获取二叉排序树指定结点; 6.获取二叉排序树根...
  • 二叉排序树C语言实现

    2021-12-12 11:44:09
    今天来给大家讲解一下二叉排序树C语言代码实现 typedef int ElemType; // 自定义数据元素为整数。 // 二叉树的数据结构。 typedef struct BSTNode { ElemType data; // 存放结点的数据元素。 struct ...

     今天来给大家讲解一下二叉排序树C语言代码实现

     

    
    
    typedef int ElemType;     // 自定义数据元素为整数。
    
    // 二叉树的数据结构。
    typedef struct BSTNode
    {
        ElemType   data;           // 存放结点的数据元素。
        struct BSTNode* lchild;    // 指向左子结点地址的指针。
        struct BSTNode* rchild;    // 指向右子结点地址的指针。
    }BSTNode, * BSTree;
    ///
    
    // 在树TT中插入关键字为ee的新结点(递归实现),返回值:0-树中已存在关键字为ee的结点;1-成功。
    int Insert(BSTree* TT, ElemType* ee);
    // 在树TT中插入关键字为ee的新结点(非递归实现),返回值:0-树中已存在关键字为ee的结点;1-成功。
    int Insert1(BSTree* TT, ElemType* ee);
    
    // 用数组arr中的序列构建二叉排序树TT。
    // 以下两种写法都可以。
    //void CreateBST(BSTree *TT,int arr[],int len);
    void CreateBST(BSTree* TT, int* arr, int len);
    
    // 在树TT中查找值为ee的结点(递归实现),成功返回结点的地址,失败返回NULL。
    BSTNode* Find(BSTree TT, ElemType* ee);
    // 在树TT中查找值为ee的结点(非递归实现),成功返回结点的地址,失败返回NULL。
    BSTNode* Find1(BSTree TT, ElemType* ee);
    
    // 在树TT中删除值为ee的结点,成功返回0,结点不存在返回1。
    int Delete(BSTree* TT, ElemType* ee);
    
    // 求二叉树的高度。
    int TreeDepth(BSTree TT);
    
    // 访问结点元素。
    void visit(BSTNode* pp);
    
    // 采用递归的方法对二叉树的先序遍历。
    void PreOrder(BSTree TT);
    
    // 采用递归的方法对二叉树的中序遍历。
    void InOrder(BSTree TT);
    
    // 采用递归的方法对二叉树的后序遍历。
    void PostOrder(BSTree TT);
    
    int main()
    {
        BSTree TT = 0; // 声明树指针变量。
    
        ElemType arr[] = { 50,66,60,26,21,30,70,68 };
    
        /*
        // 用数组arr中的序列构建二叉排序树TT。
        // 构建的二叉排序树将如下:
                    50
                 /     \
                26      66
               /  \    /  \
              21  30 60   70
                         /
                        68
        */
        CreateBST(&TT, arr, sizeof(arr) / sizeof(ElemType));
    
        ElemType ee;
    
        // 在树TT中查找值为ee的结点,成功返回结点的地址,失败返回NULL。
        ee = 30;
        BSTNode* ss = Find(TT, &ee);
        if (ss != NULL) printf("查找成功,结点的地址是%p,值是%d。\n", ss, ss->data);
        else printf("查找失败。\n");
    
        // 二叉树的中序遍历。
        printf("中序遍历结果1:"); InOrder(TT); printf("\n");
    
        // 在树TT中删除值为ee的结点,成功返回0,结点不存在返回1。
        ee = 50;
        printf("从树中删除值为ee的结点,Delete()的返回值是%d。\n", Delete(&TT, &ee));
    
        // 二叉树的中序遍历。
        printf("中序遍历结果2:"); InOrder(TT); printf("\n");
    
        return 0;
    }
    
    // 二叉树的先序遍历。
    void PreOrder(BSTree TT)
    {
        if (TT == NULL) return;
    
        visit(TT);               // 访问子树TT的根结点。
        PreOrder(TT->lchild);    // 遍历左子树。
        PreOrder(TT->rchild);    // 遍历右子树。
    }
    
    // 二叉树的中序遍历。
    void InOrder(BSTree TT)
    {
        if (TT == NULL) return;
    
        InOrder(TT->lchild);     // 遍历左子树。
        visit(TT);               // 访问子树TT的根结点。
        InOrder(TT->rchild);     // 遍历右子树。
    }
    
    // 二叉树的后序遍历。
    void PostOrder(BSTree TT)
    {
        if (TT == NULL) return;
    
        PostOrder(TT->lchild);     // 遍历左子树。
        PostOrder(TT->rchild);     // 遍历右子树。
        visit(TT);                 // 访问子树TT的根结点。
    }
    
    // 求二叉树的高度。
    int TreeDepth(BSTree TT)
    {
        if (TT == NULL) return 0;
    
        int ll = TreeDepth(TT->lchild);  // 求左子树的高度。
    
        int rr = TreeDepth(TT->rchild);  // 求右子树的高度。
    
        return ll > rr ? ll + 1 : rr + 1;     // 取左、右子树的较大者再加上根结点的高度。
    }
    
    // 访问结点元素。
    void visit(BSTNode* pp)
    {
        printf("%d ", pp->data);  // 访问结点元素就是把值输出来,意思一下就行了。
    }
    
    // 在树TT中插入关键字为ee的新结点(递归实现),返回值:0-树中已存在关键字为ee的结点;1-成功。
    int Insert(BSTree* TT, ElemType* ee)
    {
        // 如果当前子树为空,创建子树的根结点。
        if ((*TT) == NULL)
        {
            (*TT) = (BSTree)malloc(sizeof(BSTNode));
            memcpy(&(*TT)->data, ee, sizeof(ElemType));  // 考虑数据元素ee为结构体的情况,采用memcpy而不是直接赋值。
            (*TT)->lchild = (*TT)->rchild = NULL;  // 当前子树的左右孩子指针置空。
            return 1;  // 返回成功。
        }
    
        if (*ee == (*TT)->data) return 0; // 如果ee已存在,返回失败。
    
        if (*ee < (*TT)->data) Insert(&(*TT)->lchild, ee);  // 递归向左插入。
        else Insert(&(*TT)->rchild, ee);  // 递归向右插入。
    }
    
    // 在树TT中插入关键字为ee的新结点(非递归实现),返回值:0-树中已存在关键字为ee的结点;1-成功。
    int Insert1(BSTree* TT, ElemType* ee)
    {
        // 如果树为空,创建树的根结点。
        if ((*TT) == NULL)
        {
            (*TT) = (BSTree)malloc(sizeof(BSTNode));
            memcpy(&(*TT)->data, ee, sizeof(ElemType));  // 考虑数据元素ee为结构体的情况,采用memcpy而不是直接赋值。
            (*TT)->lchild = (*TT)->rchild = NULL;  // 树的左右孩子指针置空。
            return 1;  // 返回成功。
        }
    
        BSTNode* pss = NULL;  // 记录双亲结点的地址。
        BSTNode* ss = (*TT);  // 用于查找的临时指针。
        int  rl = 0;          // 记录ss是双亲结点的左子树还是右子树,0-左子树;1-右子树。
    
        while (ss != NULL)
        {
            if (*ee == ss->data) return 0; // 如果ee已存在,返回失败。
    
            pss = ss;  // 记录双亲结点的地址。
            if (*ee < ss->data) { ss = ss->lchild; rl = 0; }  // 继续向左走。
            else { ss = ss->rchild; rl = 1; }  // 继续向右走。
        }
    
        // 分配新结点。
        ss = (BSTree)malloc(sizeof(BSTNode));
        memcpy(&ss->data, ee, sizeof(ElemType));  // 考虑数据元素ee为结构体的情况,采用memcpy而不是直接赋值。
        ss->lchild = ss->rchild = NULL;  // 当前子树的左右孩子指针置空。
    
        // 让双亲结点的左或右指针指向新分配的结点。
        if (rl == 0) pss->lchild = ss;
        else pss->rchild = ss;
    
        return 1;  // 返回成功。
    }
    
    // 用数组arr中的序列构建二叉排序树TT。
    // 以下两种写法都可以。
    //void CreateBST(BSTree *TT,int arr[],int len)
    void CreateBST(BSTree* TT, int* arr, int len)
    {
        (*TT) = NULL;
    
        int ii = 0;
        for (ii = 0; ii < len; ii++)
        {
            Insert(TT, &arr[ii]);  // 把数组中的元素逐个插入树中。
            // Insert1(TT,&arr[ii]);  // 把数组中的元素逐个插入树中。
        }
    }
    
    // 在树TT中查找值为ee的结点(递归实现),成功返回结点的地址,失败返回NULL。
    BSTNode* Find(BSTree TT, ElemType* ee)
    {
        if (TT == NULL) return NULL;    // 查找失败。
    
        if (*ee == TT->data) return TT;  // 查找成功。 
    
        if (*ee < TT->data) return Find(TT->lchild, ee); // 递归向左查找。
        else return Find(TT->rchild, ee);             // 递归向右查找。
    }
    
    // 在树TT中查找值为ee的结点(非递归实现),成功返回结点的地址,失败返回NULL。
    BSTNode* Find1(BSTree TT, ElemType* ee)
    {
        BSTNode* ss = TT;  // 用于查找的临时指针,也可以直接用TT。
    
        while (ss != NULL)
        {
            if (*ee == ss->data) return ss;  // 成功找到。
    
            if (*ee < ss->data) ss = ss->lchild;  // 继续向左走。
            else ss = ss->rchild;  // 继续向右走。
        }
    
        return NULL;
    
        /*
        // 以下代码更精简,可以取代以上的代码。
        while ( (TT!=NULL) && (*ee!=TT->data) )
        {
          if (*ee<TT->data) TT=TT->lchild;  // 继续向左走。
          else TT=TT->rchild;  // 继续向右走。
        }
    
        return TT;
        */
    }
    
    // 在树TT中删除值为ee的结点,成功返回0,结点不存在返回1。
    int Delete(BSTree* TT, ElemType* ee)
    {
        if ((*TT) == NULL) return 1; // 树为空,返回1。
    
        // 1)如果树只有根结点,并且待删除的结点就是根结点。
        if (((*TT)->data == *ee) && ((*TT)->lchild == NULL) && ((*TT)->rchild == NULL))
        {
            free(*TT); (*TT) = 0; return 0;
        }
    
        BSTNode* pss = NULL;  // 记录双亲结点的地址。
        BSTNode* ss = (*TT);  // 用于查找的临时指针。
        int  rl = 0;          // 记录ss是双亲结点的左子树还是右子树,0-左子树;1-右子树。
    
        // 查找待删除的结点。
        while (ss != NULL)
        {
            if (*ee == ss->data) break;  // 成功找到。
    
            pss = ss;  // 记录双亲结点的地址。
            if (*ee < ss->data) { ss = ss->lchild; rl = 0; }  // 继续向左走。
            else { ss = ss->rchild; rl = 1; }  // 继续向右走。
        }
    
        // 结点不存在,返回1。
        if (ss == NULL) return 1;
    
        // 2)如果待删除的结点ss是叶结点,直接删除,不会破坏二叉排序树的性质。
        if ((ss->lchild == NULL) && (ss->rchild == NULL))
        {
            free(ss);   // 释放结点。
    
            // 修改双亲结点pss的左或右指针指向NULL。
            if (rl == 0) pss->lchild = NULL;
            else pss->rchild = NULL;
    
            return 0;  // 返回成功。
        }
    
        // 3)如果待删除的结点ss只有左子树或右子树,则让子树代替自己。
        if ((ss->lchild == NULL) || (ss->rchild == NULL))
        {
            if (ss->lchild != NULL)  // 有左子树。
            {
                // 修改双亲结点pss的左或右指针指向ss的左子树。
                if (rl == 0) pss->lchild = ss->lchild;
                else pss->rchild = ss->lchild;
            }
            else  // 有右子树。
            {
                // 修改双亲结点pss的左或右指针指向ss的右子树。
                if (rl == 0) pss->lchild = ss->rchild;
                else pss->rchild = ss->rchild;
            }
    
            return 0;  // 返回成功。
        }
    
        // 4)如果待删除的结点ss有左子树和右子树,让左子树最右侧的结点代替自己,然后再删除左子树最右侧的结点。
        // 也可以让右子树最左侧的结点代替自己,然后删除右子树最左侧的结点。
        BSTNode* pss1 = ss;        // 记录双亲结点的地址。
        BSTNode* ss1 = ss->lchild; // 用于查找的临时指针。
        int  rl1 = 0;              // 记录ss1是双亲结点的左子树还是右子树,0-左子树;1-右子树。
    
        // 左子树向右走到尽头。
        while (ss1->rchild != NULL)
        {
            rl1 = 1; pss1 = ss1; ss1 = ss1->rchild;
        }
    
        // 把左子树最右侧的结点值复制到结点ss中。
       
    
        // 左子树最右侧的结点ss1必定无右子树。
        // 修改双亲结点pss1的左或右指针指向ss1的左子树,ss1的左子树可以为空。
        if (rl1 == 0) pss1->lchild = ss1->lchild;
        else pss1->rchild = ss1->lchild;
    
        free(ss1);  // 释放ss1。
    
        return 0;
    }
    
    
    //删除写法二:
    //直接返回删除后的树
    BSTree Delete2(BSTree TT, ElemType ee)
    {
        BSTree f, p;
        //f指针记录待删除结点的双亲结点
        //p指针用来记录待删除结点
        f = NULL;
        p = TT;
        while (p)
        {
            if (p->data = ee)  break;
            f = p;
            if (p->data > ee)  p = p->lchild;
            else p = p->rchild;
        }
    
        //第一种情况p为NULL,即是没有待删除结点
        if (p == NULL) return TT;
    
        //分为两种情况,待删除结点有左子树和无左子树
        if (p->lchild == NULL) //无左子树
        {
            //对双亲结点进行三种讨论
    
            //第一种如果双亲结点是空
            if (f == NULL)  TT = p->rchild;
    
            //第二种p是f的左孩子
            else if (f->lchild == p)  f->lchild = p->rchild;
    
            //第三种p是f的右孩子
    
            else  f->rchild = p->rchild;
    
            free(p);
    
        }
    
        //找到以p为根节点左子树的最右边
        
        else
        {
           //m是n的双亲结点
    
           //m为p结点,n为p结点的左孩子
            BSTree m = p, n = p->lchild;
    
            //找到以p为根节点左子树的最右边
            while (n->rchild)
            {
                m = n;
                n = n->rchild;
            }
            
            //为两种情况,以n为根节点的树有无右子树
    
            if (p == m) m->lchild = n->lchild;
    
            else m->rchild = n->lchild;
    
            p->data = n->data;
    
            free(n);
    
    
    
        }
        return TT;
    
    
    }
    

    展开全文
  • 数据结构实验之查找一:二叉排序树 C Time Limit: 400MS Memory Limit: 65536KB Problem Description 对应给定的一个序列可以唯一确定一棵二叉排序树。然而,一棵给定的二叉排序树却可以由多种不同的序列得到。...

    数据结构实验之查找一:二叉排序树 C

    Time Limit: 400MS Memory Limit: 65536KB
    Problem Description
    对应给定的一个序列可以唯一确定一棵二叉排序树。然而,一棵给定的二叉排序树却可以由多种不同的序列得到。例如分别按照序列{3,1,4}和{3,4,1}插入初始为空的二叉排序树,都得到一样的结果。你的任务书对于输入的各种序列,判断它们是否能生成一样的二叉排序树。

    Input
    输入包含若干组测试数据。每组数据的第1行给出两个正整数N (n < = 10)和L,分别是输入序列的元素个数和需要比较的序列个数。第2行给出N个以空格分隔的正整数,作为初始插入序列生成一颗二叉排序树。随后L行,每行给出N个元素,属于L个需要检查的序列。
    简单起见,我们保证每个插入序列都是1到N的一个排列。当读到N为0时,标志输入结束,这组数据不要处理。

    Output
    对每一组需要检查的序列,如果其生成的二叉排序树跟初始序列生成的二叉排序树一样,则输出”Yes”,否则输出”No”。

    Example Input
    4 2
    3 1 4 2
    3 4 1 2
    3 2 4 1
    2 1
    2 1
    1 2
    0
    Example Output
    Yes
    No
    No

    代码块

    #include <stdio.h>
    #include <stdlib.h>
    struct node
    {
        int data,d;
        struct node *l,*r;
    };
    
    int deep(struct node *root)
    {
        if(root==NULL)
            return -1;
        else
            return root->d;
    }
    struct node *LL(struct node *root)
    {
        struct node *p;
        p=root->l;
        root->l=p->r;
        p->r=root;
        if(deep(root->l)>deep(root->r))
    
            root->d=deep(root->l)+1;
        else
            root->d=deep(root->r)+1;
        if(deep(p->l)>deep(p->r))
    
            p->d=deep(p->l)+1;
        else
            p->d=deep(p->r)+1;
            return p;
    }
    struct node *RR(struct node *root)
    {
        struct node *p;
        p=root->r;
        root->r=p->l;
        p->l=root;
        if(deep(root->l)>deep(root->r))
    
            root->d=deep(root->l)+1;
        else
            root->d=deep(root->r)+1;
        if(deep(p->l)>deep(p->r))
    
            p->d=deep(p->l)+1;
        else
            p->d=deep(p->r)+1;
            return p;
    }
    struct node *LR(struct node *root)
    {
        root->l=RR(root->l);
        return LL(root);
    }
    struct node *RL(struct node *root)
    {
        root->r=LL(root->r);
        return RR(root);
    }
    struct node *creat(struct node *root,int x)
    {
        if(root==NULL)
        {
            root=(struct node *)malloc(sizeof(struct node));
            root->d = 0; //会忘
            root->data=x;
            root->l=root->r=NULL;
        }
        else if(x<root->data)
        {
            root->l=creat(root->l,x);
            if(deep(root->l)-deep(root->r)==2)
            {
                if(x<root->l->data)
                    root=LL(root);
                else
                    root=LR(root);
            }
        }
        else if(x>root->data)
        {
            root->r=creat(root->r,x);
            if(deep(root->r)-deep(root->l)==2)
            {
                if(x>root->r->data)
                    root=RR(root);
                else
                    root=RL(root);
            }
        }
        if(deep(root->l)>deep(root->r))
    
            root->d=deep(root->l)+1;
        else
            root->d=deep(root->r)+1;
        return root;
    };
    int main()
    {
        int n,i,x;
        struct node *root;
        root=NULL;
        scanf("%d",&n);
        for(i=0; i<n; i++)
        {
            scanf("%d",&x);
            root=creat(root,x);
        }
        printf("%d",root->data);
        return 0;
    }
    
    /***************************************************
    User name: cb020502
    Result: Accepted
    Take time: 0ms
    Take Memory: 144KB
    Submit time: 2018-08-15 10:23:30
    ****************************************************/
    展开全文
  • 我们在上一篇博客中讲解了二叉树,这一次我们来实现二叉树的...  二叉排序树的一个重要特点是中序遍历是一个递增序列。示例代码上传至: https://github.com/chenyufeng1991/BinarySearchTree 。  (1)节点的构造
  • 二叉排序树C语言实现一

    千次阅读 2016-05-06 16:29:32
    二叉排序树插入,删除,查找等各种操作手工模拟并用C语言实现。

    一、定义:

      二叉排序树(二叉搜索树、二叉查找树)或者是空树,或者满足以下性质:`

    (1)若它的左子树非空,则左子树上所有记录的值均小于根记录的值;

    (2)若它的右子树非空,则右子树上所有记录的值均大于根记录的值;

    (3)左、右子树本身又各是一颗二叉排序树。

        ——该定义源于《数据结构》李春葆

    示例:

                     

    二、数据结构:

    使用一个链表数据结构来表示,节点定义如下:

    typedef struct STnode
    {
        int key;//数据信息
        struct STnode *left;//指向左孩子
        struct STnode *right;//指向右孩子
        struct STnode *p;//指向父节点
    } STnode;

    三、插入操作:

    二叉搜索树插入操作比较简单,将欲插入节点my_node从根节点开始比较,用cur_node表示当前被比较的节点,如果my_node.key > cur_node.key,则比较其右孩子,否则比较其左孩子,以此类推,直到找到叶节点为止,将my_node插入(大于所找到的叶节点则作为右孩子插入,小于则作为左孩子插入)。注意:插入操作一定是在叶节点上进的


    示例:插入关键字为9的节点,先和根节点比较(9>6),故与其右孩子节点比较(9>7),继续与其右孩子节点比较(9>8),由于该节点为叶节点,且9>8,则将节点作为右孩子插入。


    代码:

    //将节点my_node插入到二叉搜索树tree
    STnode* STree_Insert(STnode *tree, STnode *my_node)
    {
        STnode *parent_node;//指向my_node的父节点
        STnode *cur_node;//指向当前被比较的节点
        
        //树为空
        if(tree==NULL)
            tree=my_node;
            
        //树不为空    
        else
        {
            parent_node=NULL;
            cur_node=tree;
            while(cur_node!=NULL) //while循环寻找my_node的父节点
            {
                parent_node=cur_node;
                if(my_node->key < cur_node->key)
                    cur_node=cur_node->left;
                else
                    cur_node=cur_node->right;
            }
            my_node->p=parent_node;
            if(my_node->key < parent_node->key)//插入到左子树
                parent_node->left=my_node;
            else                               //插入到右子树  
                parent_node->right=my_node;
        }
        return tree;
    }


    四、查找节点

    思想比较简单,直接上代码:

    //在tree里查找节点my_node
    STnode *STree_Find(STnode *tree, int my_key)
    {
        STnode *cur_node=tree;
        
        if(tree==NULL)
            return NULL;
        else
        {
            while(cur_node->key != my_key)
            {
                if(my_key < cur_node->key)
                    cur_node=cur_node->left;
                else
                    cur_node=cur_node->right;
            }
            return cur_node;
        }
    }

    五、返回最小关键字节点

    根据二叉排序树的性质可知,关键字最小的节点一定是整棵树中最左边的节点所以只需从根节点开始一直寻找left指

    针,直到找到NULL为止。

    代码:

    //返回最小关键字所在节点
    STnode *STree_Min(STnode *tree)
    {
        STnode *cur_node=tree;
        
        while(cur_node->left)
        {
            cur_node=cur_node->left;
        }
        return cur_node;
    }

    六、返回最大关键字所在节点

    根据二叉排序树的性质可知,关键字最大的节点一定是整棵树中最右边的节点所以只需从根节点开始一直寻找right

    指针,直到找到NULL为止。

    代码:

    //返回最大关键字所在节点
    STnode *STree_Max(STnode *tree)
    {
        STnode *cur_node=tree;
        
        while(cur_node->right)
        {
            cur_node=cur_node->right;
        }
        return cur_node;
    }

    七、查找节点后继(中序)

    中序序列为:左子树、根、右子树,则一个节点若存在中序后继,则该后继必然位于该节点右边。

    下图所示二叉排序树的中序为:2、3、4、6、7、13、15、17、18、20


    ——该图源于《算法导论》


    如上所述,节点的后继一定位于节点右边,分两种情况:

    1、该节点右孩子不为空:其后继必然是右子树上的最左节点(如节点6,后继为节点9);

    2、该节点右孩子为NULL且该节点为其父节点的左孩子:后继为其父节点(如节点2,后继为节点3);

    3、该节点右孩子为NULL且该节点为其父节点的右孩子:后继必为该节点所在“子树”根节点T的父节点,该根节点T

    必为其父节点的左孩子,否则继续往上寻找(如节点13,满足该子树根节点为其父节点左孩子的子树根节点为6,

    该节点为其父节点15的左孩子,故该节点后继为15)

    代码:

    STnode *STree_Successor(STnode *my_node)
    {
        STnode *cur_node;
        STnode *successor;
        if(my_node->right)//右孩子不为空
            return STree_Min(my_node->right);
        else              //右孩子为空
        {
            if(my_node==my_node->p->left)//该节点为父节点左孩子
                return my_node->p;
            else//该节点为父节点右孩子
            {
                cur_node=my_node;
                successor=cur_node->p;
                while(successor!=NULL && cur_node!=successor->left)
                {
                    cur_node=cur_node->p;
                    successor=cur_node->p;
                }
                return successor;
            }
        }
    }

    八、查找节点前驱(中序)

    查找节点前驱的算法和查找节点后继的算法对称,也分为三种情况,分析分发一样,直接上代码。

    代码:

    STnode *STree_Predecessor(STnode *my_node)
    {
        STnode *cur_node;
        STnode *predecessor;
        if(my_node->left)//左孩子不为空
            return STree_Max(my_node->left);
        else              //左孩子为空
        {
            if(my_node==my_node->p->right)//该节点为父节点右孩子
                return my_node->p;
            else//该节点为父节点左孩子
            {
                cur_node=my_node;
                predecessor=cur_node->p;
                while(predecessor!=NULL && cur_node!=predecessor->right)
                {
                    cur_node=cur_node->p;
                    predecessor=cur_node->p;
                }
                return predecessor;
            }
        }
    }

    七、删除节点

    删除节点操作是二叉排序树所有操作中最复杂最难理解的操作,在下一篇博文

    (链接地址http://blog.csdn.net/xiaowang627/article/details/51336272 )中对其进行详细的图文描述

    同时对所有函数进行测试。


    展开全文
  • 二叉排序树C语言

    2020-02-03 16:11:32
    程序实现二叉排序树C语言入门小程序,适合C语言课程入门的小练习。 程序实现二叉排序树C语言入门小程序,适合C语言课程入门的小练习。 程序实现二叉排序树C语言入门小程序,适合C语言课程入门的小练习。
  • 二叉排序树,详细概念略过,参考数据结构书籍;详细代码如下:(以下代码,均可直接运行) 存储结构:二叉链表 typedef struct SOSTree { int data; struct SOSTree *LChild, *RChild; } SOSTree; 插入: bool ...
  • 主要介绍了C语言判定一棵二叉树是否为二叉搜索的方法,结合实例形式综合对比分析了C语言针对二叉搜索判定的原理、算法、效率及相关实现技巧,需要的朋友可以参考下
  • 出现的问题莫名其妙#include#includetypedefintKeyType;typedefstructnode{KeyTypekey;structnode*lchild,*rchild;...//二叉排序树插...出现的问题莫名其妙#include #include typedef int KeyType;typedef struc...
  • /************************** 判断是否为二叉排序树 ***********************************/ #include<stdio.h> typedef struct abc { struct abc *lchild,*rchild; int data; }Node; Node * init(int data);...
  • c语言二叉排序树代码

    2013-10-29 20:01:36
    c语言二叉排序树代码,根据排序树特性组成的二叉树,利用中序遍历读出
  • 读一个文件,文件中包含2000个以上英文名字 利用二叉数进行查找,在查找过程中避免 冲突的代码
  • 二叉排序树-C语言

    2019-12-13 15:50:16
    1.二叉排序树是递归定义的,得到一个重要性质:中序遍历二叉排序树,可以得到结点值递增的有序序列。 2.当先后插入二叉排序树有序时,生成单支树,单支树的查找性能较差。 3.二叉排序树的查找与折半查找类似,但就...
  • #include<stdio.h> #include<stdlib.h> #define max 10 typedef struct node{ int data; node *lchild*rchild; }Bitree; Bitree *B[max]; int temp=0; int Btree[max]; Bitree *Creatree){ //建立二叉树 Bitree *T*S...
  • 二叉排序树(C语言简单实现)

    千次阅读 2020-11-22 14:32:25
    二叉排序树(C语言简单实现) 本文参考自《大话数据结构》 如果查找的数据集是有序线性表,并且是顺序存储的,查找可以用折半、插值、斐波那契等查找算法来实现,可惜,因为有序,在插入和删除操作上,就需要耗费...
  • 创建二叉排序树C语言实现

    千次阅读 2014-06-23 17:04:42
    //二叉查找结点描述 typedef int KeyType; typedef struct Node { KeyType key; //关键字 struct Node * left; //左孩子指针 struct Node * right; //右孩子指针 struct Node * parent; //指向父节点...
  • 二叉排序树与文件操作】 功能要求: (1)从键盘输入一组学生记录建立二叉排序树; (2)二叉排序树存盘; (3)由文件恢复内存的二叉排序树; (4)中序遍历二叉排序树; (5)求二叉排序树深度; (6)求二叉...
  • 在上一篇文章中(http://blog.csdn.net/xiaowang627/article/details/51332201),对二叉排序树的定义和查找、插入等操作进行了图文描述和C语言实现,本文将详解二叉搜索树的删除操作。一、节点删除:如下图所示 (1)...
  • 掌握二叉排序树的存储方法,实现二叉排序树的创建、查找、插入、删除、平均查找长度等基本操作。 三、实验内容及要求 1、构造二叉排序树的存储结构。 2、实现创建、查找、插入、删除、平均查找长度等操作。
  • 《数据结构》实验报告班级:姓名:学号:E-mail:日期:◎实验题目: 建立二叉排序树,并中序遍历输出,输入一个关键字进行查找。 ◎实验目的:熟悉并掌握二叉排序树的建立及遍历输出以及非递归查找。◎实验内容:输入一...
  • 本文链接:二叉排序树(Binary Sort Tree)c语言 二叉排序树,又称为二叉查找树。它或则是一颗空树,或者是带有以下性质的二叉树:构造二叉排序树的目的,并不是为了顺序,而是为了提升查找和插入删除关键字的速度。...
  • 数据结构之二叉排序树C语言实现)

    万次阅读 多人点赞 2018-05-21 23:35:10
    1.二叉排序树 二叉排序树(Binary sort tree,BST),又称为二叉查找树,或者是一棵空树;或者是具有下列性质的二叉树: (1)若它的左子树不为空,则左子树上所有节点的值均小于它的根节点的值; (2)若它的右子树...
  • 建立二叉搜索树c语言

    2021-05-24 02:27:56
    你可以在网上找到关于二叉搜索非常好的文章,我们不会提供二叉搜索的完整实现,但为了维持一致性,我们而是会举例表明一个简单的二叉搜索...相比之下,建立一个节点具有多个顺序索引(key)的平衡二叉搜索...
  • 代码里有二叉排序树插入操作递归算法,二叉排序树插入操作非递归算法,二叉排序树删除操作,创建二叉排序树二叉排序树查找递归算法,二叉排序树查找非递归算法
  • 教育资料 实验报告 课程名数据结构C语言版 实验名二叉排序树 姓名 班级 学号 撰写时间2014.12.18 一 实验目的与要求 掌握二叉排序树上进行插入和删除的操作 利用 C 语言实现该操作 二 实验内容 ? 对于一个线形表, ...
  • 本文用C语言实现了二叉排序树(也用到了C++中参数引用特性),并在二叉排序树中依次插入了{5,8,2,9,4,3,1,6,7,10},最终生成的二叉树如下图所示。中序遍历该树得到有序序列{1,2,3,4,5,6,7,8,9,10} ...
  • 中序遍历二叉排序树

    2018-06-30 21:06:55
    中序遍历二叉排序树 输入一整数序列,建立二叉排序树,然后中序遍历。 输入说明 输入第一行为整数的个数n,第二行是具体的n个整数。 输出说明 建立二叉排序树,然后输出中序遍历的结果。 输入样例 5 1 6 5 9 8 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,808
精华内容 3,123
关键字:

二叉排序树c语言

c语言 订阅