二叉排序树的增删改查

SqQue.c

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

/*
	功能：初始化队列
	参数：@maxl：最大长度
	返回值：顺序队列的头指针
*/
SqQue *InitSqQue(int maxl)
{
	SqQue *q = malloc(sizeof(*q));
	q->data = malloc(maxl * sizeof(element));
	q->max_len = maxl;
	q->rear = 0;
	q->front = 0;
	q->now_len = 0;
	return q;
} 

/*
	功能：清空顺序队列
	参数：头指针
*/
void clearSqQue(SqQue *q)
{
	if(q == NULL)
	{
		return;
	}
	q->now_len = 0;
	q->rear = 0;
	q->front = 0;
	return;
}

/*
	功能：销毁顺序队列
	参数：头指针
*/
void destroySqQue(SqQue *q)
{
	if(q == NULL)
	{
		return;
	}
	free(q->data);
	free(q);
	return;
	
}

/*
	功能：判断顺序队列是否为空
	参数：头指针
	返回值：1--成功；0--失败
*/
int SqQueisEmpty(SqQue *q)
{
	if(q == NULL||q->now_len == 0)
	{
		return 1;
	}
	return 0;
}

/*
	功能：求队列的长度
	参数：头指针
	返回值：队列的长度
*/
int SqQuelenth(SqQue *q)
{
	if(q == NULL||q->now_len == 0)
	{
		return 0;
	}
	return q->now_len;
}

/*
	功能：入队
	参数：头指针;入队的元素
	返回值：1--成功；0--失败
*/
int SqQuein(SqQue *q,element x)
{
	if(q == NULL || q->now_len == q->max_len)
	{
		return 0;
	}
	q->data[q->rear++] = x;
	q->rear = q->rear % q->max_len;
	q->now_len++;
	return 1;
}

/*
	功能：出队
	参数：头指针;存放出队元素
	返回值：1--成功；0--失败
*/
int SqQueout(SqQue *q,element *x)
{
	if(q == NULL || q->now_len == 0)
	{
		return 0;
	}
	*x = q->data[q->front++];
	printf("出队元素为：%d\n",&x);
	q->front = q->front % q->max_len;
	q->now_len--;
	return 1;
}

/*
	功能：获取队头元素，但不出队
	参数：头指针;存放队头元素
	返回值：1--成功；0--失败
*/
int getSqQue(SqQue *q,element *x)
{
	if(q == NULL || q->now_len == 0)
	{
		return 0;
	}
	*x = q->data[q->front];
	printf("队头元素为：%d\n",&x);
	return 1;
}

SqQue.h

#ifndef __SQQUE_H__
#define __SQQUE_H__

#include "bitree.h"


typedef biNode *element;//队列元素的类型， 是一个指针

typedef struct SqQue
{
	element *data;			//动态定义存储空间大小
	int max_len;		//存放最多的元素个数
	int now_len;		//当前的元素个数
	int rear;			//队尾下标，下一个入队元素的下标
	int front;     		//队头下标，下一个出队元素的下标
	
}SqQue;

/*
	功能：初始化队列
	参数：@maxl：最大长度
	返回值：顺序队列的头指针
*/
SqQue *InitSqQue(int maxl);

/*
	功能：清空顺序队列
	参数：头指针
*/
void clearSqQue(SqQue *q);

/*
	功能：销毁顺序队列
	参数：头指针
*/
void destroySqQue(SqQue *q);

/*
	功能：判断顺序队列是否为空
	参数：头指针
	返回值：1--成功；0--失败
*/
int SqQueisEmpty(SqQue *q);

/*
	功能：求队列的长度
	参数：头指针
	返回值：队列的长度
*/
int SqQuelenth(SqQue *q);

/*
	功能：入队
	参数：头指针;入队的元素
	返回值：1--成功；0--失败
*/
int SqQuein(SqQue *q,element x);

/*
	功能：出队
	参数：头指针;存放出队元素
	返回值：1--成功；0--失败
*/
int SqQueout(SqQue *q,element *x);

/*
	功能：获取队头元素，但不出队
	参数：头指针;存放队头元素
	返回值：1--成功；0--失败
*/
int getSqQue(SqQue *q,element *x);



#endif

bitree.c

#include<stdio.h>
#include<stdlib.h>
#include "SqQue.h"
#include "bitree.h"


/*
	Insert:在root指向的二叉排序树中，增加一个新结点p
		要保证添加后的二叉树是一棵排序性
	@root:指向根结点
	@p: 指向待添加的结点
	返回值：
		返回添加后的二叉排序树的根结点
*/

biNode *insert(biNode *root,biNode *p)
{
	if(root == NULL)
	{
		return p;
	}
	if(p == NULL)
	{
		return root;
	}
	//pf 表示查找路径(pk路径)上的最后一个结点
	//p 待插入的结点
	//p不是pf的左子结点就是pf的右子结点
	//1.查找插入位置
	biNode *pf = root;			//pf指向查找路径上的结点
	biNode *pk = NULL;			//pk指向最后一个结点
	while(pf)
	{
		if(p->data > pf->data)
		{
			pk = pf;
			pf = pf->rchild;
		}
		else if(p->data < pf->data)
		{
			pk = pf;
			pf = pf->lchild;
		}
		else
		{
			return root;
		}
	}
	//2.插入结点
	if(p->data > pk->data)
	{
		pk->rchild = p;
	}
	else
	{
		pk->lchild = p;
	}
	return root;
}

/*
	Insert2:在root指向的二叉排序树中，增加一个新结点p
		要保证添加后的二叉树是一棵排序性
	@root:指向根结点
	@p: 指向待添加的结点
	返回值：
		返回添加后的二叉排序树的根结点
*/

biNode *insert2(biNode *root,biNode *p)
{
	if (root == NULL)
	{
		return p;
	}

	if(p == NULL)
	{
		return root;
	}

	if(p->data > root->data)
	{
		root->rchild = insert2(root->rchild,  p);
	}
	else if(p->data < root->data)
	{
		root->lchild = insert2(root->lchild, p);
	}
	return root;
}

//先序遍历
void pre_order(biNode *t)
{
	if(t != NULL)
	{
		printf("%d ",t->data);
		pre_order( t->lchild);
		pre_order( t->rchild);
	}
	
}
//中序遍历
void mid_order(biNode *t)
{
	if(t != NULL)
	{
		mid_order( t->lchild);
		printf("%d ",t->data);
		mid_order( t->rchild);
	}
}
//后序遍历
void last_order(biNode *t)
{
	if(t != NULL)
	{
		last_order(t->lchild);
		last_order(t->rchild);
		printf("%d ",t->data);
	}
}


//层次遍历
void level_order(biNode *t)
{
	if(t == NULL)
	{
		return;
	}
	SqQue *q = InitSqQue(1024);
	SqQuein(q,t);
	while(!SqQueisEmpty(q))
	{
		//出队
		element x;
		SqQueout(q,&x);
		//访问出队元素
		printf("%d ",x->data);
		//让出队元素的左子结点入队
		if(x->lchild)
		{
			SqQuein(q,x->lchild);
		}
		if(x->rchild)
		{
			SqQuein(q,x->rchild);
		}
	}
	destroySqQue(q);
	return;
}

/*
	功能：删除指定结点
	参数：t：根结点；x：要删除的数据
	返回值：新二叉树的根结点
*/
biNode *delete_x(biNode *t,telement x)
{
	biNode *px = t;		//指向删除的结点
	biNode *pf = NULL; 	//指向删除的结点的父结点
	//1.找到要删除的结点及它的父结点
	while(px)
	{
		if(x > px->data)
		{
			pf = px;
			px = px->rchild;
		}
		else if(x < px->data)
		{
			pf = px;
			px = px->lchild;
		}
		else
		{
			break;
		}
	}
	if(px == NULL)
	{
		return t;
	}
	//2.分情况删除
delete_node:
	if(px->rchild == NULL && px->lchild == NULL)		//为叶子结点，没有左孩子和右孩子
	{
		if(px == t)										//只有一个根结点
		{
			free(px);
			return NULL;
		}
		
		if(pf->lchild == px)							
		{
			pf->lchild = NULL;
		}
		else
		{
			pf->rchild = NULL;
		}
		free(px);
		return t;
	}
	else if(px->rchild == NULL && px->lchild != NULL)	//右子树为空，左子树不为空
	{
		if(px == t)
		{
			t = px->lchild;
			px->lchild = NULL;
			free(px);
			return t;
		}
		else
		{
			if(pf->lchild == px)
			{
				pf->lchild = px->lchild;
			}
			else
			{
				pf->rchild = px->lchild;	
			}
			px->lchild = NULL;
			free(px);
			return t;
		}
	}
	else if(px->rchild != NULL && px->lchild == NULL)	//左子树为空，右子树不为空
	{
		if(px == t)
		{
			t = px->rchild;
			px->rchild = NULL;
			free(px);
			return t;
		}
		else
		{
			if(pf->rchild = px)
			{
				pf->rchild = px->rchild;
			}
			else
			{
				pf->lchild = px->rchild;
			}
			px->rchild = NULL;
			free(px);
			return t;
		}
	}
	else												//左右子树都不为空
	{
		//找一个“替罪羊”
		//右子树中最小的结点or左子树中最大的结点，与其交换
		biNode *pr = px;								//记录要删除的那个结点
		pf = px;
		px = px->rchild;
		while(px->lchild)
		{
			pf = px;
			px = px->lchild;
		}
		pr->data = px->data;
		goto delete_node;
	}
	
}

bitree.h

#ifndef __BITREE_H__
#define __BITREE_H__
typedef int telement ;//树中结点元素的数据类型

typedef struct biNode
{
	telement data;			//数据域
	struct biNode *lchild;	//左孩子
	struct biNode *rchild;	//右孩子
}biNode;

/*
	Insert:在root指向的二叉排序树中，增加一个新结点p
		要保证添加后的二叉树是一棵排序性
	@root:指向根结点
	@p: 指向待添加的结点
	返回值：
		返回添加后的二叉排序树的根结点
*/

biNode *insert(biNode *root,biNode *p);

/*
	Insert2:在root指向的二叉排序树中，增加一个新结点p
		要保证添加后的二叉树是一棵排序性
	@root:指向根结点
	@p: 指向待添加的结点
	返回值：
		返回添加后的二叉排序树的根结点
*/

biNode *insert2(biNode *root,biNode *p);

//先序遍历
void pre_order(biNode *t);

//中序遍历
void mid_order(biNode *t);

//后序遍历
void last_order(biNode *t);

//层次遍历
void level_order(biNode *t);

/*
	功能：删除指定结点
	参数：t：根结点；x：要删除的数据
	返回值：新二叉树的根结点
*/
biNode *delete_x(biNode *t,telement x);


#endif

main.c

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

int main()
{
	biNode *root = NULL;
	int d;
	while(1)
	{
		scanf("%d",&d);
		if(d == 0)
		{
			break;
		}
		biNode *p = malloc(sizeof(*p));
		p->data = d;
		p->rchild = NULL;
		p->lchild = NULL;
		root = insert(root,p);
	}
	printf("先序:");
	pre_order(root);
	
	printf("\n中序:");
	mid_order(root);
	printf("\n后序:");
	last_order(root);
	printf("\n层次遍历:\n");
	last_order(root);
	int x;
	scanf("%d",&x);
	delete_x(root,x);
	printf("先序:");
	pre_order(root);
	return 0;
}

原文链接：https://blog.csdn.net/zillll/article/details/124950250